QuickSort doesn’t require extra space, average time is O(nlgn).

Idea:

- Pick a pivot and sort all elements in the array that are smaller than the pivot to the left of the chosen pivot, and all that are bigger than the pivot to the right of it
- recursively sort two sublists
- Note: the pivot could be chosen in multiple ways:
- you can pick
*first*element in the array - you can pick
*last*element in the array - you can pick
*median*element in the array - you can pick
*random*element in the array

- you can pick
- The pivot you pick could result in completely different sorting efficiency under extreme cases: http://stackoverflow.com/questions/2415193/worst-case-for-quicksort-when-can-it-occur

The following *partition()* method takes the last element as the pivot. In its *partition() *method: it sets the last element as the pivot, then it keeps an index i = low-1, then use another index j to loop through all elements from *low* to *high-1*, when we find any element nums[j] that is smaller than or equal to pivot (i.e. nums[high]), ** we increment i by 1 first**, then we swap nums[j] with nums[i], notice, we swap nums[j] with

*, not with nums[high] or anything else, we swap nums[high] after we finish iterating through*

**nums[i]***low*to

*high-1*, this is to do this: place all elements that are smaller than the pivot to the

*of the pivot, after iterating through from*

**left***low*to

*high-1*, we swap nums[i+1] with nums[high], this is to place nums[high] (i.e. current pivot) to the correct position, then we return i+1 as the pivot as all elements from

*low*to

*i*are sorted already.

I put my *partition()* function into this site and it’s accepted: http://www.practice.geeksforgeeks.org/problem-page.php?pid=700151

int[] quickSort_20160628(int[] nums){ quickSort_20160628(nums, 0, nums.length-1); return nums; } void quickSort_20160628(int[] nums, int low, int high) { if(low < high){ int pi = partition_20160628(nums, low, high); quickSort_20160628(nums, low, pi-1); quickSort_20160628(nums, pi+1, high); } } int partition_20160628(int[] nums, int low, int high) { int pivot = nums[high]; int i = low-1; for(int j = low; j <= high-1; j++){ if(nums[j] <= pivot){ i++; int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } int temp = nums[i+1]; nums[i+1] = nums[high]; nums[high] = temp; return i+1; }

Then, just out of curiosity, I followed the same pattern, implemented the *partition()* function by picking the first element as the pivot, similar idea in the *partition()* function: similar to the *partition() *function in choosing last as pivot where it uses a for loop to find all elements that are smaller than pivot to place them to the left most possible, this *partition_pivot_first_20160628*I() function uses a for loop to find all elements that are bigger than the chosen pivot and places them to the right most possible.

Cool! I figured this partition method myself by completely understanding it first. Praise the Lord!

Also, don’t forget to put if(low < high){} at the main function!!! Otherwise, it won’t work!

It’s also accepted here: http://www.practice.geeksforgeeks.org/problem-page.php?pid=700151

int[] quickSort_pivot_first_20160628(int[] nums){ quickSort_pivot_first_20160628(nums, 0, nums.length-1); return nums; } private void quickSort_pivot_first_20160628(int[] nums, int low, int high) { if (low < high) { int pi = partition_pivot_first_20160628(nums, low, high); quickSort_pivot_first_20160628(nums, low, pi - 1); quickSort_pivot_first_20160628(nums, pi + 1, high); } } private int partition_pivot_first_20160628(int[] nums, int low, int high) { int pivot = nums[low]; int i = high+1; for(int j = high; j > low; j--){ if(nums[j] > pivot){ i--; int temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; } } int temp = nums[low]; nums[low] = nums[i-1]; nums[i-1] = temp; return i-1; }

Implement quickSort() that takes median element as the pivot, it’s a bit different from the previous two, just in the way it’s written: it doesn’t use one more help function: *partition()*, instead, it uses just one function which does both recursion and partition. The fundamental idea behind the three is definitely the same: keep picking one element as pivot, keep placing all elements in the array that are smaller than the pivot to the left of the pivot and those that are bigger to the right.

int[] quickSort_pivot_median_20160628(int[] nums){ quickSort_pivot_median_20160628(nums, 0, nums.length-1); return nums; } void quickSort_pivot_median_20160628(int[] nums, int low, int high) { if(nums == null || nums.length == 0) return ; if(low >= high) return; int i = low, j = high, mid = (low+high)/2, pivot = nums[mid]; while(i <= j){ while(nums[i] < pivot) i++; while(nums[j] > pivot) j--; if(i <= j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; i++; j--; } } if(low < j) quickSort_pivot_median_20160628(nums, low, j); if(i < high) quickSort_pivot_median_20160628(nums, i, high); }