// QUICKSORT_ver1
void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers[left]; // 가장 왼쪽원소를 피봇으로 선택
while (left < right)
{
// 값이 선택한 피봇과 같거나 크다면, 이동할 필요가 없다
while ((numbers[right] >= pivot) && (left < right))
right --;
// 그렇지 않고 값이 피봇보다 작다면,
// left 위치에 현재 값을 넣는다.
if (left != right)
{
numbers[left] = numbers[right];
}
// left부터 right까지 값을 읽어들이면서
// 피봇보다 큰 값이 있다면, left값을 right로 이동한다.
while ((numbers[left] <= pivot) && (left < right))
left ++;
if (left != right)
{
numbers[right] = numbers[left];
right --;
}
}
// 모든 스캔이 끝났다면, 피봇값을 현재 left위치에 입력한다.
// 이제 피봇을 기준으로 왼쪽에는 피봇보다 작거나 같은 값만 남았다.
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
// 재귀호출을 수행한다.
if (left < pivot)
q_sort(numbers, left, pivot - 1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}
void QuickSort(int numbers[], int array_size)
{
q_sort(numbers, 0, array_size -1);
}
int const MAX = 5;
int g_arr[MAX] = {0, };
int main()
{
printf("========정렬전========\n");
//AscendingNumber(g_arr, MAX); // 순열 배열 생성
//DescendingNumber(g_arr, MAX); // 역순 배열 생성
RandomNumber(g_arr, MAX); // 랜덤 배열 생성
PrintNumber(g_arr, MAX); // 배열 출력
printf("\n");
clock_t start = clock(); // 시작 시간
QuickSort(g_arr, MAX); // ShellSort
clock_t end = clock(); // 끝 시간
printf("========정렬후========\n");
PrintNumber(g_arr, MAX); // 배열 출력
printf("\nTime : %f\n", ((double)(end-start)) / CLOCKS_PER_SEC);
}