정렬 3
정렬 3(퀵정렬)
출처 : (이코테 2021 강의 몰아보기) 4. 정렬 알고리즘
https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4
퀵정렬
기준 데이터(피봇)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나
가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정
퀵 정렬은 평균의 경우 O(NlogN)의 시간 복잡도를 가짐
최악의 경우 O(N^2)의 시간 복잡도를 가짐 EX) 이미 정렬된 배열에 대해 첫 번째 원소를 피벗으로 삼을 때
코드
#퀵 정렬 1
array=[5,7,9,0,3,1,6,2,4,8]
def quick_sort(array,start,end):
if start>=end:
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)
#퀵정렬 2
array=[5,7,9,0,3,1,6,2,4,8]
def quick_sort2(array):
if len(array)<=1:
return array
pivot=array[0]
tail=array[1:]
left_side=[x for x in tail if x<=pivot]
right_side=[x for x in tail if x>pivot]
return quick_sort2(left_side)+[pivot]+quick_sort2(right_side)
print(quick_sort2(array))
