forked from ndb796/python-for-coding-test
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path4.py
More file actions
25 lines (23 loc) ยท 1.04 KB
/
4.py
File metadata and controls
25 lines (23 loc) ยท 1.04 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
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): # ์๊ฐ๋ ธ๋ค๋ฉด ์์ ๋ฐ์ดํฐ์ ํผ๋ฒ์ ๊ต์ฒด
array[right], array[pivot] = array[pivot], array[right]
else: # ์๊ฐ๋ฆฌ์ง ์์๋ค๋ฉด ์์ ๋ฐ์ดํฐ์ ํฐ ๋ฐ์ดํฐ๋ฅผ ๊ต์ฒด
array[left], array[right] = array[right], array[left]
# ๋ถํ ์ดํ ์ผ์ชฝ ๋ถ๋ถ๊ณผ ์ค๋ฅธ์ชฝ ๋ถ๋ถ์์ ๊ฐ๊ฐ ์ ๋ ฌ ์ํ
quick_sort(array, start, right - 1)
quick_sort(array, right + 1, end)
quick_sort(array, 0, len(array) - 1)
print(array)