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

๐Ÿ’ป Insertion Sort, ์‚ฝ์ž… ์ •๋ ฌ์ด๋ž€?

Pseudo-code ์„ค๋ช…

์œ„๋Š” Insertion Sort(์‚ฝ์ž…์ •๋ ฌ)์˜ pseudo-์ฝ”๋“œ์ด๋‹ค. j๊ฐ€ 2๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๊ณ  ์ด๋Š” list๋‚ด 2๋ฒˆ์งธ item์„ ์˜๋ฏธํ•œ๋‹ค, ์ฆ‰, ํ”„๋กœ๊ทธ๋ž˜๋ฐํ•  ๋•Œ๋Š” index 1์„ ์˜๋ฏธํ•œ๋‹ค. ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ list๋ฅผ iterateํ•˜๋ฉด์„œ list ์•ž ์ชฝ๋ถ€ํ„ฐ ์ •๋ ฌ์„ ํ•ด๋‚˜๊ฐ„๋‹ค. ์ •๋ ฌ์„ ํ•˜๊ณ  ๋‚˜์„œ ๊ทธ ๋‹ค์Œ item์œผ๋กœ ์ด๋™ํ•˜๊ณ  ํ•ด๋‹น item์„ ์ •๋ ฌ๋œ ์™ผ์ชฝ list์— ์ •๋ ฌ๋œ ์ˆœ์„œ์— ์‚ฝ์ž…์„ ํ•œ๋‹ค.

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

  1. list์˜ 2๋ฒˆ์งธ item๋ถ€ํ„ฐ ์‹œ์ž‘ํ•œ๋‹ค. (์ฒซ๋ฒˆ์งธ item์€ ์ด๋ฏธ ์ •๋ ฌ๋œ list๋ผ๊ณ  ๊ฐ„์ฃผํ•œ๋‹ค, item์ด ํ•˜๋‚˜์ธ list์—์„œ ๊ทธ item์€ ํ•ญ์ƒ ์ •๋ ฌ๋œ ์ƒํƒœ์ด๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค)
  2. key๋ผ๋Š” ๋ณ€์ˆ˜์— list์˜ j๋ฒˆ์งธ ๊ฐ’์„ ์ €์žฅํ•œ๋‹ค.
  3. i๋ผ๋Š” ๋ณ€์ˆ˜์— j - 1 ๊ฐ’์„ ์ €์žฅํ•œ๋‹ค. (list์˜ i๋ฒˆ์งธ ๊ฐ’์„ ์™ผ์ชฝ์— ์ •๋ ฌ๋œ list์— ๋น„๊ต๋ฅผ ํ•˜๋ฉฐ ์‚ฝ์ž…ํ•˜๊ธฐ ์œ„ํ•จ์ด๋‹ค)
  4. while๋ฌธ

    1. key๊ฐ€ list[i]๋ณด๋‹ค ์ž‘์œผ๋ฉด list[i+1] (j์˜ ์œ„์น˜๋ฅผ ์˜๋ฏธํ•œ๋‹ค)์— ์ •๋ ฌ๋œ list์˜ ๊ฐ€์žฅ ํฐ ๊ฐ’์„ ๋ณต์‚ฌํ•œ๋‹ค.
    2. i -= 1 ์„ ํ•˜๊ณ  4.1๋ฒˆ์„ ๋ฐ˜๋ณตํ•œ๋‹ค. ๋งŒ์•ฝ list๋งจ ์•ž๊นŒ์ง€ ๋„๋‹ฌํ•˜๋ฉด loop์„ ์ข…๋ฃŒํ•œ๋‹ค.
  5. key ๊ฐ’์„ list[i+1]์— ์ €์žฅํ•œ๋‹ค. (์ด ๋ถ€๋ถ„์ด ์ •๋ ฌ๋œ list์— ์ƒˆ๋กœ์šด ์ˆซ์ž๋ฅผ ์‚ฝ์ž…ํ•˜๋Š” ๊ฒƒ์ฒ˜๋Ÿผ ๋ณด์ด๊ฒŒ ๋งŒ๋“ ๋‹ค)
  6. j += 1์„ ํ•˜๊ณ  2๋ฒˆ๋ถ€ํ„ฐ ๋‹ค์‹œ ๋ฐ˜๋ณตํ•œ๋‹ค.

