Quick_Sort(iterative).cc

#include<stdio.h>
#define MAX 100

typedef struct{
	int left; //하한
	int right; //상한
}element; //스택 구조체

element stack[MAX];
int top = -1; //스택 top=-1

//arr배열의 a번째 원소와 b번째 원소 교환
void EXCHANGE(int* arr, int a, int b)
{
	int temp;
	temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

//(정렬을 원하는 배열, 하한(배열의 시작 index), 상한(배열의 마지막 index))
void QuickSort(int *arr, int m, int n)
{
	int i = 0;
	int j = 0;

	int pivot = m; //key값 index
	stack[MAX];
	
	top++;
	stack[top].left = m;//스택에 상한 값 넣음
	stack[top].right = n;//스택에 하한 값 넣음

	while (top != -1) //스택이 비기 전까지
	{
		m = stack[top].left; //하한 스택 pop
		n = stack[top].right; //상한 스택 pop
		top-- ;

		if(m < n){
			pivot = m;

			i = m;
			j = n;
			while (1){
				while (arr[i] < arr[pivot])	i++; //작은 수 찾기
				while (arr[j] > arr[pivot])	j--; //큰 수 찾기

				if (i < j){
					EXCHANGE(arr, i, j); //두 값 교환
				}
				else{ //작은 값이 큰 값보다 뒤에 있을 경우
					break; //반복문 종료
				}
			}
			EXCHANGE(arr, j, pivot); //pivot과 작은 값을 교환
			
			//스택을 이용하여 재귀 구현
			//스택은 FILO이므로 왼쪽 배열을 먼저 정렬하려면 나중에 넣음
			//QuickSort(arr, j + 1, n);
			top++;
			stack[top].left = j + 1; //하한에 j+1 push
			stack[top].right = n; //상한에 n push
		
			//QuickSort(arr, m, j - 1);
			top++;
			stack[top].left = m; //하한에 m push
			stack[top].right = j - 1; //상한에 j-1 push
			
		}
	}

}


void main(){
	int number[12] = { 8, 3, 11, 9, 12, 2, 6, 15, 18, 10, 7, 14 };
	int i;
	for (i = 0; i < 12; i++){
		printf("%d ", number[i]);
	}
	printf("\n");
	QuickSort(number, 0, 11);
	for (i = 0; i < 12; i++){
		printf("%d ", number[i]);
	}
}