반응형
퀵 정렬(Quick sort)
quick 정렬의 source code이다. C에서 기본으로 제공하는 qsort는 아래와 같은 원리도 동작한다.
#include <stdio.h>
#include <stdlib.h>
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
int quickSort(int* arr, int left, int right)
{
int L = left, R = right;
int pivot = arr[(left + right)/2];
do {
while( arr[L] < pivot )
L++;
while( arr[R] > pivot )
R--;
if( L <= R )
{
swap(&arr[L], &arr[R]);
L++;
R--;
}
} while( L <= R );
if( left < R )
quickSort(arr, left, R);
if( L < right )
quickSort(arr, L, right);
}
int main()
{
int num =0, i = 0, j = 0, input = 0;
int *arr = NULL;
scanf("%d", &num);
arr = (int*)calloc(num, sizeof(int));
for(i=0; i<num; i++)
{
scanf("%d", &input);
arr[i] = input;
}
quickSort(arr, 0, num-1);
for(i=0; i<num; i++)
{
printf("%d\n", arr[i]);
}
free(arr);
arr = NULL;
return 0;
}
c에서 제공하는 qsort를 이용하여 정렬한다.
첫번째는 sort 할 포인터, 두번째는 크기, 세번째는 포인터 형(간격), 네번째는 compare 함수.
compare 함수에 구현된 부분은 오름차순 정렬을 기본으로 하였으며, 내림차순으로 정렬하기 위해서는 return value가 반대로 되도록 해준다.
#include <stdio.h> #include <stdlib.h> int compare(const void* a, const void* b) { if( *(int*)a > *(int*)b ) return 1; else if( *(int*)a < *(int*)b ) return -1; else return 0; } int main() { int num =0; int *arr = NULL; scanf("%d", &num); arr = (int*)calloc(num, sizeof(int*)); for(int i=0; i<num; i++) scanf("%d", &arr[i]); qsort(arr, num, sizeof(int), compare); for(int i=0; i<num; i++) printf("%d ", arr[i]); free(arr); return 0; }
반응형
'알고리즘' 카테고리의 다른 글
[알고리즘] DFS 경로찾기 (0) | 2018.10.20 |
---|---|
[알고리즘] BFS (0) | 2018.10.17 |
[알고리즘] DFS (0) | 2018.08.31 |
[알고리즘] 쿼드트리 (Quad Tree) (0) | 2018.07.31 |
[알고리즘] 계수 정렬(Counting sort) (0) | 2018.06.11 |
댓글