C# 퀵 정렬(Quick Sort)에 대해서

퀵 정렬이란?

이름부터 퀵 정렬이기 때문에 빠르다. 그렇다면 퀵 정렬은 어떤 정렬인가?

 

• '찰스 앤토니 리처드 호어(Charles Antony Richard Hoare)'가 개발한 정렬 알고리즘
• 분할 정복(divide and conquer) 방법
• 분할, 정복, 결합의 과정으로 진행
• 불안정 정렬, 비교 정렬
• 분할 정복 알고리즘에 속하며 평균적으로 매우 빠른 수행 속도를 자랑한다.

 

퀵 정렬 수행과정

• 배열의 첫 번째 값을 피벗(pivot)으로 설정한다.
• low는 left + 1 자리부터 피벗과 비교해서 작으면 한 칸씩 증가한다.
• high는 right 자리에서부터 피벗과 비교해서 크면 한 칸씩 감소한다.
• low와 high가 결정되면 서로 스왑한다.
• 위의 절차를 반복한다.  low와 high가 교차하면 정지한다.
• 피벗값과 high를 스왑(SWAP)한다
• 피벗을 기준으로 왼쪽, 오른쪽 두 개의 배열로 만들어서 각각 1~5번 과정을 반복한다.
• 더 이상 나눌 배열이 없을 때까지 반복한다.
• 정렬 완료

 

 

 

시간 복잡도와 공간 복잡도

• 최고 시간 복잡도: O(n log n)
• 평균 시간 복잡도: O(n log n)
• 최악 시간 복잡도: O(n^2)
• 최고 공간 복잡도: O(1)

 

수도 코드

function quickSort(arr, l, r)
    if l < r
        pivotIndex = partition(arr, l, r)
        quickSort(arr, l, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, r)

function partition(arr, l, r)
    pivot = arr[r]
    i = l - 1
    
    for j = l to r - 1
        if arr[j] < pivot
            i = i + 1
            swap arr[i] and arr[j]
    
    swap arr[i + 1] and arr[r]
    return i + 1

 

예제 코드

using System;

namespace backjun
{
    public class Program
    {
        static void Main(string[] args)
        {
            int[] array = new int[] { 5,3,8,4,9,1,6,2,7 };

            QuickSort(array, 0, 8);

            Console.WriteLine();
        }

        public static void QuickSort(int[] array, int left, int right)
        {
            var pivot = left;
            var low = left + 1;
            var high = right;

            while(low <= high)
            {
                if (array[low] < array[pivot])
                {
                    low++;
                    continue;
                }

                if (array[pivot] < array[high])
                {
                    high--;
                    continue;
                }

                if (low < high)
                {
                    Swap(array, low, high);
                }
            }

            if (left < right)
            {
                Swap(array, pivot, high);

                QuickSort(array, left, high - 1);
                QuickSort(array, high + 1, right);
            }
        }

        public static void Swap(int[] array, int left, int right)
        {
            var temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }
}

 

참고 사이트

Quick Sort: A Beginner-Friendly Guide with TypeScript

[알고리즘] 퀵 정렬(Quick Sort) 알고리즘 개념과 원리에 대해 쉽고 빠르게 공부해보자 [C언어]