Sep 14, 2019 โ€ข2 min read โ˜•

๐Ÿ’ป Bubble Sort, ๋ฒ„๋ธ” ์ •๋ ฌ์ด๋ž€?

Pseudo-code ์„ค๋ช…

์œ„๋Š” Bubble Sort(๋ฒ„๋ธ”์ •๋ ฌ)์˜ pseudo-์ฝ”๋“œ์ด๋‹ค. ์ •๋ ฌ์„ ํ•œ๋‹ค๊ณ  ํ–ˆ์„ ๋•Œ ๊ฐ€์žฅ ๋– ์˜ฌ๋ฆฌ๊ธฐ ์‰ฝ๊ณ  ๊ตฌํ˜„ํ•˜๊ธฐ ์‰ฌ์šด ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ผ๊ณ  ์ƒ๊ฐํ•œ๋‹ค. ์ฒ˜์Œ์— 2๊ฐœ์”ฉ ๋น„๊ต๋ฅผ ํ•˜๋ฉด์„œ ์™ผ์ชฝ์ด ์˜ค๋ฅธ์ชฝ๋ณด๋‹ค ํฌ๋ฉด ๋ฐ”๊ฟ”์„œ ๊ฐ€์žฅ ํฐ ๊ฐ’์ด iteration ๋งˆ๋‹ค ๋งจ ๋’ค์— ์œ„์น˜ํ•˜๊ฒŒ ํ•œ๋‹ค. (๋ฐ˜๋Œ€๋กœ ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ๋งจ ์•ž์œผ๋กœ ์œ„์น˜ํ•˜๊ฒŒ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค)

์ด pseudo-์ฝ”๋“œ๋Œ€๋กœ ์ง„ํ–‰ํ•˜๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

  1. list ๋งจ์•ž๋ถ€ํ„ฐ list์˜ ๊ธธ์ด๊นŒ์ง€ iteration ์ง„ํ–‰ํ•œ๋‹ค.
  2. list ๋๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ ๊ทธ ์•ž์— item๊ณผ ๋น„๊ต๋ฅผ ํ•˜๊ณ  ํ˜„ item์ด ๋” ์ž‘์œผ๋ฉด swap์„ ํ•œ๋‹ค, ์ด๋Ÿฌํ•œ ๋น„๊ต๋ฅผ i + 1๊นŒ์ง€ iteration ์ง„ํ–‰ํ•œ๋‹ค.

pseudo-์ฝ”๋“œ๋งŒ ๋ด๋„ ๋‹ค๋ฅธ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค๋ณด๋‹ค ๋” ๋‹จ์ˆœํ•ด๋ณด์ด๋Š” ๊ฒƒ์„ ๋ณผ ์ˆ˜ ์žˆ๋‹ค. list๊ธธ์ด๋งŒํผ iteration์„ ํ•˜๋Š”๋ฐ, iteration๋งˆ๋‹ค ๋์—์„œ๋ถ€ํ„ฐ ๋งจ ์•ž๊นŒ์ง€ ๋‹ค์‹œ ํ•œ๋ฒˆ iteration์„ ํ•˜๋ฉฐ item๋ผ๋ฆฌ ๋น„๊ต๋ฅผ ํ•œ๋‹ค. ๋‘ ๋ฒˆ์˜ for loop iteration์˜ ํšŸ์ˆ˜๋ฅผ ์ œ๊ณฑ๋งŒํผ ๋Š˜๋ฆฌ๊ธฐ ๋•Œ๋ฌธ์— ์ด sorting algorithm์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(n^2)๊ฐ€ ๋˜๋Š” ๊ฒƒ์ด๋‹ค.

๊ทธ๋ฆผ์— ์žˆ๋Š” iteration ๊ณผ์ •์„ ๊ฐ„๋‹จํžˆ ์‚ดํŽด๋ณด์ž. ํ•ด๋‹น ๊ทธ๋ฆผ์€ pseudo-์ฝ”๋“œ์™€๋Š” ๋ฐ˜๋Œ€ ๋ฐฉํ–ฅ์œผ๋กœ ์ง„ํ–‰๋˜์„œ ํฐ ๊ฐ’์„ ๋จผ์ € ๋’ค๋กœ ์œ„์น˜ํ–ˆ๋‹ค.

๋‘ ๋ฒˆ์งธ for loop๋‚ด,

์ฒซ๋ฒˆ์งธ iteration์—์„œ -2์™€ 45๋ฅผ ๋น„๊ตํ–ˆ๋”๋‹ˆ ์˜ค๋ฅธ์ชฝ์— ์žˆ๋Š” 45๊ฐ€ ๋” ํฌ๊ธฐ ๋•Œ๋ฌธ์— ๋‹ค์Œ์œผ๋กœ ๋„˜์–ด๊ฐ„๋‹ค.

๋‘๋ฒˆ์งธ iteration์—์„œ๋Š” 45์™€ 0์„ ๋น„๊ตํ•˜๊ณ  0์ด ๋” ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์„œ๋กœ์˜ ์œ„์น˜๋ฅผ ๋ฐ”๊ฟจ๋‹ค.

์„ธ๋ฒˆ์งธ iteration์—์„œ๋Š” 45์™€ 11์„ ๋น„๊ตํ•˜๊ณ  11์ด ๋” ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์„œ๋กœ์˜ ์œ„์น˜๋ฅผ ๋ฐ”๊ฟจ๋‹ค.

๋„ค๋ฒˆ์งธ iteration์—์„œ๋Š” 45์™€ -9๋ฅผ ๋น„๊ตํ•˜๊ณ  -9๊ฐ€ ๋” ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์„œ๋กœ์˜ ์œ„์น˜๋ฅผ ๋ฐ”๊ฟจ๋‹ค.

์ด๋ ‡๊ฒŒ ๋‘ ๋ฒˆ์งธ for loop์˜ iteration์ด ๋๋‚˜๋ฉด, ๊ฐ€์žฅ ๋์ด ์ œ์ผ ํฐ ๊ฐ’์œผ๋กœ ์ •๋ ฌ๋œ๋‹ค. ๊ทธ ๋‹ค์Œ๋ฒˆ์—์„œ๋Š” ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ item์„ ์ œ์™ธํ•˜๊ณ  ๋‚˜๋จธ์ง€ item๋ผ๋ฆฌ๋งŒ ๋น„๊ต๋ฅผ ํ•œ๋‹ค.

Python Code

๊ทธ๋ฆผ๊ณผ ๋น„์Šทํ•œ ๋ฐฉํ–ฅ์œผ๋กœ ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ–ˆ๋‹ค

import random

def bubble_sort(num):
    for i in range(len(num)):
        for j in range(len(num)-1-i): # ๋งจ ์•ž๋ถ€ํ„ฐ ๋น„๊ต๋ฅผ ์‹œ์ž‘ํ•œ๋‹ค
            if num[j]>num[j+1]:
                num[j], num[j+1] = num[j+1], num[j] # swapํ•œ๋‹ค
    return num


number = [i for i in range(10)]
random.shuffle(number)
print(number)
bubble = bubble_sort(number)
print(bubble)
ยฉ 2021 Dojin Kim, Built with Gatsby