C:TIL-quick sort

quick sort는 정렬이 필요할 때 자주 사용하는 알고리즘이다.(성능-O(nlogn)

quicksort를 코드로 작성하였을 경우,

void swap(int A[], int a, int b)
{
	int temp = A[a];
	A[a] = A[b];
	A[b] = temp;
}

int partition(int A[], int p, int r)
{
	// 배열 A[p..r]의 원소들을 A[r]을 기준으로 양족으로 재배치하고 
	// A[r]이 자리한 위치를 return한다.
	int i, j;
	i = p - 1; j = p;

	while (j != r) {
		if (A[j] < A[r])
			swap(A, ++i, j);
		j++;
	}
	swap(A, ++i, r);
	return i;
}

void quickSort(int A[], int p, int r)
{
	int q;
	if (p < r) {
		q = partition(A, p, r);
		printList(A, 9);
		quickSort(A, p, q - 1);
		quickSort(A, q + 1, r);
	}
}

매번 quicksort 알고리즘을 코드로 구현하기 번거롭기 때문에,
간편하게 stdlib.h에 있는 qsort() 함수를 사용할 수 있다.

void qsort (void *base, size_t nel, size_t width, int (*compare)(const void *, const void *);

int static compare (const void* first, const void* second) 
//오름차순. 내림차순의 경우 등호 방향 바꾸기
{
    if (*(int*)first > *(int*)second)
        return 1;
    else if (*(int*)first < *(int*)second)
        return -1;
    else
        return 0;
}

사용예시-> qsort(array, array_size, sizeof(int), compare)