[알고리즘] 퀵 정렬 (Quick Sort, 개념과 장단점, 과정, 자바 코드 구현, 시간복잡도, 공간복잡도)

목차

• 퀵 정렬이란?
• 퀵 정렬 과정
• 퀵 정렬 구현 (자바 코드)
• 시간복잡도
• 공간복잡도
• 정렬 알고리즘 비교

 

---

1. 퀵 정렬이란?

피벗을 기준으로 왼쪽은 피벗보다 작은 값, 오른쪽은 피벗보다 큰 값을 가질 수 있도록 값을 이동시킨다. 분할과 동시에 정렬이 이뤄지며, 분할된 배열의 크기가 1이 되면 정렬이 완료된다.

 

(특징)

• 최선 및 평균 시간복잡도는 O(n log(n))이며, 최악의 시간복잡도는 O(n^2)이다.
• O(n log(n))의 시간복잡도를 가지는 병합 정렬보다 상대적으로 속도가 빠르다.
• JAVA의 Arrays.sort()에서 사용되는 정렬 알고리즘이다.

 

(장점)

• 배열 내에서 교환하는 방식(제자리 정렬)으로 추가적인 메모리 공간을 필요로 하지 않는다.
• 다른 알고리즘과 비교했을 때도 가장 빠르다.

(단점)

• 정렬된 배열에 대해서는 불균형 분할로 인해 더 오랜 시간이 소요된다.

 

---

2. 퀵 정렬 과정

1) 피벗을 지정한다.

 

2) 피벗을 기준으로 왼쪽은 작은 원소들, 오른쪽은 큰 원소들이 오도록 이동한다.

 

3) 배열의 크기가 1일 때까지, 피벗을 기준으로 왼쪽과 오른쪽 배열에 대해 (1)번 과정을 반복한다.

 

https://www.geeksforgeeks.org/implement-quicksort-with-first-element-as-pivot/

 

---

3. 퀵 정렬 구현 (자바 코드)

import java.util.*;
import java.io.*;

class Main {
    public static void main (String[] args) throws IOException {
        int[] arr = {5, 2, 2, 9, 100, 70, 11};
        int n = arr.length;

        // 오름차순 정렬
        quickSort(arr, 0, n-1);

        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivot = partition(arr, left, right);

            quickSort(arr, left, pivot - 1);
            quickSort(arr, pivot + 1, right);
        }
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];

        int lIdx = left, rIdx = right;

        while (lIdx < rIdx) {
            while (pivot < arr[rIdx]) {
                rIdx--;
            }
            while (lIdx < rIdx && arr[lIdx] <= pivot) {
                lIdx++;
            }
        }

        arr[left] = arr[lIdx];
        arr[lIdx] = pivot;

        return lIdx;
    }
}

 

---

4. 시간복잡도

데이터의 개수가 n일 때,

• 크기가 n인 배열 분할 : n/2, n/2 => n
• 크기가 n/2인 배열 분할 : n/4, n/4, n/4, n/4 => n/2 + n/2
  ...
• 크기가 1인 배열 분할 : 1 ... 1 => n/n

 

배열의 개수가 1이 될 때까지 분할하므로 log(n)번 분할한다. 또한 분할을 할 때마다 피벗을 기준으로 정렬이 이뤄지기 때문에, n번의 비교 연산이 이뤄진다.

 

따라서 log(n)번의 분할과 분할 시 n번의 비교 연산이 이뤄지기 때문에, 최적 및 평균 시간복잡도는 O(n log(n))이다.

 

만약 이미 정렬된 배열일 경우에는 분할이 n번만큼 이뤄지므로, 최악의 시간복잡도는 O(n^2)이다.

 

---

5. 공간복잡도

데이터 개수가 n일 때,

 

주어진 배열 내에서 교환이 이뤄지므로 공간복잡도는 O(n)이다.

 

---

6. 정렬 알고리즘 비교 (시간복잡도)