QuickSort 는 분할 정복 (Divide-and-Conquer) 정렬 알고리즘입니다. 배열에서 '피벗 (pivot)' 요소를 선택하고, 다른 요소들을 피벗보다 작거나 큰 두 개의 하위 배열로 분할하여 작동합니다. 그런 다음 하위 배열을 재귀적으로 정렬합니다. QuickSort 의 평균 시간 복잡도는 O(n log n) 입니다. QuickSort 는 안정 정렬 (stable sort) 이 아니라는 점에 유의해야 합니다. 즉, 동일한 정렬 항목의 상대적인 위치가 보존되지 않을 수 있습니다.
이 단계에서는 java.util.Arrays 클래스를 가져와야 합니다. 이 클래스에는 int 배열을 String으로 변환하는 데 사용될 배열 조작을 위한 여러 메서드가 포함되어 있습니다.
import java.util.Arrays;partition()이라는 헬퍼 (helper) 메서드를 정의합니다. partition() 메서드는 배열 arr, 시작 인덱스 low, 종료 인덱스 high를 입력으로 받습니다. partition() 메서드는 피벗 (pivot) 으로 요소를 선택하고, 피벗 요소보다 작은 모든 요소가 피벗의 왼쪽에, 피벗보다 큰 모든 요소가 피벗의 오른쪽에 위치하도록 요소를 분할합니다. 피벗 요소는 올바른 위치에 배치됩니다.
partition() 메서드는 분할된 요소의 인덱스를 반환합니다. 분할된 요소는 피벗 요소가 배치된 위치입니다.
public static int partition(int[] arr, int low, int high) {
// Select the pivot element
int pivot = arr[high];
int i = (low - 1); // Index of smaller element and indicates the right position of pivot found so far
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // increment index of smaller element
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i + 1] and arr[high]
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // Return the partition index
}quicksort()라는 정렬 메서드를 정의합니다. quicksort() 메서드는 배열 arr, 시작 인덱스 low, 종료 인덱스 high를 입력으로 받습니다. quicksort() 메서드는 arr[] 배열을 재귀적으로 정렬합니다.
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi is partitioning index, arr[p] is now
// at right place
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}정렬할 정수 배열을 생성하여 arr 필드에 할당합니다.
int[] arr = {7, 9, 1, 2, 10, 15, 6};arr 필드를 입력으로 하여 배열의 시작 및 마지막 인덱스와 함께 quickSort() 메서드를 호출합니다. Arrays.toString(arr) 메서드를 사용하여 배열을 정렬하고 표시합니다.
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));다양한 특성을 가진 배열을 사용하여 QuickSort 구현을 테스트합니다.
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));이 단계에서는 최악의 시나리오를 피하기 위해 각 반복마다 피벗을 무작위로 선택해야 합니다. 이를 위해 partition() 메서드를 업데이트하고 다음 줄을 대체합니다.
int pivot = arr[high];다음 줄로:
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;무작위 피벗 요소를 사용하여 QuickSort 구현을 테스트합니다.
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));이 단계에서는 QuickSort 가 처리할 수 있는 엣지 케이스를 다룹니다. 이러한 엣지 케이스를 정수 배열로 정의합니다.
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));Java Lab 에서 QuickSort 의 전체 코드는 다음과 같습니다.
import java.util.Arrays;
public class QuickSort {
public static int partition(int[] arr, int low, int high) {
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;
int i = low - 1;
for (int j = low; j <= high - 1; ++j) {
if (arr[j] <= pivot) {
++i;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void quickSort(int[] arr, int low, int high) {
if (low >= high) {
return;
}
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
public static void main(String[] args) {
System.out.println("Quick Sort Implementation in Java\n-----------------------");
int[] arr = {7, 9, 1, 2, 10, 15, 6};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));
}
}이 Lab 에서는 Java 에서 QuickSort 알고리즘을 구현하는 단계별 가이드를 제공했습니다. QuickSort 에서 피벗 (pivot) 선택이 중요한 단계이며, 피벗을 선택하는 다양한 기술이 알고리즘의 성능에 영향을 미칠 수 있다는 것을 배웠습니다. QuickSort 는 대량의 데이터를 정렬하는 데 가장 적합합니다. QuickSort 의 최악 시간 복잡도는 O(N^2) 인 반면, 평균 및 최선 시간 복잡도는 O(NLogN) 입니다.
