[Python3] QuickSort (퀵 정렬)
2018. 8. 3. 02:16 |
프로그래밍/기타
공부하다가 Python으로 퀵 정렬을 구현해 보았다. 단점은 이미 정렬된 상태에서 이렇게 양 극값을 Pivot으로 선택하는 경우 시간이 O(n^2) 소요된다는거...
#!/usr/bin/env python3
def quick_sort(arr, start, end):
if start >= end:
return arr
pivot = start
left = start + 1
right = end
while True:
while left <= right and arr[left] <= arr[pivot]:
left += 1
while left <= right and arr[pivot] <= arr[right]:
right -= 1
if left > right:
arr[pivot], arr[right] = arr[right], arr[pivot]
pivot = right
break
arr[left], arr[right] = arr[right], arr[left]
quick_sort(arr, start, pivot-1)
quick_sort(arr, pivot+1, end)
return arr
# 테스트 출력 코드
from random import shuffle
test_case = list(range(1, 101))
shuffle(test_case)
print('Before Sort :\n', test_case)
quick_sort(test_case, 0, 99)
print('After Sort :\n', test_case)
'프로그래밍 > 기타' 카테고리의 다른 글
| [Python3] 카카오 코드 페스티벌 2018 예선 - 인형들 (0) | 2019.01.18 |
|---|---|
| python-ldap Windows Active Directory unicodePwd userAccountControl DSID-031A120C (0) | 2018.12.20 |
| 티스토리 블로그 SSL(TLS) www <-> non-www 상호 전환 Javascript (7) | 2018.09.08 |
| [Python3] Permutation (순열) (2) | 2018.08.04 |
| [카카오][Python3] 리틀 프렌즈 사천성 (1) | 2018.08.02 |
| [카카오][Python3] 단체사진 찍기 (0) | 2018.08.01 |
| [Python3] Merge Sort (병합 정렬) (0) | 2018.07.14 |
| Flask에서 No-Cache 헤더 설정 (0) | 2018.05.29 |
최근에 달린 댓글 최근에 달린 댓글