Suppose we have the following array and want to sort it using quicksort: [10, 23, 15, 7, 18, 3, 15, 10, 28] The array has nine elements. The quicksort process is basically as follows:

  1. Select a segmentation value;
  2. Place elements less than or equal to the split value before it, and elements greater than or equal to the split value after it;
  3. Determine the index of the segmentation value in the ordered sequence; For example, if we choose 18 as the partition value, then after sorting ([3, 7, 10, 10, 15, 15, 18, 23, 28]), the number of 18 should be 6.
  4. Use recursion to sort the elements before and after the split value.

The whole idea of quicksort isn’t hard, but there are some special cases to consider if you’re writing code by hand:

  • The selected split value is either the maximum or minimum value of the array;
  • When there are equal elements in the array.

Quicksort analysis

Steps 2 and 3 mentioned above are partitions in the algorithm code. Imagine that we use the left and right cursors to rank elements less than or equal to the split value before it, and elements greater than or equal to the split value after it, by moving the cursor and comparing it to the split value.

The selected split value is not a maximum or minimum

[10, 23, 15, 7, 28, 3, 15, 10, 18]

  1. 18 is the split value, moved to the end of the array;
  2. The left cursor moves from left to right to find the first element (23) greater than the split value. The left cursor moves from index 0 to index 1.
  3. The right cursor moves from right to left to find the first element (10) less than the split value, whose index is 7;
  4. Switch 23 with 10, and the array becomes[10, 10, 15, 7, 28, 3, 15, 23, 18];
  5. The left cursor continues to the right to find the next element (28) greater than the split value and moves from index 1 to index 4;
  6. The right cursor continues to the left to find the next element (15) less than the split value and moves from index 7 to index 6;
  7. Switch 28 with 15, and the array becomes[10, 10, 15, 7, 15, 3, 28, 23, 18];
  8. The left cursor continues to the right to find the next element (28) greater than the split value and moves from index 4 to index 6;
  9. The right cursor continues to the left to find the next element (3) less than the split value and moves from index 6 to index 5;
  10. At this point, the index of the left cursor is greater than that of the right cursor, and the movement stops.
  11. At this point, all elements before the left cursor are less than or equal to the split value, and all elements behind the left cursor are greater than or equal to the split value.
  12. Divide the values of 18 withThe left cursor28 counterpoint (note here,The split value is swapped with the element indicated by the left cursor), the array becomes[10, 10, 15, 7, 15, 3, 18, 23, 28];
  13. The index of the left cursor is the final number of the split value we are looking for. In other words, the split value of 18, in the final sorted array, index must be 6.
  14. At last, we use recursion to quickly sort the array elements [0 ~ 5] and [7 ~ 8].

The selected split value is the maximum

[10, 23, 15, 7, 18, 3, 15, 10, 28]

  1. 28 was selected as the segmentation value;
  2. The left cursor moves to the end of the array (index = 8) as the first element greater than 28 is searched from left to right.
  3. The right cursor, moving from right to left, looks for the first element (10) less than 28 whose index = 7;
  4. However, since the index of the left cursor is greater than the index of the right cursor, the elements pointed to by the left cursor are not switched, so the split value is switched with 28 pointed to by the left cursor. The reason for the swap here is that, through the subsequent analysis, we can draw a conclusion that the split value is always swapped with the element pointed to by the left cursor, regardless of whether the maximum or minimum value is selected. This facilitates code writing and reduces discussion of special cases within the code.
  5. The final ordinal of the partition value 28 is index 8;
  6. Use recursion to quickly sort array elements [0 ~ 7].

The selected split value is the minimum

[10, 23, 15, 7, 18, 3, 15, 10, 28]

  1. Take 10 as the split value, and move 10 to the end of the array, and the array becomes[28, 23, 15, 7, 18, 3, 15, 10, 10];
  2. Left cursor, from left to right, finds the first element (28) greater than 10 with index = 0;
  3. The right cursor, moving from right to left, searches for the first element (10) less than 10.
  4. The left and right cursor stops moving, and the split value is switched with the left cursor pointing to 28 (again, the left cursor). The index of the left cursor is the index of the split value 10 after the array is finally sorted.
  5. Use recursion to quickly sort array elements [1 ~ 8].

