퀵 정렬(Quick Sort)에 대해 알아보자!

퀵 정렬

• 오름차순을 기준으로 정렬.
• 불안정 정렬에 속함.
• 매우 빠른 수행 속도를 자랑하는 방법.
• 기준이 되는 원소(Pivot)을 잡고 해당 원소보다 작은 값을 왼쪽, 큰 값을 오른쪽에 배치해주며 정렬하는 방법.

<이미지 출처:https://gmlwjd9405.github.io/images/algorithm-quick-sort/quick-sort.png>

 

---

퀵 정렬 C# 코드

void SortQuick(int[] _arr, int _first, int _last)
    {
        if (_first < _last)
        {
            int pivot = GetPivot(_arr, _first, _last);

            SortQuick(_arr, _first, pivot - 1);
            SortQuick(_arr, pivot + 1, _last);
        }
    }

    int GetPivot(int[] _arr, int _first, int _last)
    {
        int pivot = _arr[_first];
        int low = _first + 1;
        int high = _last;

        while (low <= high)
        {
            while (low <= high && _arr[low] < pivot)
            {
                low++;
            }

            while (low <= high && _arr[high] > pivot)
            {
                high--;
            }

            if (low <= high)
            {
                Swap(_arr, low, high);
                low++;
                high--;
            }
        }

        Swap(_arr, _first, high);
        return high;
    }
    
    public void Swap(int[] arr, int left, int right)
    {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

 

• 장점
  - 속도가 빠름.
  - 메모리 효율이 좋음.
  
  
• 단점
  - 정렬된 리스트에 대해서는 불균형 분할에 의해 오히려 수행시간이 오래 걸림.
  - 불균형 분할을 방지하기 위해 피벗 선택 시 리스트를 더욱 균등하게 분할할 수 있는 데이터를 선택.

<이미지 출처: https://gmlwjd9405.github.io/images/algorithm-quick-sort/sort-time-complexity.png>

---