YEJIN LEE

“Keep turnin’ the pages”

3 minute read

퀵정렬 Quick Sort

✏️개념

  • 선택, 버블, 삽입 정렬은 모두 시간복잡도가 N^2인 알고리즘이다. 이러한 복잡도를 가지는 알고리즘은 데이터 개수가 10만 개만 넘어가도 사용하기 매우 어려워진다.

  • 퀵 정렬은 이름처럼 매우 빠른 알고리즘인데, 분할 정복 알고리즘을 사용한다. 특정한 배열이 있을 때, 배열의 원소들을 나누어 계산한다는 점에서 분할 정복 알고리즘이다.

  • 특정한 값(pivot/피벗 이라고 함)을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.

    3 7 8 1 5 9 6 10 2 4

    • 보통 가장 앞의 값을 피벗으로 선택한다.

    • 과정

          3 7 8 1 5 9 6 10 2 4        // 3을 피벗으로 두고, 왼쪽에서 오른쪽을 볼때 3보다 큰 값을 찾고(7), 오른쪽에서 왼쪽으로 볼때 3보다 작은 값을 찾는다(2)
                                  // 여기서 7과 2를 바꿔준다. 여전히 피벗값은 3이다
      3 2 8 1 5 9 6 10 7 4        // 또 피벗값을 기준으로 큰 값(8)과 작은 값(1)을 찾아 바꿔준다
      3 2 1 8 5 9 6 10 7 4        // 피벗값(3)을 기준으로 큰 값(8)과 작은 값(1)을 찾는다. 이 때, 큰 값의 인덱스가 작은 값의 인덱스보다 크다(엇갈림)
                                  // 이 상황에서는 작은 값과 피벗값을 바꾼다. 그리고 피벗값은 그 자리에 고정.
      1 2 3* 8 5 9 6 10 7 4       // 이 때, 3을 기준으로 오른쪽의 값들은 3보다 크고 3의 왼쪽 값들은 3보다 작게 된다. 
                                  // 3을 기준으로 한 번 분할 된 것이다.                          
      1 2 3* 8 5 9 6 10 7 4       // 1을 피벗값으로 두고 큰 값(2)과 작은 값을 찾는데, 작은 값이 없으므로 작은 값은 자기 자신(1)이 된다.
                                  // 또 다시 엇갈린 상황이 발생했으므로 피벗값(1)과 작은 값(1)을 바꾼 뒤 피벗값은 그 위치에 고정.
      1* 2 3* 8 5 9 6 10 7 4      // 그 다음 피벗값은 2가 되고 위와 같은 과정을 거친다.
      1* 2* 3* 8 5 9 6 10 7 4     // 그 다음 피벗값은 8이 되고, 8보다 큰 값(9), 작은 값(4)을 바꾼다
      1* 2* 3* 8 5 4 6 10 7 9     // 이렇게 과정을 반복한다
      1* 2* 3* 8 5 4 6 7 10 9
      1* 2* 3* 7 5 4 6 8* 10 9    // 피벗값은 7이 되고, 7 오른쪽에는 큰값이 없으므로 7, 작은 값은 6이 되므로 둘을 바꾸고 고정
      1* 2* 3* 6 5 4 7* 8* 10 9
      1* 2* 3* 4 5 6* 7* 8* 10 9
      1* 2* 3* 4* 5 6* 7* 8* 10 9
      1* 2* 3* 4* 5* 6* 7* 8* 10 9
      1* 2* 3* 4* 5* 6* 7* 8* 9 10*

✏️구현

    #include<iostream>
    using namespace std;

    void quickSort(int *data, int start, int end);      // 배열, 첫번째 원소 인덱스, 마지막 원소 인덱스

    int main(void){

        int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

        return 0;
    }

    void quickSort(int *data, int start, int end){

        int left, right;
        left = start; right = end;       //왼쪽에서 오른쪽으로 큰 값을 찾고, 오른쪽에서 왼쪽으로 훑으며 작은 값을 찾는다. 

        // 원소가 한 개인 경우
        if(start >= end){
            return;
        }

        // 피벗 값은 첫번째 원소 인덱스
        int pivot = start;

        // 엇갈린 상황이 올 때 까지
        while(left < right){
            while(data[left] < data[pivot]) left++;       //왼쪽에서 오른쪽으로 훑으며 큰 값을 찾을 때 까지
            while(data[right] > data[pivot]) right--;     //오른쪽에서 왼쪽으로 훑으며 작은 값을 찾을 때 까지
            
            if(left < right){
                int tmp = data[right];
                data[right] = data[left];
                data[right] = tmp;
                left++; right--;
            }
        }

        quickSort(data, start, right);
        quichSort(data, left, end);
    }

✏️시간복잡도 / BigO

  • O(N * logN)

  • 2^10 은 약 1000, 2^20 은 약 1,000,000이다. 이때 logN 에서 N이 백만이어도 20밖에 안된다. 거의 상수라고 봐도 무방할 정도로 매우 빠른 것이다.

  • 한 번 수행할 때 오른쪽과 왼쪽으로 나누어진다.

  • 1 2 3 4 5 6 7 8 9 10을 선택정렬로 정렬하는 경우 N*N 이므로 100.

  • 분할정복으로 반반 쪼갠다면
    1 2 3 4 5 –> 5 * 5 = 25
    6 7 8 9 10 –> 5 * 5 = 25
    25 + 25 총 50이 되므로 100보다 훨씬 작다. 작게 쪼갠 뒤 나중에 합치게 되면 훨씬 적은 연산으로 수행할 수 있다. 이것이 분할정복의 원리이다. 반으로 쪼개는 과정은 logN이라고 할 수 있고, 따라서 시간복잡도는 N*logN이 되는 이유이다.

  • 그러나! 피벗값에 따라 최악의 경우 N^2이 나올 수 있다

    • 이미 정렬이 되어 있는 경우, 1 2 3 4 5 6 7 8 9 10 피벗값은 1이 되는데 1보다 작은 값이 없어 10번의 비교연산수행 후 1 하나만 고정된다. 피벗값이 차례로 2, 3…으로 넘어가도 마찬가지이다. 분할정복의 이점을 쓰지 못하는 경우가 되는 것이다. 따라서 10+9+8+7+6+5+4+3+2+1이 된다.

즉, 일반적인 경우는 퀵정렬이 빠르지만 이미 정렬이 되어 있는 경우에는 삽입정렬이 더 빠르다.

You may also enjoy