Quick Sort

public class QuickSorts {
	private void swap(int[] array, int firstIndex, int secondIndex) {
		int temp = array[firstIndex];
		array[firstIndex] = array[secondIndex];
		array[secondIndex] = temp;
	}

	private int pivot(int[] array, int pivotIndex, int endIndex) {
		int swapIndex = pivotIndex;
		for (int i = pivotIndex + 1; i <= endIndex; i++) {
			if (array[i] < array[pivotIndex]) {
				swapIndex++;
				swap(array, swapIndex, i);
			}
		}
		swap(array, pivotIndex, swapIndex);
		return swapIndex;
	}

	public void quickSort(int[] array, int left, int right) {
		if (left < right) {
			int pivotIndex = pivot(array, left, right);
			quickSort(array, left, pivotIndex - 1); // recursive
			quickSort(array, pivotIndex + 1, right); // recursive 
		}
	}
}

• pivot 메서드는 helper function (muck like 'merge function' was for a merged sort)
• pivot은 array에서 중간 인덱스/값
• 그렇지만 swap을 반환한다
• {4, 6, 1, 7, 3, 2, 5} 라는 배열을 정렬. 그런데 pivot 함수만 실행하면 {2, 1, 3, 4, 6, 7, 5}가 나옴. 일단 Pivot = 4. 여기서 피봇을 중심으로 left, right으로 나누어 재귀로 다시 quickSort 함수를 실행.
• 배열의 아이템을 일일이 탐색하는 과정과 divide and conquer 두 가지 과정이 수행되므로 Big O는 O(n log n).
• quick sort는 아이템들이 완전 랜덤하게 있을 때는 유용하지만 이미 much sorted 되어 있는 경우에는 그다지 유용하지 않음. 그럴 때는 차라리 insertion sort 같은 것을 쓰는 것이 나음.