퀵소트(quicksort) 알고리즘
다양한 퀵소트 구현 방식이 존재 하지만, 아래의 방식이 가장 구현하기 쉽고 속도도 빠르다.
<사용법 >
quickSort(정렬할 배열, 배열 맨 왼쪽, 배열 맨 오른쪽)
<예시>
#define N 5
int arr[N] = {5,4,3,2,1};
quickSort(arr, 0, N-1);
<코드>
void swap(int &x, int &y) { int temp = x; x = y; y = temp; } void quickSort(int A[], int left, int right) { int leftIndex = left, rightIndex = right; int pivot = A[(left + right) / 2]; while (leftIndex <= rightIndex) { while (A[leftIndex] < pivot) leftIndex++; while (A[rightIndex] > pivot) rightIndex--; if (leftIndex <= rightIndex) { swap(A[leftIndex], A[rightIndex]); leftIndex++; rightIndex--; } } if (left < rightIndex) quickSort(A, left, rightIndex); if (right > leftIndex) quickSort(A, leftIndex, right); } | cs |
<STL 형태의 퀵소트 구현>
void _swap(void* a, void* b, int size) { void* temp = malloc(size); memcpy(temp, a, size); memcpy(a, b, size); memcpy(b, temp, size); free(temp); } int comepare(const void* a, const void* b) { if(((point*)a)->x < ((point*)b)->x) return 1; else if (((point*)a)->x > ((point*)b)->x) return -1; else return 0; } void quickSort(void* arr, int count, int size, int (*cmp)(const void*, const void*)) { int left = 0, right = count - 1; int leftIndex = 0, rightIndex = right, mid = (left + right) / 2; void* pivot = malloc(size); memcpy(pivot, (char*)arr + mid*size, size); while (leftIndex <= rightIndex) { while (cmp((char*)arr + leftIndex*size, pivot) > 0) leftIndex++; while (cmp((char*)arr + rightIndex*size, pivot) < 0) rightIndex--; if (leftIndex <= rightIndex) { _swap((char*)arr + leftIndex*size, (char*)arr + rightIndex*size, size); leftIndex++; rightIndex--; } } free(pivot); if (left < rightIndex) quickSort(arr, rightIndex, size, cmp); if (right > leftIndex) quickSort(arr, leftIndex, size, cmp); } | cs |