๐ ํต ์ ๋ ฌ์ด๋?
- ๊ธฐ์ค์ (pivot ์ด๋ผ๊ณ ๋ถ๋ฆ)์ ์ ํด์, ๊ธฐ์ค์ ๋ณด๋ค ์์ ๋ฐ์ดํฐ๋ ์ผ์ชฝ(left), ํฐ ๋ฐ์ดํฐ๋ ์ค๋ฅธ์ชฝ(right) ์ผ๋ก ๋ชจ์ผ๋ ํจ์๋ฅผ ์์ฑํจ
- ๊ฐ ์ผ์ชฝ(left), ์ค๋ฅธ์ชฝ(right)์ ์ฌ๊ท์ฉ๋ฒ์ ์ฌ์ฉํด์ ๋ค์ ๋์ผ ํจ์๋ฅผ ํธ์ถํ์ฌ ์ ์์
์ ๋ฐ๋ณตํจ
- ํจ์๋ ์ผ์ชฝ(left) + ๊ธฐ์ค์ (pivot) + ์ค๋ฅธ์ชฝ(right) ์ ๋ฆฌํดํจ
๐ ํต ์ ๋ ฌ ๊ตฌํํ๊ธฐ
๐๊ทธ๋ฆผ์ผ๋ก ๊ณผ์ ์ดํดํ๊ธฐ
โ
Code
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)
- ํ์ด์ฌ list comprehension์ ์ฌ์ฉํ๋ฉด ๋ค์๊ณผ ๊ฐ์ด ๊ตฌํํ ์ ์๋ค.
def qsort(data):
if len(data) <= 1:
return data
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(left) + [pivot] + qsort(right)
๐ ์ดํด๊ฐ ์ ์๋๋ค๋ฉด ์ฌ๊ธฐ๋ฅผ ํด๋ฆญ
๐ ์๊ฐ ๋ณต์ก๋
- ํต ์ ๋ ฌ์ ์๊ฐ ๋ณต์ก๋๋ O(nlogn)
- ๋จ, ์ต์
์ ๊ฒฝ์ฐ(๋งจ ์ฒ์ pivot์ด ๊ฐ์ฅ ํฌ๊ฑฐ๋, ๊ฐ์ฅ ์์์ ๋ชจ๋ ๋ฐ์ดํฐ๋ฅผ ๋น๊ตํ๋ ์ํฉ)์๋ O(n2)