[정렬 알고리즘] 퀵 정렬(Quick Sort)

http://www.xybernetics.com/techtalk/SortingAlgorithmsExplained/SortingAlgorithmsExplained.html

퀵 정렬이란?

퀵 정렬이란 분할 정복(Divide and Conquer) 방법을 사용하여 구현된 정렬 알고리즘을 의미한다. JAVA의 Arrays.sort()도 내부적으로 피벗을 하나가 아닌 두 개 사용하여 배열을 세 부분으로 나눈 Dual-Pivot QuickSort를 사용한다.

 

퀵 정렬은 분할 알고리즘을 무엇으로 사용하느냐, 그리고 피봇 설정을 무엇으로 하느냐에 따라 효율이 크게 달라진다.
분할 방법은 Hoare(호어), Lomuto(로무토) 방법이 존재하고, Pivot 설정은 랜덤 피봇, 중앙값 피봇, 이중 피봇, 하이브리드 피봇 등 다양한 방식이 있지만 가장 단순한 형태는 인덱스를 배열의 한 부분으로 고정시킨 고정값 피봇이다.(보통 첫 번째 값, 마지막 값, 혹은 가운데 인덱스를 고정)

 

[이것이 코딩 테스트다 with Python] 23강 퀵 정렬에서 Hoare방식의 퀵 정렬을 쉽게 알 수 있다.

분할 정복(Divide and Conquer)이란?

Divide and Conquer 과정

분할 정복이란 큰 문제를 작은 문제로 나누어서 해결하는 알고리즘을 의미한다. 분할 → 정복 → 결합의 단계로 처리된다.

1. 분할 단계에서는 문제를 작은 부분 문제들로 나누는 단계이다.
2. 정복 단계에서는 부분 문제를 해결하는 단계이다
3. 결합 단계에서는 부분 문제의 해들을 모아 원래의 문제의 해를 구하는 방식을 의미한다.

퀵 정렬은 합병과정이 없다.

Hoare(호어) VS Lomuto(로무토)

ChatGPT

Pivot 설정

1. 랜덤 피봇(Random Pivot): 배열에서 임의의 값을 피벗으로 선택하여 정렬하는 방식.(랜덤 피봇을 사용하면 최악의 경우를 방지할 수 있다.)
2. 중앙값 피봇(Median Pivot): 배열의 특정 원소(예: 첫 번째, 마지막, 중간 값 중 중앙값)를 피벗으로 선택하는 방식.
3. 이중 피봇(Dual Pivot): 두 개의 피벗을 사용하여 세 개의 부분으로 나누는 방식
4. 하이브리드 피봇(Hybrid Pivot): 상황에 따라 다른 피벗 전략을 혼합하여 사용하는 방식
5. 고정값 피봇: 배열의 한 부분을 고정시키는 방식

고정된 인덱스 피봇 (가운데 인덱스 고정) vs. 중앙값 피봇

고정된 인덱스 피벗의 가운데 인덱스 선택 방법과 중앙값 피벗 설정 방법의 차이점이 헷갈려 GPT에 물어보았다.

ChatGPT

Hoare 분할 방식

1. 피봇 값보다 큰 값들은 오른쪽, 작은 값들은 왼쪽 집합에 위치시킨다.(아래에서 i와 j가 교차했을 때가 이것이 완성된 때)
2. 피봇 값을 두 집합의 가운데에 위치시킨다.(아래서 i와 j가 교차했을 때 피봇의 값과 j의 위치와 swap해주는 것)
3. 대부분의 강의나 교육자료에서 Hoare 분할 방식을 사용한다.

초기상태

 

슈도코드

 

정렬 완료

Lomuto 분할 방식

1. 피봇 값보다 큰 값들은 오른쪽, 작은 값들은 왼쪽 집합에 위치시킨다.
2. 피봇 값을 두 집합의 가운데에 위치시킨다.(아래에서 j가 끝까지 진행되었고, i+1와 피폿값이 swap 될 때 이것이 완성된 때)

* Hoare 방식과 가장 큰 차이점은 i와 j가 모두 증가하는 방식이라는 것이다.

