2021. 9. 9. 08:02ใ์ฝ๋ฉ ํ ์คํธ ์ค๋น/์๊ณ ๋ฆฌ์ฆ
์๋ ํ์ธ์? ์ฃผ๋ํ๋ ์ ๋๋ค.
์ค๋์ ์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ์ ์๋ฃ๊ตฌ์กฐ์์ ํต ์ ๋ ฌ์ ๋ํด ๊ณต๋ถ ํด ๋ณด๋๋ก ํ๋ ๊ฒ์ด์์.
์์ค ์ฝ๋์ ๋ํด์ ํ์ธ ํ๊ณ ์ถ์ผ์ ๋ถ๋ค๊ป์๋ ์ฃผ๋ํ๋์ Git hub์ ๊ด์ฌ์ ์ฃผ์ธ์!
๐ Quick Sort(ํต ์ ๋ ฌ)์ด๋?
์ด๊ฒ์ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ๊ฝ์ธ ๊ฒ์ด์์!
์ด๋ฆ ๊ทธ๋๋ก ๋น ๋ฅด๊ธฐ ๋๋ฌธ์ธ ๊ฒ์ด์์.
ํต ์ ๋ ฌ์ ๊ธฐ์ค์ (pivot)์ ์ ํด์, ๊ธฐ์ค์ ๋ณด๋ค ์์ Data๋ ์ผ์ชฝ(left)์ ๊ทธ๋ณด๋ค ํฐ Data๋ ์ค๋ฅธ์ชฝ(right)๋ก ๋ชจ์ผ๋ ํจ์๋ฅผ ์์ฑํ๋ ๊ฒ์ด์์.
๊ฐ ์ผ์ชฝ, ์ค๋ฅธ์ชฝ์ ์ฌ๊ท์ฉ๋ฒ์ ํ์ฉํ์ฌ ๋ค์ ๋์ผ ํจ์๋ฅผ ํธ์ถํ ๋ค ์ ์์ ์ ๋ฐ๋ณตํ๋๋ก ํ๋ฉด ๋๋ ๊ฒ์ด์์.
๊ทธ๋ฐ ๋ค, ํจ์๋ ์ผ์ชฝ + ๊ธฐ์ค์ + ์ค๋ฅธ์ชฝ์ ํ ๋ค ๋ฐํํ๋ฉด ๋๋ ๊ฒ์ด์์.
import random
def qsort(data):
if len(data) <= 1:
return data
left, right = list(), list()
pivot = data[0]
for index in range(1, len(data)):
if pivot > data[index]:
left.append(data[index])
else:
right.append(data[index])
return qsort(left) + [pivot] + qsort(right)
def qsort_list_comprehension(data):
if len(data) <= 1:
return data
left, right = list(), list()
pivot = data[0]
left = [item for item in data[1:] if pivot > item]
right = [item for item in data[1:] if pivot <= item]
return qsort_list_comprehension(left) + [pivot] + qsort_list_comprehension(right)
data_list = random.sample(range(100), 10)
print(qsort(data_list))
print("=" * 1000)
data_list = random.sample(range(100), 10)
print(qsort_list_comprehension(data_list))
print("=" * 1000)
๐ ์๊ณ ๋ฆฌ์ฆ ๋ถ์
๋ณํฉ ์ ๋ ฌ๊ณผ ์ ์ฌํ ์ด ์น๊ตฌ์ ์๊ฐ ๋ณต์ก๋๋ O($n log n$)์ธ ๊ฒ์ด์์.
ํ์ง๋ง, ์ต์ ์ ๊ฒฝ์ฐ์ ๋งจ ์ฒ์ pivot์ด ๊ฐ์ฅ ํฌ๊ฑฐ๋, ๊ฐ์ฅ ์์๋ฒ๋ฆฌ๋ฉด ๋ฌธ์ ๊ฐ ๋์ด ๋ฒ๋ฆฌ๋ ๊ฒ์ด์์.
์ด๋ ๊ฒ ๋์ด ๋ฒ๋ฆฌ๋ฉด ๋ชจ๋ Data๋ฅผ ๋น๊ตํด์ผ ํ๋ ํผ๊ณคํ ์ํฉ์ด ๋ฐ์ํ๋ฉฐ, ์ด ๋, ์๊ฐ ๋ณต์ก๋๋ O($n^2$)์ด ๋๋ ๊ฒ์ด์์.
'์ฝ๋ฉ ํ ์คํธ ์ค๋น > ์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๊ณ ๋ฆฌ์ฆ] ์์ฐจ ํ์ (0) | 2021.09.19 |
---|---|
[์๊ณ ๋ฆฌ์ฆ] ์ด์ง ํ์ ๊ธฐ๋ฒ (0) | 2021.09.17 |
[์๊ณ ๋ฆฌ์ฆ] ๋ณํฉ ์ ๋ ฌ (merge sort) (0) | 2021.09.09 |
[์๊ณ ๋ฆฌ์ฆ] Dynamic Programming(๋์ ๊ณํ๋ฒ)& Divide and Conquer(๋ถํ ์ ๋ณต) (0) | 2021.09.09 |
[์๊ณ ๋ฆฌ์ฆ] 02. ์ ํ ์ ๋ ฌ (0) | 2021.09.08 |