Quicksort is a divide and conquer algorithm. It first divides a large list into two smaller sub-lists and then recursively sort the two sub-lists. If we want to sort an array without any extra space, quicksort is a good option. On average, time complexity is O(n log(n)).
The basic step of sorting an array are as follows:
- Select a pivot
- Move smaller elements to the left and move bigger elements to the right of the pivot
- Recursively sort left part and right part
This post shows two versions of the Java implementation. The first one picks the rightmost element as the pivot and the second one picks the middle element as the pivot.
Version 1: Rightmost element as pivot
The following is the Java Implementation using rightmost element as the pivot.
public class QuickSort {
public static void main(String[] args) {
int[] arr = {4, 5, 1, 2, 3, 3};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int start, int end){
int partition = partition(arr, start, end);
if(partition-1>start) {
quickSort(arr, start, partition - 1);
}
if(partition+1<end) {
quickSort(arr, partition + 1, end);
}
}
public static int partition(int[] arr, int start, int end){
int pivot = arr[end];
for(int i=start; i<end; i++){
if(arr[i]<pivot){
int temp= arr[start];
arr[start]=arr[i];
arr[i]=temp;
start++;
}
}
int temp = arr[start];
arr[start] = pivot;
arr[end] = temp;
return start;
}
} |
You can use the example below to go through the code.
Version 2: Middle element as pivot
public class QuickSort {
public static void main(String[] args) {
int[] x = { 9, 2, 4, 7, 3, 7, 10 };
System.out.println(Arrays.toString(x));
int low = 0;
int high = x.length - 1;
quickSort(x, low, high);
System.out.println(Arrays.toString(x));
}
public static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length == 0)
return;
if (low >= high)
return;
// pick the pivot
int middle = low + (high - low) / 2;
int pivot = arr[middle];
// make left < pivot and right > pivot
int i = low, j = high;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// recursively sort two sub parts
if (low < j)
quickSort(arr, low, j);
if (high > i)
quickSort(arr, i, high);
}
} |
Output:
9 2 4 7 3 7 10
2 3 4 7 7 9 10
Here is a very good animation of quicksort.
ref: https://www.programcreek.com/2012/11/quicksort-array-in-java/
Người đăng 
EmoticonEmoticon