알고리즘 – Quick Sort (퀵정렬) (2020년)

알고리즘 종류인 Quick Sort (퀵정렬)에 대한 정보 찾고 계셨나요? 오늘은 정렬 알고리즘인 Quick Sort 퀵정렬에 대해 알아보려 합니다. 퀵 정렬의 시간 복잡도 (Big-O Notation)는 최상의 경우 O(n log n), 평균적으로 O(n log n) 그리고 최악의 경우 O(n^2) 입니다.

퀵 정렬은 정렬 알고리즘에서 빠르고 효율적인 알로리즘으로 뽑혀, 많은 개발자들이 사용하고 있습니다.

1. 예제

예제:

방법:

리스트에서 “Pivot point” 즉 피봇 아이템 하나를 골라, 피봇 아이템의 값보다 작은 아이템들은 피봇 아이템의 왼쪽으로, 큰 아이템은 오른쪽으로 넘기는 방식을 기반으로 정렬해 나아갑니다.

2. 퀵 정렬 풀이

Iteration 1

1. Pivot을 0번째 인덱스인 5번값으로 정했습니다.

int leftIndex = 0;

int rightIndex= 6;

2. 맨 왼쪽 leftIndex 아이템과 Pivot 아이템과 비교해서 pivot보다 큰 아이템 (즉 오른쪽으로 넘길 아이템)을 찾습니다. 5(비교 아이템 index 0) == 5(pivot 아이템). 작지도 크지도 않기때문에 아무것도 하지 않습니다.

int leftIndex = 0;

int rightIndex= 6;

3. 이번에는 맨 오른쪽 rightIndex 아이템과 Pivot 아이템과 비교해서 이번엔 pivot보단 작은 아이템 (즉 왼쪽으로 넘길 아이템)을 찾습니다. 3(비교 아이템 index 6) < 5(pivot 아이템).

int leftIndex = 0;

int rightIndex= 6;

4. leftIndex아이템과 rightIndex아이템과 바꿔줍니다. (위에 말했듯이 Pivot 값보다 작은 애들은 왼쪽으로 큰 애들은 오른쪽으로 보내는 규칙)

int leftIndex = 0;

int rightIndex= 6;

5. 다시 왼쪽으로 가서 leftIndex부터 다시 비교합니다. 3번이 5번보다 작기때문에 다음 index로 넘어 갑니다. 이미 왼쪽(5보다 작은 아이템들)에 있기 때문입니다. leftIndex = leftIndex + 1;

int leftIndex = 0;

int rightIndex= 6;

6. leftIndex랑 비교합니다. 2번이 5번보다 작기때문에 다음 index로 넘어 갑니다. leftIndex = leftIndex + 1;

int leftIndex = 1;

int rightIndex= 6;

7. leftIndex랑 비교합니다. 4번이 5번보다 작기때문에 다음 index로 넘어 갑니다. Index = Index + 1;

int leftIndex = 2;

int rightIndex= 6;

8. leftIndex랑 비교합니다. 6번이 5번보다 크기때문에 오른쪽에 위치해야합니다. 일단, 넘기기전에 **leftIndex를 기억해둡니다**. leftIndex의 값을 오른쪽으로 넘기기전에 오른쪽에서 왼쪽으로 가져올 아이템을 찾아야합니다. 서로 index를 바꿔야하기때문입니다.

int leftIndex = 3;

int rightIndex= 6;

9. rightIndex랑 pivot이랑 비교합니다. 5번(rightIndex아이템)이 5번(pivot)보다 크지 않기때문에 오른쪽에 있을 필요가 없어졌습니다.

int leftIndex = 3;

int rightIndex= 6;

10. 아까 leftIndex랑 rightIndex랑 바꿔줍니다.

int leftIndex = 3;

int rightIndex= 6;

11. 다시 leftIndex랑 비교합니다. 5(leftIndex아이템)이 5(pivot)보다 작지 않기때문에 왼쪽에 있을 필요가 없어졌습니다. **leftIndex를 기억해둡니다**.

int leftIndex = 3;

int rightIndex= 6;

12. 다시 rightIndex랑 비교합니다. 6(rightIndex아이템)이 5(pivot)보다 크기 때문에 아무것도 하지않습니다. rightIndex = rightIndex – 1;

int leftIndex = 3;

int rightIndex= 6;

13. 다시 rightIndex랑 비교합니다. 7(rightIndex아이템)이 5(pivot)보다 크기 때문에 아무것도 하지않습니다. rightIndex = rightIndex – 1;

int leftIndex = 3;

int rightIndex= 5;

14. 다시 rightIndex랑 비교합니다. 1(rightIndex아이템)이 5(pivot)보다 작습니다. 왼쪽으로 넘겨야 합니다.

int leftIndex = 3;

int rightIndex= 4;

15. leftIndex랑 rightIndex랑 바꿔줍니다.

int leftIndex = 3;

int rightIndex= 4;

16. 아직 Iteration이 끝나지 않았기때문에 나머지 아이템들도 비교합니다. 다시 leftIndex랑 pivot이랑 비교합니다. 1이 5보다 작기 때문에 아무것도 하지 않습니다. leftIndex = leftIndex + 1;

int leftIndex = 3;

int rightIndex= 4;

17. leftIndex랑 rightIndex 자체가 같기때문에, 이번 iteration은 끝 (rightIndex값 (즉 pivot index)을 리턴합니다.)

int leftIndex = 4;

int rightIndex= 4;

18. 한번의 iteration으로 Pivot은 이미 자신의 자리를 찾았다는걸 알수 있습니다.

Iteration 2 – Recursion Left

