Quick Sort

Quick sort는 기준 데이터인 pivot 을 설정하고, pivot보다 작은 값과 pivot보다 큰 값의 위치를 교환하고, 두 개의 포인터가 어긋나는 시점에 왼쪽에 위치한 포인터를 pivot과 교환해줌으로서, pivot의 왼쪽에는 pivot보다 작은 값들만 , pivot의 오른쪽에는 pivot보다 큰 값들만 위치하도록 한다. pivot의 왼쪽, 오른쪽 부분의 배열에 대해서 다시 재귀적으로 정렬을 수행하는 정렬 알고리즘이다.

퀵소트 알고리즘은 분할정복(divide & conquer) 알고리즘에 속한다.

퀵소트 알고리즘에도 pivot을 어떻게 잡는 지에 대한 다양한 방법이 있지만, 가장 대표적인 호어 분할 방식으로 pivot을 잡으면 list에서 첫번째 데이터를 pivot으로 잡는다.

알고리즘은 다음과 같은 단계로 이루어진다.

1. pivot 설정
2. 왼쪽 pointer에서는 pivot보다 큰 값을 찾고, 오른쪽 pointer 에서는 pivot보다 작은 값을 찾는다.
3. 만약 두 pointer 의 위치가 어긋나면 왼쪽에 위치한 pointer와 ( 더 작은 데이터 ) pivot 의 값을 교환한다.
   • 3번 과정 이후에, pivot 을 기준으로 왼쪽, 오른쪽에 대해 다시 1번 과정을 재귀적으로 수행한다.
4. 그렇지 않다면 두 pointer간의 값을 교환한다.

파이썬으로 구현한 퀵소트는 다음과 같다.

def quickSort(arr,lt,rt):
    ## 배열의 원소가 하나 남으면 이미 정렬된 상태로 간주하고 종료한다.
    if(lt>=rt):
        return;
    # pivot값을 설정한다.
    pivot = arr[lt];
    left = lt+1;
    right= rt;
    while left<=right:
        # 왼쪽에서부터 pivot값보다 작거나 같은 값을 찾는다. 
        while  left<=rt and arr[left] <= pivot:
            left+=1;
        # 오른쪽에서부터 pivot값보다 큰 값을 찾는다.
        while  arr[right] > pivot:
            right-=1;
        # 두 포인터가 엇갈리지 않았으면 교환한다
        if(left>right):
            arr[right] , arr[lt] = arr[lt], arr[right];
        # 엇갈렸다면 왼쪽에 위치한 포인터, 작은값과 pivot을 교환한다.
        else:
            arr[left] , arr[right] = arr[right], arr[left]
    ## pivot을 기준으로 정렬된 두 파티션을 재귀적으로 다시 정렬을 수행한다. 
    quickSort(arr,lt,right-1);
    quickSort(arr,right+1,rt);

if __name__ =="__main__":
    array = [2,4,5,7,8,22,1,41,2,33,232,13];
    quickSort(array,0,len(array)-1);   
    print(array)

자바로 구현한 quick sort는 다음과 같다.

import java.util.Arrays;
public class QuickSort {

    public static void quickSort(int[] arr, int lt, int rt ){
        if(lt>=rt){
            return;
        }
        int pivot = partition(arr, lt, rt);
        quickSort(arr, lt,pivot-1);
        quickSort(arr,pivot+1, rt);
    }

    private static int partition(int[] arr, int lt, int rt) {
        int pivotIndex = lt;
        int pivot = arr[lt++];

        while(lt <= rt){
            while (lt <= rt && arr[lt] <= pivot ){
                lt++;
            }
            while (arr[rt] > pivot){
                rt--;
            }
            if(lt < rt){
                swap(arr,lt, rt);
            }else{
                swap(arr,rt,pivotIndex);
            }
        }
        return rt;
    }

    private static void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {2,4,5,1,32,2,4,21,1,3,232,13};
        System.out.println("before sorting :" + Arrays.toString(arr));
        quickSort(arr,0,arr.length-1);
        System.out.println("after sorting :" + Arrays.toString(arr));
    }
}

시간,공간복잡도

퀵소트의 시간복잡도는 평균경우가 O(NlogN), 최악의 경우가 O(N^2)이다. (최악의 경우는 pivot이 매번 가장 작거나, 가장 클 경우로 사실 상 확률이 매우 적다. )

공간복잡도는 O(1)으로 merge sort (O(N))보다는 효율적인 공간복잡도를 가지고 있다.

Reference

• 퀵소트 설명사진: https://www.w3resource.com/csharp-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-9.php