퀵정렬은 분활 정복 알고리즘을 기반으로 하는 정렬 알고리즘으로, 효율성과 간결함 때문에 자주 사용된다. 평균적으로 O(nlogn) 의 시간 복잡도를 가지며, 최악의 경우 O(N²)이 될 수 있지만 적절한 피벗 선택으로 최악의 경우를 피할 수 있다.
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
int pivotIndex = partition(array, low, high);
quickSort(array, low, pivotIndex - 1);
quickSort(array, pivotIndex + 1, high);
}
}
public static int partition(int[] array, int low, int high) {
int pivot = array[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
i++;
swap(array, i, j);
}
}
swap(array, i + 1, high);
return i + 1;
}
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}