퀵 정렬(Quick Sort)이란?
퀵 정렬은 분할 정복(Divide and Conquer) 기법을 사용하는 대표적인 정렬 알고리즘입니다. 배열에서 하나의 피벗(pivot) 요소를 선택하고, 이 피벗을 자신의 올바른 위치에 배치합니다. 그런 다음 피벗을 기준으로 왼쪽과 오른쪽에 있는 하위 배열들에 대해 다시 퀵 정렬을 재귀적으로 수행하며, 전체 배열이 정렬될 때까지 이 과정을 반복합니다.
평균 시간 복잡도는 O(n log n)으로 매우 빠르며, 실무에서도 널리 사용되는 정렬 방식입니다.
C# 재귀 퀵 정렬 예제 코드
다음은 C#에서 재귀를 사용하여 퀵 정렬을 구현한 프로그램입니다.
using System;
namespace QuickSortDemo {
class Example {
static public int Partition(int[] arr, int left, int right) {
int pivot;
pivot = arr[left];
while (true) {
while (arr[left] < pivot) {
left++;
}
while (arr[right] > pivot) {
right--;
}
if (left < right) {
int temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
} else {
return right;
}
}
}
static public void quickSort(int[] arr, int left, int right) {
int pivot;
if (left < right) {
pivot = Partition(arr, left, right);
if (pivot > 1) {
quickSort(arr, left, pivot - 1);
}
if (pivot + 1 < right) {
quickSort(arr, pivot + 1, right);
}
}
}
static void Main(string[] args) {
int[] arr = {67, 12, 95, 56, 85, 1, 100, 23, 60, 9};
int n = 10, i;
Console.WriteLine("Quick Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
quickSort(arr, 0, 9);
Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
}
}
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
Quick Sort Initial array is: 67 12 95 56 85 1 100 23 60 9 Sorted Array is: 1 9 12 23 56 60 67 85 95 100
코드 상세 분석
1. Main() 함수 — 초기 배열 출력 및 정렬 호출
Main() 함수에서는 먼저 초기 배열의 상태를 화면에 출력합니다. 이후 quickSort() 함수를 호출하여 배열 전체에 대한 퀵 정렬을 수행합니다. 해당 코드는 다음과 같습니다.
int[] arr = {67, 12, 95, 56, 85, 1, 100, 23, 60, 9};
int n = 10, i;
Console.WriteLine("Quick Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
quickSort(arr, 0, 9);2. quickSort() 함수 — 재귀적 분할
quickSort() 함수 내부에서는 Partition() 함수를 호출하여 피벗 요소를 결정합니다. 그런 다음 반환된 피벗 값에 따라 좌우 하위 배열을 대상으로 quickSort()를 다시 호출하여 재귀적으로 정렬을 진행합니다.
if (left < right) {
pivot = Partition(arr, left, right);
if (pivot > 1) {
quickSort(arr, left, pivot - 1);
}
if (pivot + 1 < right) {
quickSort(arr, pivot + 1, right);
}
}- pivot > 1인 경우: 피벗 왼쪽 구간(left ~ pivot-1)에 대해 재귀 호출을 수행합니다.
- pivot + 1 < right인 경우: 피벗 오른쪽 구간(pivot+1 ~ right)에 대해 재귀 호출을 수행합니다.
3. Partition() 함수 — 피벗 위치 확정
Partition() 함수에서는 주어진 배열 구간의 가장 왼쪽 요소를 피벗으로 선택한 뒤, 왼쪽 인덱스와 오른쪽 인덱스를 이동시키며 피벗보다 작은 값과 큰 값을 서로 교환(swap)합니다. 이 과정을 반복하여 피벗이 자신의 최종 위치에 도달하면 해당 인덱스를 반환합니다.
int pivot;
pivot = arr[left];
while (true) {
while (arr[left] < pivot) {
left++;
}
while (arr[right] > pivot) {
right--;
}
if (left < right) {
int temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
} else {
return right;
}
}정리
이처럼 퀵 정렬은 피벗을 중심으로 배열을 계속 분할하면서 정렬하는 방식입니다. 재귀 호출을 통해 각 하위 배열이 독립적으로 정렬되며, 모든 분할이 완료되면 전체 배열이 오름차순으로 정렬된 결과를 얻을 수 있습니다. C#뿐만 아니라 다양한 프로그래밍 언어에서 동일한 개념으로 구현할 수 있으므로, 알고리즘 학습의 필수 주제로 꼭 익혀두시기 바랍니다.