ํต ์ ๋ ฌ (quick sort)
- ํต์ ๋ ฌ์ ์ฝ์ ์ ๋ ฌ๊ณผ ๋ค๋ฅด๊ฒ '์ด๋ฏธ ๋ฐ์ดํฐ๊ฐ ๊ฑฐ์ ์ ๋ ฌ๋ ๊ฒฝ์ฐ' ์๊ฐ๋ณต์ก๋๊ฐ ๊ฑฐ์ O(n^2)์ผ๋ก ๋งค์ฐ ๋๋ฆฌ๊ฒ ๋์ํ๋ค.
- ํ์ง๋ง ๋ฐ์ดํฐ๊ฐ ๋ฌด์์๋ก ์ ๋ ฅ๋๋ ๊ฒฝ์ฐ O(nlogn)์ ์๋๋ก ๋งค์ฐ ๋น ๋ฅด๊ฒ ๋์ํ๋ค. ๊ทธ๋ฌ๋ฏ๋ก ๋ฐ์ดํฐ์ ์ํ๋ฅผ ๋ณด๊ณ ์ฝ์ ์ ๋ ฌ๊ณผ ์ ์ ํํ์ฌ ์ฌ์ฉํด์ผํ๋ค.
def quick_sort(array, start, end):
if start >= end: # ์๋ ์ฌ๊ทํจ์์์ ๋ชจ๋ ์ ๋ ฌ์ด ๋๋๊ณ ์์๊ฐ 1๊ฐ์ธ ๊ฒฝ์ฐ ์ข
๋ฃ
return
pivot = start
left = start + 1
right = end
while left <= right:
while left <= end and array[left] <= array[pivot]:
left += 1
while right > start and array[right] >= array[pivot]:
right -= 1
if left > right: # left์ right๊ฐ ๊ต์ฐจํ ๋ ์์๊ฐ(right(์๊ฐ๋ ธ์ผ๋ฏ๋ก))๊ณผ pivot ๊ต์ฒด
array[right], array[pivot] = array[pivot], array[right]
else: # ๋ง์ฝ ๊ต์ฐจํ์ง ์์๋ค๋ฉด left์ right ๊ต์ฒด
array[left], array[right] = array[right], array[left]
quick_sort(array, start, right - 1) # pivot ๊ธฐ์ค ์ผ์ชฝ
quick_sort(array, right + 1, end) # pivot ๊ธฐ์ค ์ค๋ฅธ์ชฝ ์ฌ๊ทํจ์๋ฅผ ํตํด ๋ค์ ์ ๋ ฌ
ํต ์ ๋ ฌ2 (quick sort)
- ํ์ด์ฌ์ ์ฅ์ ์ ์ด๋ฆฐ ์ข ๋ ์งง๊ณ ์ง๊ด์ ์ธ quick sort code (๋น๊ต ํ์๊ฐ ์ฆ๊ฐํ์ฌ ํจ์จ์ ์กฐ๊ธ ๊ฐ์)
def quick_sort(array):
if len(array) <= 1:
return array
pivot = array[0]
tail = array[1:]
left_side = [x for x in tail if x <= pivot] # ํผ๋ด์ ์ ์ธํ ๋ฆฌ์คํธ tail ์ค ํผ๋ด๋ณด๋ค ์์ ๊ฐ์ left_side ๊ฐ์ฒด์ ์ ์ฅ (๋ชจ๋ tail์ ๋ํด ๋น๊ต๋ฅผ ํ๋ฏ๋ก ๋ ์ฐ์ฐํ์๊ฐ ๋ง์)
right_side = [x for x in tail if x > pivot] # ๊ฐ์ ๋ฐฉ์์ผ๋ก ํผ๋ด๋ณด๋ค ํฐ ๊ฐ์ right_side ๊ฐ์ฒด์ ์ ์ฅ return
quick_sort(left_side) + [pivot] + quick_sort(right_side) # ์ฌ๊ทํจ์๋ฅผ ํธ์ถํ์ฌ len(array) <= 1 ์ผ๋๊น์ง ๋ฐ๋ณตํ๊ณ ์ ์ฒด ๋ฆฌ์คํธ ๋ฐํ
๋ณํฉ ์ ๋ ฌ (merge sort)
- ๋ฐ์ดํฐ๋ฅผ ๋ ์ด์ ๋๋ ์ ์์ ๋๊น์ง ๋๋๊ณ , ๋ค์ ๋ณํฉํ๋ฉฐ ์ ๋ ฌํ๋ ๋ฐฉ๋ฒ์ด๋ค. (๋ณํฉ ํ ๋ ์ ๋ ฌ์คํ)
- ๋ฐ์ดํฐ๋ฅผ ๋๋ ๋ ์ ์ฐจ ๋ฐ์ฉ ์ค์ด๋๋ฏ๋ก O(logN), ๋ณํฉ ํ ๋ ๋ชจ๋ ๊ฐ์ ๋น๊ต ํด์ผํ๋ฏ๋ก O(N)์ด๋ฏ๋ก ์ด O(NlogN)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.
def merge_sort(array):
if len(array) <= 1:
return array
mid = len(array) // 2
left_array = array[:mid]
right_array = array[mid:]
left_array = merge_sort(left_array)
right_array = merge_sort(right_array)
return merge(left_array, right_array)
def merge(left, right):
result = []
while ( len(left) > 0 or len(right) > 0 ):
if ( len(left) > 0 and len(right) > 0 ):
if ( left[0] <= right[0] ):
result.append(left[0])
left = left[1:]
else:
result.append(right[0])
right = right[1:]
elif len(left) > 0:
result.append(left[0])
left = left[1:]
elif len(right) > 0:
result.append(right[0])
right = right[1:]
return result
'์ฝ๋ฉํ ์คํธ > ๊ธฐ๋ณธ ์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
์์ฐจํ์(Sequential_Search) (0) | 2022.02.20 |
---|---|
์ด์งํ์(Binary_Search) (0) | 2022.02.20 |
๊น์ด ์ฐ์ ํ์(DFS) (0) | 2022.02.20 |
๋๋น ์ฐ์ ํ์(BFS) (0) | 2022.02.20 |
์ ๋ ฌ ์ฝ๋1(๊ณ์ ์ ๋ ฌ, ์ฝ์ ์ ๋ ฌ, ์ ํ ์ ๋ ฌ) (0) | 2022.01.10 |