출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬
퀵정렬이란
병합정렬과 함께 가장 빠른 정렬방법 중 하나. 대부분 프로그래밍 언어에서 정렬라이브러리로 사용.
기준(피벗)을 설정하고 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식이다.
피벗: 큰숫자와 작은 숫자를 교환할 때 교환하기 위한 기준.
가장 대표적인 방식인 호어 분할(리스트의 첫번째 데이터를 피벗으로 정한다.) 사용.
피벗을 설정한 뒤
왼쪽에서 피벗보다 큰 데이터를 찾고, 오른쪽에서는 피벗보다 작은 데이터를 찾는다.
그 후 서로 데이터위치 변경
만약 두값의 위치가 서로 엇갈리면 작은 데이터와 피벗의 위치 서로 변경
그 후 피벗의 왼쪽에 피벗보다 작은 데이터가 위치하고 피벗의 오른쪽에 피벗보다 큰데이터가 위치하는 작업인 파티션(분할)이 완료된다.
그다음부터 분리된 왼쪽리스트와 오른쪽 리스트에 대해서 개별적으로 퀵정렬을 진행한다.
퀵정렬이 끝나는 조건은 리스트의 개수가 1개이하일 경우이다.
1. 재귀를 이용한 방식
array=[5,7,9,0,3,1,6,2,4,8]
def quick_sort(array,start,end):
#원소가 1개면 종료한다.
if start>=end:
return
pivot=start
left=start+1# 왼쪽 데이터 시작인덱스
right=end #오른쪽 데이터 시작인덱스
#인덱스 길이를 벗어나지 않으면서 피벗보다 큰데이터를 찾을 때 까지
while left<=right:
while left<=end and array[pivot]>=array[left]:
left+=1
#피벗보다 작은데이터 찾기
while right >start and array[pivot] <= array[right]:
right -= 1
#엇갈렸을 경우 피벗과 가장작은 데이터 교환
if left>right:
array[pivot],array[right]=array[right],array[pivot]
else:
array[right], array[left] = array[left], array[right]
#마지막에 right랑 피벗이랑 바꾸니까 right-1이 피벗보다 작은데이터가 된다.
quick_sort(array,start,right-1)
quick_sort(array, right+1,end)
quick_sort(array,0,len(array)-1)
print(array)
2. 더 쉽게 쓰기
이 코드 같은 경우는 기존의 퀵정렬과는 다르게
호어분할은 똑같으나 피벗을 기준으로 파티션 작업만 하고
왼쪽과 오른쪽을 바꿔 넣는 작업은 하지 않는다.
한번에 분할만 계속해서 피벗을 가운데에 끼어넣고 정렬하는 방식이다.
좀 더 기억하기가 쉽다.
def quick_sort(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_sort(left_side) +[pivot]+quick_sort(right_side)
print(quick_sort(array))
