[정렬] 이코테 QuickSort - 퀵정렬

퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나
• 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
• 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정

퀵 정렬 동작 예시

• [Step 0] 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고
  오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경함

• [Step 1] 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '9'가 선택되고
  오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '2'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경함

• [Step 2] 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '6'이 선택되고
  오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '1'이 선택된다. 단, 이처럼 위치가 엇갈리는 경우 '피벗'과
  '작은 데이터'의 위치를 서로 변경함

• [분할 완료] 이제 '5'의 왼쪽에 있는 데이터는 모두 5보다 작고, 오른쪽에 있는 데이터는 모두 '5'보다 크다는
  특징이 있다. 이렇게 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide) 또는 Partition이라고 함

• [왼쪽 데이터 묶음 정렬] 왼쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행함

[오른쪽 데이터 묶음 정렬] 오른쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행함

이러한 과정을 반복하면 전체 데이터에 대해서 정렬이 수행된다

 

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[pivot], array[right] = array[right], array[pivot]
    else:
      array[right], array[left] = array[left], array[right]
  quick_sort(array,start,right-1)
  quick_sort(array,right+1,end)

quick_sort(array,0,len(array)-1)
print(len(array)-1)
print(array)

위 과정에서 처음 index out of range가 발생하였는데

조건을

while array[left] <= array[pivot] and left <= end: 

위와 같이 바꾸었을 때, left <= end가 검증이 안된 상태에서 array[left]를 확인 하려다 보니 발생하는 문제였다.

조건문을 사용할때는 위와 같은 경우를 주의하여야 할 것 같다.