[C/알고리즘] 퀵정렬 Quick Sort

// 퀵정렬 quickSort.c

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

// int형 두개를 맞바꿔주는 함수.
void int_swap(int *x, int *y) {
	int tmp = *x;

	*x = *y;
	*y = tmp;
}

// long int형 두개를 맞바꿔주는 함수.
void long_swap(long *x, long *y) {
   long tmp = *x;
   *x = *y;
   *y = tmp;
}

// 배열의 내용을 출력한다.
void printArray(int *array, int length) {
    for (int i = 0; i < length; i++) {
        printf("%d\n", array[i]);
    }
    printf("\n");
}

int quick_sort(int *array, int start, int end) {

	if (start >= end) return 0;
	int pivot = start;
	int left = start + 1;
	int right = end;
	int tmp;

	while (left <= right) {
		while (left <= end && array[left] <= array[pivot]) {
			left++;
		}
		while (right > start && array[right] >= array[pivot]) {
			right--;
		}
		if (left > right) {
			int_swap(&array[right], &array[pivot]);
		}
		else {
			int_swap(&array[left], &array[right]);
		}
	}
	quick_sort(array, start, right - 1);
	quick_sort(array, right + 1, end);

	return 0;
}


int main() {
	// int num[] = { 5, 7, 9, 0, 3, 1, 6, 2, 4, 8 };
    // const int length = sizeof(num) / sizeof(int);
    const int length = 1000;
    int *num = calloc(length, sizeof(int));

 	for (int i = 0; i < length; i++)
		num[i] = rand();

	quick_sort(num, 0, length-1);
    printArray(num, length);

	free(num);
	return 0;
}
------실행 결과---------

2416949
6072641
6939507
7684930
8936987
10901063
11614769
11671338
12260289
12895151
14989683
........
2118421993
2130794395
2135019593
2137100237
2137390358
2142757034
2143124030
2145174067
2147469841