퀵 정렬, 퀵 소트(Quick Sort)

퀵 정렬, 퀵 소트(Quick Sort)

QuickSort.java

import java.util.Arrays; import java.util.Random; /** * QuickSort * Time Complecty : O (n log(n)) * @author atin84 * */ public class QuickSort { public void sort(int[] data, int left, int right) { // 1. pivot은 중간값을 지정 int pivot = data[(left + right) / 2]; // 내부 사용 변수 설정 int leftIndex = left; int rightIndex = right; int temp = 0; // 2. leftIndex와 rightIndex가 만날 때까지 반복 while (leftIndex < rightIndex) { // 3. left값이 pivot보다 작으면 +1 while (data[leftIndex] < pivot) leftIndex++; // 4. right값이 right보다 크면 -1 while (data[rightIndex] > pivot) rightIndex--; // 5. 데이터가 클 경우 swap 처리 if (leftIndex < rightIndex) { temp = data[leftIndex]; data[leftIndex] = data[rightIndex]; data[rightIndex] = temp; } // 6. 데이터가 크거나 같을 때 index if (leftIndex <= rightIndex) { leftIndex++; rightIndex--; } } if (left < rightIndex) { sort(data, left, rightIndex); } if (leftIndex < right) { sort(data, leftIndex, right); } } public static boolean isSorted(int[] data) { int count = data.length - 1; for (int i = 0; i < count; i++) { if (data[i] > data[i + 1]) { return false; } } return true; } public static void main(String args[]) { int count = 100; Random random = new Random(); int[] sortedArray = new int[count]; for (int i = 0; i < count; i++) { sortedArray[i] = random.nextInt(1000); } System.out.print("Before : "); System.out.println(Arrays.toString(sortedArray)); System.out.println(); QuickSort quickSort = new QuickSort(); quickSort.sort(sortedArray, 0, sortedArray.length - 1); System.out.print("After : "); System.out.println(Arrays.toString(sortedArray)); System.out.println(); System.out.println("isSorted : " + isSorted(sortedArray)); } }