Quick Sort

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

퀵 정렬 동작

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

   ->
[5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
							<-
                            

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

      ->
[5, 4, 9, 0, 3, 1, 6, 2, 7, 8]
					  <-   

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

                  ->
[5, 4, 2, 0, 3, 1, 6, 9, 7, 8]
			    <-                       

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

                  
[1, 4, 2, 0, 3] [5] [6, 9, 7, 8]
			                                                              

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

    ->               
[1, 4, 2, 0, 3] 
          <-
         

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

    ->               
[6, 9, 7, 8]
<-          

• 이상적인 겨우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN)을 기대할 수 있다.
• 너비 * 높이 = N logN = NlogN

퀵 정렬의 시간 복잡도

• 퀵 정렬은 평균의 경우 O(NlogN)의 시간 복잡도를 가진다.
• 하지만 최악의 경우 O(N2)의 시간 복잡도를 가진다.
  -> 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에 대해서 퀵 정렬을 수행하는 경우

퀵 정렬의 구현

1. 일반적인 방식

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
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        #left는 "오른쪽 끝까지 가도 괜찮아. 다 검사하고 나서 범위 벗어나면 while에서 걸러줄게."
        #right는 "왼쪽 끝(피벗 자리)은 내 구역 아냐. 그 자리는 피벗 고정이니까 그 앞까지만 검사해."
        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)


nums = [5, 7, 9, 0, 3, 1, 6 , 2, 4]
quick_sort(nums, 0, len(nums) - 1)
print(nums)

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)


nums = [5, 7, 9, 0, 3, 1, 6 , 2, 4]
print(quick_sort(quick_sort(nums)))