초기상태

슈도코드

정렬 완료

퀵 정렬 장점과 단점

장점	평균적으로 가장 빠른 정렬 알고리즘 중 하나
	추가 메모리 공간이 거의 필요 없음 (인플레이스 정렬)
	캐시 친화적 (Cache-Friendly)
	평균적으로 힙 정렬보다 교환 횟수가 적음
단점	피벗을 제대로 선택하지 않으면 최악의 경우 O(n²)까지 느려질 수 있음.
	안정 정렬이 아님 (Unstable Sort)
	구현이 상대적으로 복잡
	작은 데이터셋에서는 삽입 정렬보다 느림

 

시간 복잡도

알고리즘	Best	Avg	Worst	Run-time(정수 60,000개) 단위: sec
삽입정렬	O(n)	O(n²)	O(n²)	7.438
선택정렬	O(n²)	O(n²)	O(n²)	10.842
버블정렬	O(n²)	O(n²)	O(n²)	22.894
셸 정렬	O(n)	O(n¹·⁵)	O(n²)	0.056
퀵 정렬	O(nlogn)	O(nlogn)	O(n²)	0.014
힙 정렬	O(nlogn)	O(nlogn)	O(nlogn)	0.034
병합 정렬	O(nlogn)	O(nlogn)	O(nlogn)	0.026

 

퀵 정렬 알고리즘 구현

// 분할 방법: Lomuto(로무토) 분할 방식
// 피벗 설정 방법: 고정된 인덱스 피벗 (마지막 원소 선택)

public void quickSort(int[] arr, int left, int right) {
    // base condition
    if (left >= right) {
        return;
    }
    int pivot = arr[right];
    
    int sortedIndex = left;
    for (int i = left; i < right; i++) {
        if (arr[i] <= pivot) {
            // swap(arr, i, sortedIndex);
            int tmp = arr[i];
            arr[i] = arr[sortedIndex];
            arr[sortedIndex] = tmp;
            sortedIndex++;
        }
    }
    // swap(arr, sortedIndex, right);
    int tmp = arr[sortedIndex];
    arr[sortedIndex] = arr[right];
    arr[right] = tmp;
    
    quickSort(arr, left, sortedIndex - 1);
    quickSort(arr, sortedIndex + 1, right);
}

 

// 분할 방법: Lomuto(로무토) 분할 방식
// 피벗 설정 방법: 고정된 인덱스 피벗 (마지막 원소 선택)

import java.util.Arrays;

class GfG {

    // Partition function
    static int partition(int[] arr, int low, int high) {
        
        // Choose the pivot
        int pivot = arr[high];
        
        // Index of smaller element and indicates 
        // the right position of pivot found so far
        int i = low - 1;

        // Traverse arr[low..high] and move all smaller
        // elements to the left side. Elements from low to 
        // i are smaller after every iteration
        for (int j = low; j <= high - 1; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        
        // Move pivot after smaller elements and
        // return its position
        swap(arr, i + 1, high);  
        return i + 1;
    }

    // Swap function
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // The QuickSort function implementation
    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            
            // pi is the partition return index of pivot
            int pi = partition(arr, low, high);

            // Recursion calls for smaller elements
            // and greater or equals elements
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        int n = arr.length;
      
        quickSort(arr, 0, n - 1);
        
        for (int val : arr) {
            System.out.print(val + " ");  
        }
    }
}

//출력
//Sorted Array
//1 5 7 8 9 10

참고자료

[1] geeksforgeeks - Quick Sort

[2] 위키백과 - 퀵정렬

[3] 티스토리 Contributor9 - [Java/알고리즘] 정렬 알고리즘(Sort Algorithm) 이해하기 -1 : 기본 구조 및 종류

[4] 데굴데굴 개발자의 기록:티스토리 - [알고리즘/JAVA] 정렬 알고리즘 : 선택, 삽입, 버블, 병합, 퀵 정렬

[5] 티스토리 Storage Gonie - 퀵 정렬(Quick Sort)

[6] Youtube 채널 YunHee Kang - Quick sort-Lomuto