정렬(Sorting)은 데이터 요소들을 오름차순 또는 내림차순으로 배열하는 과정을 말합니다. 효율적인 정렬 알고리즘을 선택하는 것은 프로그램 성능에 큰 영향을 미치며, 그중에서도 퀵 정렬(Quick Sort)은 가장 널리 사용되는 정렬 기법 중 하나입니다.
정렬의 종류
C 언어에서 활용되는 대표적인 정렬 기법은 다음 다섯 가지가 있습니다.
- 버블 정렬(Bubble Sort, 교환 정렬)
- 선택 정렬(Selection Sort)
- 삽입 정렬(Insertion Sort, 선형 정렬)
- 퀵 정렬(Quick Sort, 분할 교환 정렬)
- 병합 정렬(Merge Sort, 외부 정렬)
퀵 정렬(Quick Sort)이란?
퀵 정렬은 분할 정복(Divide and Conquer) 방식을 사용하는 알고리즘으로, 평균 시간 복잡도가 O(n log n)으로 매우 빠른 성능을 자랑합니다. 동작 과정은 다음 세 단계로 요약할 수 있습니다.
- 1단계: 배열에서 하나의 요소를 선택하여 피벗(pivot)으로 지정합니다.
- 2단계: 정렬되지 않은 배열을 두 개의 하위 배열로 나눕니다.
- 3단계: 피벗보다 작은 값은 첫 번째 하위 배열로, 피벗보다 큰 값은 두 번째 하위 배열로 이동시킵니다.
그림으로 이해하는 퀵 정렬
아래 예시에서 각 기호는 다음을 의미합니다.
- P: 피벗(Pivot) 요소
- L: 왼쪽 포인터(Left Pointer)
- R: 오른쪽 포인터(Right Pointer)
정렬할 요소는 6, 3, 7, 2, 4, 5 입니다.
첫 번째 분할이 완료되면 다음과 같은 상태가 됩니다.
- 피벗이 최종 위치에 고정됩니다.
- 피벗 왼쪽의 모든 요소는 피벗보다 작습니다.
- 피벗 오른쪽의 모든 요소는 피벗보다 큽니다.
- 배열을 왼쪽 부분과 오른쪽 부분, 두 개의 하위 배열로 나눕니다.
- 왼쪽 파티션에 퀵 정렬을 재귀적으로 적용합니다.
모든 분할 과정이 끝나면 다음과 같은 결과를 얻습니다.
- 각 피벗이 자신의 최종 위치에 고정됩니다.
- 왼쪽 요소들은 모두 더 작은 값으로 정렬되어 있습니다.
- 오른쪽 요소들도 더 큰 값으로 정렬되어 있습니다.
- 두 개의 하위 배열을 합치면 최종 정렬 결과는 2, 3, 4, 5, 6, 7 입니다.
C 언어 구현 예제
다음은 퀵 정렬 기법을 사용해 요소를 정렬하는 C 프로그램의 전체 소스 코드입니다.
#include<stdio.h>
void quicksort(int number[25],int first,int last){
int i, j, pivot, temp;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(number[i]<=number[pivot]&&i<last)
i++;
while(number[j]>number[pivot])
j--;
if(i<j){
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}
int main(){
int i, count, number[25];
printf("몇 개의 요소를 입력하시겠습니까?: ");
scanf("%d",&count);
printf("%d개의 요소를 입력하세요: ", count);
for(i=0;i<count;i++)
scanf("%d",&number[i]);
quicksort(number,0,count-1);
printf("정렬된 요소 순서: ");
for(i=0;i<count;i++)
printf(" %d",number[i]);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 출력 결과를 확인할 수 있습니다.
몇 개의 요소를 입력하시겠습니까?: 10 10개의 요소를 입력하세요: 2 3 5 7 1 9 3 8 0 4 정렬된 요소 순서: 0 1 2 3 3 4 5 7 8 9
시간 복잡도 정리
퀵 정렬의 시간 복잡도는 다음과 같습니다.
- 평균: O(n log n)
- 최선: O(n log n)
- 최악: O(n²) — 이미 정렬된 배열에서 피벗 선택이 좋지 않을 경우 발생
퀵 정렬은 추가 메모리가 거의 필요 없는 제자리(in-place) 정렬이며, 피벗 선택 전략만 잘 조정하면 실무에서도 안정적으로 뛰어난 성능을 발휘합니다.