ํ•œ iteration์— list๋‚ด์˜ ๋ชจ๋“  item์„ ํ•œ๋ฒˆ ์‚ดํŽด๋ณธ๋‹ค. ๊ทธ๋ฆฌ๊ณ  iteration์ค‘์— ์„ ํƒ๋œ item์„ ์ •๋ ฌ๋œ list์—์„œ ๋‹ค์‹œ ๋น„๊ตํ•˜๋ฉฐ ์‚ดํŽด๋ณธ๋‹ค. ๊ทธ๋ž˜์„œ, ์ด sorting algorithm์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” `O(n^2)`๊ฐ€ ๋˜๋Š” ๊ฒƒ์ด๋‹ค.

๊ทธ๋ฆผ์— ์žˆ๋Š” iteration ๊ณผ์ •์„ ๊ฐ„๋‹จํžˆ ์‚ดํŽด๋ณด์ž

์ฒซ๋ฒˆ์งธ iteration์—์„œ๋Š” 9๋Š” ์ด๋ฏธ ์ •๋ ฌ๋œ ์ƒํƒœ์ด๊ณ , list[1]์ธ 7๊ณผ indexํ•˜๋‚˜ ์ž‘์€ 9์™€ ๋น„๊ต๋ฅผ ํ•œ๋‹ค. 7์ด ๋” ์ž‘๊ธฐ ๋•Œ๋ฌธ์— 7์„ 9์•ž์œผ๋กœ ์‚ฝ์ž…์„ ํ•œ๋‹ค.

๋‘๋ฒˆ์งธ iteration์—์„œ๋Š” [7,9]๋Š” ์ด๋ฏธ ์ •๋ ฌ๋œ ์ƒํƒœ์ด๊ณ , list[2]์ธ 6๊ณผ 9๋ฅผ ๋น„๊ตํ•œ๋‹ค. 9๊ฐ€ ๋” ํฌ๊ธฐ ๋•Œ๋ฌธ์— ํ•œ์นธ ๋” ์™ผ์ชฝ์œผ๋กœ ์›€์ง์—ฌ์„œ 6๊ณผ 7์„ ๋น„๊ตํ•œ๋‹ค. ์ด๋•Œ 6์ด ๋” ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ๋งจ ์•ž์œผ๋กœ ์‚ฝ์ž…์„ ํ•œ๋‹ค.

์„ธ๋ฒˆ์งธ iteration์—์„œ๋Š” 15๊ฐ€ ์ •๋ ฌ๋œ list [6,7,9] ์ค‘์—์„œ ๊ฐ€์žฅ ํฐ 9๋ณด๋‹ค๋„ ํฌ๊ธฐ ๋•Œ๋ฌธ์— ์ถ”๊ฐ€์ ์ธ ์ด๋™์„ ํ•˜์ง€ ์•Š๋Š”๋‹ค.

...

list์˜ ๋งจ ๋งˆ์ง€๋ง‰ item์„ ์™ผ์ชฝ์— ์ •๋ ฌ๋œ list์— ์ •๋ ฌ๋œ ์ƒํƒœ๋ฅผ ์œ ์ง€ํ• ๋งŒํ•œ ์œ„์น˜์— ์‚ฝ์ž…์„ ํ•˜๊ฒŒ ๋˜๋ฉด โ‡’ ๋ฆฌ์ŠคํŠธ๊ฐ€ ์ •๋ ฌ์ด ๋œ๋‹ค.

Python Code

import random

def insertion_sort(num):
    for j in range(1,len(num)):
        key = num[j] 
        i = j - 1
        while i>=0 and (num[i] > key): # i๊ฐ€ list๋งจ ์•ž๊นŒ์ง€ ์˜ค๋˜์ง€, num[i]๊ฐ€ ์œ„์— ์ €์žฅ๋œ num[j]๋ณด๋‹ค ์ž‘์œผ๋ฉด loop๋น ์ ธ ๋‚˜์˜จ๋‹ค.
            num[i+1] = num[i]
            i -= 1
        num[i+1] = key
    return num


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