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

목차

 

퀵 정렬이란?

퀵 정렬은 분할 정복 (Divide and Conquer)과 재귀 방식을 이용한 정렬 알고리즘이다. 분할 정복이란 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 방식이다. 

 

퀵 정렬에서는 pivot이라는 기준을 하나 정하고, 왼쪽은 기준보다 작은 값, 그리고 더 큰 값은 기준 오른쪽으로 옮기면서 배열을 둘로 분할한 후 정렬한다. 보통 pivot은 맨 앞이나 맨 뒤, 혹은 중간에 위치한 값을 선택한다.

 

퀵 정렬 과정

1. 배열 맨 앞에 있는 수를 pivot으로 설정한다. 그리고 배열의 길이가 n일 때, 배열의 시작점은 0이 되고 도착점은 n - 1이 된다.
2. pivot 값을 기준으로 시작점에서부터 검사해서 큰 값을, 도착점에서부터 작은 값을 찾는다.
3. 두 값을 바꾸고, 같은 과정을 수행한다
4. 큰 값의 index와 작은 값의 index가 교차하는 경우, 작은 값과 pivot 값을 바꾼다. 이렇게 하면 pivot 값을 기준으로 왼쪽은 pivot보다 작은 값들, 오른쪽은 큰 값들로 분할된다
5. 분할된 영역에서 맨 앞에 있는 수를 pivot으로 설정하고 같은 과정을 수행한다

 

이제 퀵 정렬 예시를 한번 살펴보겠다.

 

 

 

소스 코드

 

import java.io.*;
import java.util.*;
public class Main {
   static int number = 10;  //데이터의 개수
   static int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};  //정렬할 배열

   public static void main(String[] args) throws IOException {
       quickSort(arr, 0, number - 1);
   }

   static void quickSort(int[] arr, int start, int end) {
       if (start >= end) {
           return;  //원소가 1개인 경우
       }

       int pivot = start;  //pivot값은 첫번째 원소
       int i = start + 1;  //시작점 - 왼쪽부터 큰 값을 찾을 때 시작하는 인덱스
       int j = end;  //도착점 - 오른쪽부터 작은 값을 찾을 때 시작하는 인덱스
       int temp;  //수를 바꿀 때 사용하는 임시 변수

       while (i <= j) { // 엇갈릴 때까지 반복
           while (arr[i] <= arr[pivot]) { //pivot보다 더 큰 값을 만날 때까지
               i++;
           }
           while (arr[j] >= arr[pivot] && j > start) { //pivot보다 더 작은 값을 만날 때까지
               j--;
           }
           if (i > j) { //현재 엇갈린 상태면 pivot값과 교체
               temp = arr[j];
               arr[j] = arr[pivot];
               arr[pivot] = temp;
           } else { //엇갈리지 않았다면 i와 j를 교체
               temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
           }
      }

       //분할된 왼쪽과 오른쪽 둘다 퀵 정렬 수행
       quickSort(arr, start, j - 1);
       quickSort(arr, j + 1, end);
   }
}

 

만약에 내림차순으로 정렬을 한다고 할 때는 다음만 바꿔주기만 하면 된다.

 

while (arr[i] >= arr[pivot]) { //pivot보다 더 큰 값을 만날 때까지
    i++;
}
while (arr[j] <= arr[pivot] && j > start) { //pivot보다 더 작은 값을 만날 때까지
    j--;
}

 

퀵 정렬 (내림차순)

 

import java.io.*;
import java.util.*;
public class Main {
    static int number = 10;  //데이터의 개수
    static int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};  //정렬할 배열

    public static void main(String[] args) throws IOException {
        quickSort(arr, 0, number - 1);
    }

    static void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;  //원소가 1개인 경우
        }

        int pivot = start;  //pivot값은 첫번째 원소
        int i = start + 1;  //시작점 - 왼쪽부터 큰 값을 찾을 때 시작하는 인덱스
        int j = end;  //도착점 - 오른쪽부터 작은 값을 찾을 때 시작하는 인덱스
        int temp;  //수를 바꿀 때 임시 변수

        while (i <= j) { // 엇갈릴 때까지 반복
            while (arr[i] >= arr[pivot]) { //pivot보다 더 큰 값을 만날 때까지
                i++;
            }
            while (arr[j] <= arr[pivot] && j > start) { //pivot보다 더 작은 값을 만날 때까지
                j--;
            }
            if (i > j) { //현재 엇갈린 상태면 pivot값과 교체
                temp = arr[j];
                arr[j] = arr[pivot];
                arr[pivot] = temp;
            } else { //엇갈리지 않았다면 i와 j를 교체
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
       }

        //분할된 왼쪽과 오른쪽 둘다 퀵 정렬 수행
        quickSort(arr, start, j - 1);
        quickSort(arr, j + 1, end);
    }
}

 

 

퀵 정렬 시간 복잡도

 

퀵 정렬의 성능은 어떻게 pivot 값을 선택하느냐에 따라 크게 달라질 수 있다. pivot 값을 기준으로 동일한 개수의 작은 값들과 큰 값들이 분할되면 O(NlogN)의 시간 복잡도를 가지게 된다.

 

하지만, pivot 값을 기준으로 분할했을 때 값들이 한 편으로 크게 치우치게 되면, 퀵 정렬의 성능은 저하되고, 한편으로만 모든 값이 몰리면 O(N^2)의 시간 복잡도를 가지게 된다. 추가로 이미 배열이 정렬되어 있고 pivot이 항상 그 배열의 최솟값 혹은 최댓값인 경우에는 최악의 시간 복잡도를 가진다. 이때, 분할이 N만큼 진행되다 보니 최악의 시간 복잡도는 O(N^2)이 된다.

 

 

이 그래프에서 볼 수 있듯이 자료의 개수 N이 많아질수록 O(N log N)의 시간 복잡도를 가지고 있는 퀵 정렬은 다른 정렬 알고리즘보다 훨씬 더 효율적이다.

 

 

 

퀵 정렬의 장단점

장점

• O(NlogN)의 시간 복잡도를 가지므로 다른 정렬 알고리즘보다 빠르다
• 정렬하고자 하는 배열 안에서 교환하는 방식(in-place)이므로, 다른 메모리 공간을 필요로 하지 않는다

 

단점

• 불안정 정렬(Unstable Sort)이다
  
• 정렬된 배열에 대해서는 Quick sort의 불균형 분할에 의해 오히려 수행 시간이 더 많이 걸린다