퀵 정렬(Quick Sort)은 일반적으로 재귀 호출을 사용하지만, 재귀 대신 명시적인 스택(배열)을 활용하면 반복적(Iterative) 방식으로도 구현할 수 있습니다. 재귀 호출로 인한 스택 오버플로우를 걱정할 필요가 없고, 함수 호출 오버헤드를 줄일 수 있다는 점이 장점입니다.
다음은 반복적 퀵 정렬을 구현한 Java 프로그램입니다.
예제 코드
public class Demo{
void swap_vals(int arr[], int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int partition(int arr[], int l, int h){
int x = arr[h];
int i = (l - 1);
for (int j = l; j <= h - 1; j++){
if (arr[j] <= x){
i++;
swap_vals(arr, i, j);
}
}
swap_vals(arr, i + 1, h);
return (i + 1);
}
void quick_sort(int arr[], int l, int h){
int my_list[] = new int[h - l + 1];
int top = -1;
my_list[++top] = l;
my_list[++top] = h;
while (top >= 0){
h = my_list[top--];
l = my_list[top--];
int p = partition(arr, l, h);
if (p - 1 > l){
my_list[++top] = l;
my_list[++top] = p - 1;
}
if (p + 1 < h){
my_list[++top] = p + 1;
my_list[++top] = h;
}
}
}
public static void main(String args[]){
Demo my_ob = new Demo();
int my_arr[] = { 34, 76, 41, 32, 11, 0 , 91, 102, -11};
my_ob.quick_sort(my_arr, 0, my_arr.length - 1);
int i;
System.out.println("After iteratively performing quick sort, the array is ");
for (i = 0; i < my_arr.length; ++i)
System.out.print(my_arr[i] + " ");
}
}실행 결과
After iteratively performing quick sort, the array is -11 0 11 32 34 41 76 91 102
코드 동작 원리
Demo 클래스에는 세 가지 핵심 메서드가 포함되어 있습니다.
- swap_vals: 임시 변수(
temp)를 사용하여 배열 내 두 위치의 값을 서로 교환하는 유틸리티 메서드입니다. - partition: 마지막 요소를 피벗(pivot)으로 선택하고, 피벗보다 작거나 같은 요소들을 왼쪽으로 몰아넣은 뒤 피벗을 올바른 위치에 배치합니다. 그리고 피벗의 최종 인덱스를 반환하여 배열을 두 부분으로 나눕니다.
- quick_sort: 재귀 호출 대신
my_list라는 스택 역할을 하는 배열을 사용합니다. 처리해야 할 하위 배열의 시작 인덱스와 끝 인덱스를 스택에 저장하고,while루프를 통해 스택이 빌 때까지 분할(partition) 작업을 반복 수행합니다.
main 메서드에서는 Demo 클래스의 인스턴스를 생성하고 정렬되지 않은 정수형 배열을 초기화합니다. 이후 해당 배열에 대해 quick_sort 메서드를 호출하면, 정렬된 결과가 콘솔에 출력됩니다.
참고 사항
이 반복적 퀵 정렬의 평균 시간 복잡도는 O(n log n)이며, 최악의 경우 O(n²)입니다. 재귀 버전과 알고리즘 자체의 성능은 동일하지만, 호출 스택 깊이에 제약이 있는 환경에서 안정적으로 동작한다는 실용적인 이점이 있습니다.