위와 같은 방식으로 이번 iteration에는 pivot보단 작은 값들인 왼쪽 리스트를 정렬하도록 합니다. Pivot은 더이상 정렬에 투입되지 않습니다. 이미 자신의 위치를 찾았기 때문입니다.

1. 새로운 pivot을 고릅니다. 이번에도 0번째 인덱스인 3번값으로 정했습니다.

int leftIndex = 0;

int rightIndex= 3;

2. 아까와 같이 leftIndex랑 pivot이랑 비교합니다. 3이 3보다 작지 않기 때문에 오른쪽으로 넘겨야 합니다. 오른쪽으로 넘겨 바꿀 오른쪽 아이템을 찾도록 합니다.

int leftIndex = 0;

int rightIndex= 3;

3. rightIndex랑 비교합니다. 4가 1보다 크기 때문에 오른쪽으로 옮겨야 합니다.

int leftIndex = 0;

int rightIndex= 3;

4. leftIndex랑 rightIndex랑 바꿉니다.

int leftIndex = 0;

int rightIndex= 3;

5. 다시 leftIndex랑 비교합니다. 1이 작기때문에 leftIndex = leftIndex + 1;

int leftIndex = 0;

int rightIndex= 3;

6. 다시 leftIndex랑 비교합니다. 2가 작기때문에 leftIndex = leftIndex + 1;

int leftIndex = 1;

int rightIndex= 3;

7. 다시 leftIndex랑 비교합니다. 4가 더 크기때문에 바꿔야 합니다.

int leftIndex = 2;

int rightIndex= 3;

8. 다시 rightIndex랑 비교합니다. 3이 3보다 크지 않기 때문에 왼쪽으로 넘겨야 합니다.

int leftIndex = 2;

int rightIndex= 3;

9. leftIndex랑 rightIndex랑 바꿉니다.

int leftIndex = 2;

int rightIndex= 3;

10. 다시 leftIndex랑 비교합니다. 3이 3보다 작지 않기 때문에 옴겨야 합니다. 하지만, rightIndex가 더 크고 더이상 비교할 대상이 없기 떄문에 iteration은 끝이 남니다.

int leftIndex = 2;

int rightIndex= 3;

Iteration 2 – Recursion Right

이번에는 pivot보다 큰 값들인 오른쪽 리스트를 정렬합니다. Note. 아직 iteration 2라는거 기억하세요. Pivot은 더이상 정렬에 투입되지 않습니다. 이미 자신의 위치를 찾았기 때문입니다.

1. 새로운 pivot을 고릅니다. 이번에는 제일 왼쪽인 5번째 인덱스인 7번값으로 정했습니다.

int leftIndex = 5;

int rightIndex= 6;

2. 위에서 했던것과 같이 leftIndex랑 pivot과 비교하고 leftIndex인 7과 rightIndex인 6과 바꿉니다.

3. 7번과 6번이 바뀌면서 iteration 끝

int leftIndex = 5;

int rightIndex= 6;

Iteration 3 – Recursion Left Left, Right Right

3번째 iteration에서는 2번째 iteration recursion left에서 쪼갠 0부터 3번째까지의 리스트를 다시한번 왼쪽리스트와(0-1) 오른쪽리스트(2-3)로 쪼개서 비교해 나갑니다.

3. 해석

7개의 아이템을 가지고 있는 리스트가 퀵정렬로 인해서 3번의 iteration만에 성공적으로 정렬 했습니다.

이번 예제같은 경우에는 최상의 경우라 할수 있습니다. 랜덤으로 리스트에서 pivot index를 고르게 되는데 고른 pivot 값이 리스트에서 그나마 중간에 속하기 때문에 첫 iteration후 왼쪽 리스트와 오른쪽 리스트가 대충 대칭이 됩니다. 대칭이 되면 좋은 이유는 Recursive하게 다음 iteration에서 list를 왼쪽sub-list랑 오른쪽 sub-list로 나눠 나가며 계속 정렬해 나가야 하기 때문에 좋습니다.

[7] Iteration 1

[4] [2] Iteration 2

[2],[2] [2] Iteration 3

최악의 경우는, 고른 pivot의 값이 항상 서브 리스트의 가장 작은 값 또는 항상 가장 큰값이라면 최악의 경우가 됩니다.

[7] Iteration 1 – 고른값 1

[0] [6] Iteration 2 – 고른값 2

[0] [0] [5] Iteration 3 – 고른값 3

[0] [0] [0] [4] Iteration 4 – 고른값 4

[0] [0] [0] [0] [3] Iteration 5 – 고른값 5

[0] [0] [0] [0] [0] [2] Iteration 6

Iteration이 6가 되는걸 볼수 있습니다. 7개의 아이템 리스트를 정렬하는데 필요한 iteration이 6이면 O(n^2) 최악경우가 됩니다.

4. C# Quick Sort 코드

static void Main(string[] args)
{
    int[] list = { 5, 2, 4, 6, 1, 7, 3};
    QuickSort(list, 0, list.Length - 1);
}

static public void QuickSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int pivot = Partition(arr, left, right);
        if (pivot > 1)
            QuickSort(arr, left, pivot - 1);

        if (pivot + 1 < right)
            QuickSort(arr, pivot + 1, right);
    }
}

static public int Partition(int[] list, int left, int right)
{
    int pivot = list[left];

    while (true)
    {
        while (list[left] < pivot)
            left++;

        while (list[right] > pivot)
            right--;

        if (left < right)
        {
            int temp = list[right];
            list[right] = list[left];
            list[left] = temp;
        }
        else
        {
            return right;
        }
    }
}