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

๐Ÿ’ป Selection Sort, ์„ ํƒ ์ •๋ ฌ์ด๋ž€?

Pseudo-code ์„ค๋ช…

์œ„๋Š” Selection Sort(์„ ํƒ์ •๋ ฌ)์˜ pseudo-์ฝ”๋“œ์ด๋‹ค. i๊ฐ€ 1๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜์ง€๋งŒ, ๊ฐ€์žฅ ์ฒซ Index๋ฅผ ์˜๋ฏธํ•˜๊ณ  ํ”„๋กœ๊ทธ๋žจ์„ ํ•  ๋•Œ๋Š” 0 index์ด๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋งค iteration๋งˆ๋‹ค 2๊ฐ€์ง€ ๋™์ž‘์„ ์ˆ˜ํ–‰ํ•œ๋‹ค. list๋‚ด์—์„œ ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ์ฐพ๊ณ  list์•ž์—๋‹ค ์ •๋ ฌํ•œ๋‹ค. ๊ทธ ๋‹ค์Œ์— ์ •๋ ฌ๋œ ๊ฐ’๋ณด๋‹ค ํ•˜๋‚˜ ํฐ ๊ฐ’์—์„œ ๋‹ค์‹œ ๊ฐ™์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ ์šฉํ•œ๋‹ค.

๊ธ€๋กœ ํ’€์–ด๋ณด๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

  1. min์ด๋ž€ ๋ณ€์ˆ˜์— i๋ฅผ ์ €์žฅํ•œ๋‹ค.
  2. j์—๋Š” i +1 ๊ฐ’์„ ๋Œ€์ž…ํ•œ๋‹ค.
  3. j๋ถ€ํ„ฐ list ๋๊นŒ์ง€ ์‚ดํŽด๋ณด๋ฉด์„œ ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ์ฐพ๊ณ  ๊ทธ index๋ฅผ min์— ์ €์žฅํ•œ๋‹ค.
  4. ๋งŒ์•ฝ min ๊ฐ’์ด ๋ฐ”๋€Œ์—ˆ๋‹ค๋ฉด i ์ž๋ฆฌ์˜ item๊ณผ min ์ž๋ฆฌ์˜ item์„ ๋ฐ”๊พผ๋‹ค.
  5. i += 1์„ ํ•˜๊ณ  1๋ฒˆ์œผ๋กœ ๋Œ์•„๊ฐ„๋‹ค.

ํ•œ iteration์— list๋‚ด์˜ ๋ชจ๋“  item์„ ์‚ดํŽด๋ณด๊ณ , ์ด๋Ÿฌํ•œ ๊ณผ์ •์„ list์˜ ๊ธธ์ด๋งŒํผ ์ง„ํ–‰ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ด sorting algorithm์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” `O(n^2)`๊ฐ€ ๋˜๋Š” ๊ฒƒ์ด๋‹ค. iteration ์ˆ˜๋Š” ์–ธ์ œ๋‚˜ ist ๊ธธ์ด์™€ ๊ฐ™๊ธฐ ๋•Œ๋ฌธ์— average์™€ worst case์—์„œ์˜ ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ ๊ฐ™๋‹ค.

iteration ๊ณผ์ •์„ ๊ฐ„๋‹จํžˆ ์‚ดํŽด๋ณด์ž

์ฒซ๋ฒˆ์งธ iteration์—์„œ๋Š” 7๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ list ์ „์ฒด๋ฅผ ํ๊ณ  1์ด ์ œ์ผ ์ž‘์€ ๊ฒƒ์„ ํŒŒ์•…ํ–ˆ๊ณ  1์„ ๋งจ ์•ž์— ์œ„์น˜ํ–ˆ๋‹ค.

๋‘๋ฒˆ์งธ iteration์—์„œ๋Š” 1์„ ์ œ์™ธํ•˜๊ณ  ๊ทธ ๋‹ค์Œ item์ธ 4๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ list ์ „์ฒด๋ฅผ ํ๊ณ  2๊ฐ€ ์ œ์ผ ์ž‘์Œ์„ ํŒŒ์•…ํ–ˆ๋‹ค. ๊ทธ๋ž˜์„œ 2๋ฅผ 1 ๋‹ค์Œ์— ์œ„์น˜ํ–ˆ๋‹ค.

์„ธ๋ฒˆ์งธ iteration์—์„œ๋Š” 1,2๋ฅผ ์ œ์™ธํ•˜๊ณ  ๊ทธ ๋‹ค์Œ item์ธ 5๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ list ์ „์ฒด๋ฅผ ํ๊ณ  4๊ฐ€ ์ œ์ผ ์ž‘์Œ์„ ํŒŒ์•…ํ–ˆ๋‹ค. ๊ทธ๋ž˜์„œ 1, 2 ๋‹ค์Œ์— 4๋ฅผ ๋’€๋‹ค.

...

iteration์„ list์˜ item๋ณด๋‹ค ํ•˜๋‚˜ ์ž‘์€ ์ˆ˜ ๋งŒํผ ๋ฐ˜๋ณต์„ ํ•˜๋ฉด โ‡’ ๋ฆฌ์ŠคํŠธ๊ฐ€ ์ •๋ ฌ์ด ๋œ๋‹ค.

Python Code

import random

def selection_sort(num):
    for i in range(len(num)):
        minimum = i
        for j in range(i+1, len(num)): # i๋ณด๋‹ค ํ•˜๋‚˜ ํฐ ์ˆ˜๋ถ€ํ„ฐ list๋๊นŒ์ง€ iterateํ•œ๋‹ค
            if num[j] < num[minimum]: 
                minimum = j # list๋‚ด์— ์ œ์ผ ์ž‘์€ ์ˆซ์ž๋ฅผ ์ฐพ๊ณ  ๊ทธ index๋ฅผ minumum ๋ณ€์ˆ˜์— ์ €์žฅํ•œ๋‹ค
        if minimum != i: 
            num[i], num[minimum] = num[minimum], num[i]
    return num


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