When all elements of an array are equal

[10, 10, 10, 10, 10]

  1. Select an arbitrary index element as the split value, and move to the end of the array;
  2. Left cursor, moving from left to right, searches for the first element greater than 10, fails, moves to index 4;
  3. The right cursor, moving from right to left, searches for the first element less than 10, fails, and moves to the left end of the array;
  4. The left and right cursor stops moving, and the split value is switched with the 10 indicated by the left cursor (again, the left cursor);
  5. Use recursion to quickly sort array elements with serial number [0 ~ 3].

Code implementation

Java version

Partition is the most tricky part of the code. Here is the Java version of the code implementation, in this version, the split value is randomly selected; If you don’t pick randomly, you can split the last element of the array each time, so that you can just delete the choosePivot code.

import java.util.Arrays;
import java.lang.Math;

public class QuickSort {
	/ / swap function
	public static void swap(int[] arr, int first, int second) {
		int temp = arr[first]; 
		arr[first] = arr[second]; 
		arr[second] = temp; 
	} 
	
	// Choose a random pivot
	public static void choosePivot(int[] arr, int start, int end) {
		int random = (int) (Math.random() * (end - start + 1)); 
		int randomPivot = start + random; 
		
		// Place the randomly selected split value at the end of the array
		swap(arr, randomPivot, end); 
	}

	// Find the final index of the split value
	public static int partition(int[] arr, int start, int end) {		
		// Left and right cursor
		int i = start, j = end - 1; 
		// Switch the left and right cursor elements
		while(true) {
			// Left cursor, from left to right, to find the element greater than the split value
			// Ensure that the index of the left cursor cannot exceed the maximum index of the array
			while(i < end && arr[i] <= arr[end]) {
				i++; 
			} 
			
			// Right cursor, from right to left, to find the element less than the split value
			// Note that the index of the right cursor can be at least -1
			while(j >= 0 && arr[j] >= arr[end]) {
				j--; 
			}
			
			// If the index of the left cursor is greater than the index of the right cursor, do not switch left and right
			if(i > j) break; 
			// Otherwise, switch left and right to continue looking for elements on both sides of the split value
			swap(arr, i, j); 
		} 
		
		// Swap the split value with the element indicated by the left cursor
		swap(arr, end, i); 
		// return index of the left cursor
		return i; 
	}
	
	// quick sort
	public static void quickSort(int[] arr, int start, int end) {
		// Base condition of the recursion
		if(start >= end) return; 

		// Randomly select the segmentation value
		choosePivot(arr, start, end); 
		
		// Find the final index of the split value
		int i = partition(arr, start, end); 

		// Use recursion to quickly sort the array elements around the split value
		quickSort(arr, start, i - 1);
		quickSort(arr, i + 1, end); 
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = {15.3.23.26.28.26.15.3.29.34}; 
		System.out.println("Before quick sort: " + Arrays.toString(arr)); 

		quickSort(arr, 0, arr.length - 1); 

		System.out.println("After quick sort: "+ Arrays.toString(arr)); }}Copy the code

The JavaScript version

function swap(arr, left, right) {
    let temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

function partition(arr, start, end) {
    let left = start;
    let right = end - 1;

    while (true) {
        while (left < end && arr[left] <= arr[end]) left++;

        while (right >= start && arr[right] >= arr[end]) right--;

        if (left > right) break;
        swap(arr, left, right);
    }

    swap(arr, end, left);
    return left;
}

function quickSort(arr, start, end) {
    if (start >= end) return;

    let i = partition(arr, start, end);

    quickSort(arr, start, i - 1);
    quickSort(arr, i + 1, end);
}

let arr = [15.3.23.7.15.19.76.32.0.21];

quickSort(arr, 0, arr.length - 1);
console.log("After sort: " + arr);
Copy the code