알고리즘 - 퀵정렬(quick sort) c#

퀵정렬(quick sort)

---

특정한 값을 기준으로 큰 숫자와 작은 숫자를 나누면 어떨까? 해서 나온 답이 >> 퀵정렬은 피봇을 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해 가며 정렬하는 방법입니다.

퀵정렬 과정

1. 피벗 선택: 배열에서 하나의 원소(피벗)를 선택합니다.
2. 분할: 피벗보다 작은 원소들은 왼쪽으로, 큰 원소들은 오른쪽으로 이동시키는 방식으로 배열을 재배열합니다.
3. 재귀적 정렬: 피벗을 제외한 왼쪽과 오른쪽 부분 배열에 대해 같은 과정을 재귀적으로 반복합니다.

 

퀵정렬(quick sort) 이론

---

이제 아래 사진과 함께 설명해 보겠습니다.

출처 : https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

그림에 있는 피봇을 기준으로 보면서 위에 글을  확인하시고
특정한 값을 기준으로 큰 숫자와 작은 숫자를 나누면 어떨까? 를 기억하시면 이해가 잘 될 겁니다.

 

퀵정렬(quick sort) 코드

---

using System;

class Program
{
    // 퀵 정렬 메서드
    static void QuickSort(int[] array, int low, int high)
    {
        if (low < high)
        {
            int pivotIndex = Partition(array, low, high);
            QuickSort(array, low, pivotIndex - 1);
            QuickSort(array, pivotIndex + 1, high);
        }
    }

    // 파티션 수행 메서드
    static int Partition(int[] array, int low, int high)
    {
        int pivot = array[high];
        int i = low - 1;

        for (int j = low; j < high; j++)
        {
            if (array[j] <= pivot)
            {
                i++;
                Swap(array, i, j);
            }
        }

        Swap(array, i + 1, high);
        return i + 1;
    }

    // 두 원소 위치 교환
    static void Swap(int[] array, int i, int j)
    {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    static void Main()
    {
        int[] data = { 9, 4, 6, 8, 3, 1, 7, 2, 5 };
        Console.WriteLine("정렬 전: " + string.Join(", ", data));

        QuickSort(data, 0, data.Length - 1);

        Console.WriteLine("정렬 후: " + string.Join(", ", data));
    }
}