비재귀 퀵소트

#include <stdlib.h>
#include <stdio.h>

void QuickSort(int* array, int n)
{

int start, end, left, right;

int pivot, t;
int* pBase;
int top = -1;

 

pBase = (int*)malloc(sizeof(int)*(2*n+2));
pBase[++top] = n-1;
pBase[++top] = 0;

 

while(top != -1)

{

start = pBase[top--];
end = pBase[top--];
if(end-start > 0)
{

pivot = start;
left = start + 1;
right = end;

 

while(1)
{

while(array[left] < array[pivot] && left<right)

++left;

while(right >= left && array[right] > array[pivot])

--right;

 

if(left >= right)

break;

 
t = array[left];
array[left] = array[right];
array[right] = t;

}

t = array[pivot];
array[pivot] = array[right];
array[right] = t;

pBase[++top] = right - 1;
pBase[++top] = start;
pBase[++top] = end;
pBase[++top] = right + 1;

}

}

free(pBase);

}

 

int main()
{

int DataSet[] = {6, 5, 4, 3, 2, 1};
int Length = sizeof(DataSet)/ sizeof(int);
int i=0;

QuickSort(DataSet, 6);
for(i=0; i<Length; i++)
printf("%d ", DataSet[i]);
puts("");
return 0;

}