๊ณ์ ์ ๋ ฌ (count sort)
- ๊ณ์์ ๋ ฌ์ ๋ฐ์ดํฐ์ ํฌ๊ธฐ ๋ฒ์๊ฐ ์ ํ๋์ด ์ ์ํํ๋ก ํํ๋ ์ ์์๋ ํจ๊ณผ์ ์ผ๋ก ์ฌ์ฉํ ์ ์๋ค. (์ผ๋ฐ์ ์ผ๋ก ํฐ ๋ฐ์ดํฐ์ ์์ ๋ฐ์ดํฐ์ ์ฐจ์ด๊ฐ 1,000,000์ด ๋์ง ์์๋ ์ฌ์ฉํ๋ค.)
- ๋ฐ์ดํฐ์ ๊ฐ์๊ฐ N, ๋ฐ์ดํฐ ์ค ์ต๋๊ฐ์ด K์ผ๋, ์ต์ ์ ๊ฒฝ์ฐ์๋ O(n+k)์ ์ํ์๊ฐ์ ๋ณด์ฅํ๋ ๋น ๋ฅธ ์ ๋ ฌ๋ฒ์ด๋ค.
- ๋์์๋ฆฌ๋ ๋ง์ฝ ์ต์0๋ถํฐ ์ต๋1,000,000์ ๋ฐ์ดํฐ๊ฐ ์ฃผ์ด์ง๋ ๊ฒฝ์ฐ, '๋ชจ๋ ๋ฒ์๋ฅผ ๋ด์ ์ ์๋ ๋ฆฌ์คํธ' - ์ฆ 1,000,001๊ฐ์ ๋ฆฌ์คํธ๋ฅผ ์ ์ธํ์ฌ ๊ฐ ๊ฐ์ ๋ด๋๊ฒ์ด๋ค. ๊ทธ๋์ ๋งค์ฐ ํฐ ๋ฒ์๋ ์ฌ์ฉํ ์ ์๋ค.
def count_sort(array):
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] += 1 # (array[0] = 7) => count[7] += 1
for i in range(len(count)):
for _ in range(count[i]): # count[1]๊ฐ ๋ง์ฝ 3์ด๋ผ๋ฉด 1์ 3๋ฒ ๋ฐ๋ณตํ์ฌ
print(i, end=' ') # 1 1 1 ์ด๋ผ๋ ์ถ๋ ฅ์ ํ๋ค.
์ฝ์ ์ ๋ ฌ (insertion sort)
- ํ๊ท ์ ์ผ๋ก O(n^2)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง์ง๋ง ํ์ฌ ๋ฐ์ดํฐ ๋ฆฌ์คํธ๊ฐ ๊ฑฐ์ ์ ๋ ฌ๋ ์ํ์ผ๋ ์ต๋ O(n)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.
- ์ฆ, ์ฃผ์ด์ง ๋ฐ์ดํฐ๊ฐ ๊ฑฐ์ ์ ๋ ฌ๋ ์ํ๋ผ๋ฉด ํต์ ๋ ฌ๋ณด๋ค ๋ ํจ์จ์ ์ด๋ฏ๋ก ๋ฐ์ดํฐ์ ์ํ๋ฅผ ๋ณด๊ณ ์ฌ์ฉํ๋ฉด ํจ๊ณผ์ ์ด๋ค.
def insertion_sort(array):
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j] < array[j - 1]:
array[j], array[j - 1] = array[j - 1], array[j] # ๋ง์ฝ array[i]๋ณด๋ค array[i-1]์ด ํฌ๋ค๋ฉด ๋ ์ธ๋ฑ์ค ์ค์
else: break
return(array)
์ ํ ์ ๋ ฌ (selection sort)
- ์ง๊ด์ ์ด์ง๋ง O(n^2)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ ธ ๋งค์ฐ ๋๋ฆฌ๋ฏ๋ก ์ฌ์ฉํ ์ผ์ ์ ๋ค.
- ์ ๋ ฌ์ ๊ธฐ๋ณธ ์ฝ๋๋ก ์งํ ๋ฐฉ์์ ์ดํดํ๊ธฐ ์ข์ ์ฝ๋์ด๋ค.
def selection_sort(array):
for i in range(len(array)):
min_index = i
for j in range(i + 1, len(array)):
if(array[min_index] > array[j]):
min_index = j
array[i], array[min_index] = array[min_index], array[i]
return(array)
'์ฝ๋ฉํ ์คํธ > ๊ธฐ๋ณธ ์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
์์ฐจํ์(Sequential_Search) (0) | 2022.02.20 |
---|---|
์ด์งํ์(Binary_Search) (0) | 2022.02.20 |
๊น์ด ์ฐ์ ํ์(DFS) (0) | 2022.02.20 |
๋๋น ์ฐ์ ํ์(BFS) (0) | 2022.02.20 |
์ ๋ ฌ ์ฝ๋2(ํต ์ ๋ ฌ, ๋ณํฉ ์ ๋ ฌ) (0) | 2022.01.10 |