Insertion Sort
์ ๋ ฌ ๊ณผ์
์ ๋ ฌํ ์๋ฃ๋ฅผ ๋ ๊ฐ์ ๋ถ๋ถ์งํฉ S์ U๋ก ๊ฐ์
๋ถ๋ถ์งํฉ S
: ์ ๋ ฌ๋ ์๋ถ๋ถ์ ์์๋ค๋ถ๋ถ์งํฉ U
: ์์ง ์ ๋ ฌ๋์ง ์์ ๋๋จธ์ง ์์๋ค
์ ๋ ฌ๋์ง ์์ ๋ถ๋ถ์งํฉ U์ ์์๋ฅผ ํ๋์ฉ ๊บผ๋ด์ ์ด๋ฏธ ์ ๋ ฌ๋์ด์๋ ๋ถ๋ถ์งํฉ S์ ๋ง์ง๋ง ์์๋ถํฐ ๋น๊ตํ๋ฉด์ ์์น๋ฅผ ์ฐพ์ ์ฝ์ ํ๋ค.
์ฝ์ ์ ๋ ฌ์ ๋ฐ๋ณตํ๋ฉด์ ๋ถ๋ถ์งํฉ S์ ์์๋ ํ๋์ฉ ๋๋ฆฌ๊ณ ๋ถ๋ถ์งํฉ U์ ์์๋ ํ๋์ฉ ๊ฐ์ํ๊ฒ ๋๋ค.
๋ถ๋ถ์งํฉ U๊ฐ ๊ณต์งํฉ์ด ๋๋ฉด ์ฝ์ ์ ๋ ฌ์ด ์์ฑ๋๋ค
์๊ฐ ๋ณต์ก๋
O (n ^ 2)
๊ฐ ๋ถ๋ถ์งํฉ์ ์์๋ฅผ ๋งค๋ฒ ๋น๊ตํด์ผ ํ๋ฏ๋ก!
Iterative Selection Sort
arr = [69, 10, 30, 2, 16, 8, 31, 22]
N = len(arr)
for i in range(1,N): # 1 ~ N-1
tmp = arr[i]
print(arr[:i], arr[i:])
j = i -1
while j >= 0 and arr[j] > tmp:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = tmp
print(arr)
Last updated
Was this helpful?