[알고리즘] 퀵 정렬

퀵 정렬이란 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나 이고, 평균적인 상황에서 최고의 성능을 낸다. 

퀵 정렬의 특징

• 분할 정복 알고리즘이다.
• 최악 시간복잡도 O(n²), 평균 시간복잡도 O(n log n) 
• 퀵정렬은 불안정 정렬에 속하며 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다.

퀵 정렬 알고리즘

리스트에서 적절한 피벗(원소) 하나를 고르고, 피벗 앞에는 피벗보다 작은 값들이 오게 하고, 피벗 뒤에는 피벗보다 큰 값들이 오게 한다. 작업이 완료되면 피벗을 기준으로 두 개의 리스트가 생기는데, 각각 리스트에도 이전에 했던 과정을 재귀적으로 반복해준다. 리스트가 더 이상 나누어지지 않는다면, 재귀반환하면서 여러 개의 정렬된 리스트를 하나의 리스트로 결합해준다.

 

퀵 정렬 시간 복잡도

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

퀵 정렬 소스 (JAVA)

import java.util.Arrays;

public class QuickSort {

/*
 오름차순으로 정렬한 퀵 정렬 예제
*/
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        Integer arr[] = {5, 1, 8, 4, 0, 9, 2, 3, 7, 6};
        quickSort.quickSort(arr, 0, arr.length - 1);
        
        System.out.println(Arrays.toString(arr));

    }

    public void quickSort(Integer[] arr, int s, int e) { 
            int mid = partition(arr, s, e);
            if (s < mid - 1)
                quickSort(arr, s, mid - 1);
            if(mid < e)
                quickSort(arr, mid, e);
    }

    public int partition(Integer[] arr, int s, int e) {
        int pivot = arr[(s + e) / 2];

        while (s <= e) {
            while(pivot > arr[s]) s++;
            while(pivot < arr[e]) e--;
            
            if(s <= e){
                swap(arr, s, e);
                s++;
                e--;
            }
        }

        return s;
    }

    public void swap(Integer arr[], int s, int e){
        int temp = arr[s];
        arr[s] = arr[e];
        arr[e] = temp;
    }
}

---

퀵 정렬을 자세히 설명해주는 동영상 (추천!)

https://www.youtube.com/watch?v=7BDzle2n47c