# 快速排序法 QuickSort

###### tags: `leetcode`,`sorting`

>ref: https://github.com/chmonk/leetCodeTraining/blob/dev/src/sort/quickSort.java
>

## 基礎流程

1. 利用數列中最前或最後的idx作為pivot(比較基準),由此pivot將該數列分類,理想的pivot為該數列之數值排列中位數(此情況為time resolution為 O(n log~2~n),最差的情形為該數列已經過排序,每次分組取到的pivot皆為該數組之極值,此情況下為 O(n^2^)以上

2. TR, 比較行為為n次(每數組需要跟pivot比較), 依據分組情況最優化為log~2~n組=>O(nlog~2~n), 最差為分組n次(每次分組為極值一個與剩餘情況)=>O(n^2^)

	public void quickSort(int[] nums, int start_idx, int end_idx) {

		// termination condition
		if (end_idx - start_idx < 1) {
			return;
		}

		//use the last idx as pivot 
		int pivot = nums[end_idx];

		int lower_idx = start_idx;

		for (int loop_idx = start_idx; loop_idx < end_idx; loop_idx++) {
			//while the number smaller than pivot,replace this num to the lower_idx
			if (nums[loop_idx] < pivot) {
				swap(nums, lower_idx, loop_idx);
				lower_idx++;
			}
		}

		swap(nums, lower_idx, end_idx);

		// number array idx lower than lower_idx are smaller than the pivot 
		quickSort(nums, start_idx, lower_idx - 1);

		// number array idx larger than lower_idx are larger than the pivot 
		quickSort(nums, lower_idx + 1, end_idx);

	}

	private void swap(int[] nums, int a, int b) {
		int record = nums[a];
		nums[a] = nums[b];
		nums[b] = record;
	}

## 進階:優化
1. pivot選擇中間數
2. 當數列中有數字與pivot相同時,集中於數列內連續排列,並不進行到下次的子排序

	public void quickSort_dual(int[] nums, int start_idx, int end_idx) {

		// termination condition
		if (start_idx >= end_idx) {
			return;
		}

		int middle_idx = start_idx + (end_idx - start_idx) / 2; //avoid big number

		int pivot_idx = end_idx;

		//use the middle value as pivot to separate the array 
		if (nums[start_idx] > nums[middle_idx]) {
			swap(nums, start_idx, middle_idx);
		}
		if (nums[end_idx] < nums[middle_idx]) {
			swap(nums, end_idx, middle_idx); 
		}
		if (nums[start_idx] > nums[middle_idx]) {
			swap(nums, start_idx, middle_idx);
		}
		swap(nums, end_idx, middle_idx);

		int low = start_idx;
		int high = end_idx - 1; // leave pivot as standard
		
		int loop_idx = start_idx;

		while (loop_idx <= high) {

			if (nums[loop_idx] < nums[pivot_idx]) {
				// < pivot , exchange with the nums[++low] (exchange with the number bigger than
				// pivot),loop++
				swap(nums, low++, loop_idx++);
			} else if (nums[loop_idx] == nums[pivot_idx]) {
				// == pivot , loop++
				loop_idx++;
			} else {
				// >pivot exchange with the nums[high] and loop_idx don't ++ for check the
				swap(nums, high--, loop_idx);
			}
		}

		swap(nums, ++high, pivot_idx); // put the pivot value in the middle 

		quickSort_dual(nums, start_idx, --low); //owing to low++, in the end, now the low idx is the pivot value, so --low 

		quickSort_dual(nums, ++high, end_idx); // in the end, high idx is the pivot, ++high lead to high point to the number larger than pivot

	}