This is the fifth day of my participation in the August Wen Challenge.More challenges in August

Abstract

Quicksort and merge sort have something in common, in that they split it in the middle and do it separately.

So this is also a recursive idea, but unlike merge sort, which is sort and then sort, quicksort is sort and then split.

nature

Each time you identify a pivot element, compare it to the other elements in the sequence and place it anywhere to the left or right of the element. Once you’re done, you know where the pivot element is.

Understanding this fast should be to fix the position of one element, regardless of the position of other elements, without comparison processing (because of the unfeeling, so fast? – My understanding)

logic

  1. Select an element in the sequence and set it to pivot element
  2. The sequence is split into two sub-sequences using pivot
    • Place the element less than Pivot to the left of the sequence
    • Place the element greater than pivot to the right of the sequence
    • You can place the element equal to pivot on either the left or the right
  3. The subsequence continues to perform the preceding 1 and 2 operations until it can no longer be divided

process

  1. Take 0 coordinate as axis point, randomly obtain axis point element, and 0 position element replacement
  2. Compare and adjust the substitution of the beginning and end elements with the axis point elements. Place the elements smaller than the axis point to the left of the axis point coordinate and the elements larger than the axis point to the right of the axis point coordinate.
  3. Take the axis element as the center line, split into two sub-sequences, continue 1 and 2 operations (recursive properties)
  4. Until the beginning and end coordinates are equal (that is, there is only one element in the sequence)

implementation

A recursive method of dividing a sequence into subsequences. All recursive methods must have the judgment condition to terminate recursion, otherwise it will cause an endless loop, which needs special attention

	/** * compare within [begin, end] *@param begin
	 * @param end
	 */
	private void sort(int begin, int end) {
		if ((end - begin) < 2) return;
		
		int mid = pivotIndex(begin, end);
		// Split into two subsequences
		sort(begin, mid);
		sort(mid+1, end);
	}
Copy the code

Adjusts the elements in the sequence by dividing lines with the axis coordinates and returns the new axis coordinates. Be sure to assign the axis point element to the new axis point coordinate when the comparison has been completed.

One neat thing about this code is that it compares and swaps the header and tail positions

There is a very clever way of nesting two small loops with a large loop, so that the head and tail can be compared and swapped with the pivot elements.

First of all, we need to clarify the purpose, which is that the elements in the sequence smaller than the axis are placed to its left, and the elements larger than the axis are placed to its right. Without adding extra memory, you can do it this way.

The logic can be focused on the code, here are a few points to note

  1. The comparison here is head to tail, using three while loops to do so
  2. Begin and end are like two Pointers that swap and then switch the direction of the comparison, which is very clever.
	/** * returns the inner construct axis point coordinates * at [begin, end]@param begin
	 * @param end
	 * @return* /
	private int pivotIndex(int begin, int end) {
		// Get the coordinates (begin and end) from a random number and swap them with the BEGIN coordinate element to avoid 2^n
		swap(begin, begin + (int)(Math.random()*(end - begin)));
		// Pivot point elements
		E pivot = array[begin];
		
		// end refers to the last element
		end--;
		
		// compare head and tail alternately
		while (begin < end) {
			// compare the tail
			while (begin < end) {
				if (cmp(pivot, array[end]) < 0) {
					end--;
				} else {
					array[begin] = array[end];
					begin++;
					break; }}// Header comparison
			while (begin < end) {
				if (cmp(pivot, array[begin]) > 0) {
					begin ++;
				} else {
					array[end] = array[begin];
					end--;
					break; }}}// Place the pivot element in its final position
		array[begin] = pivot;
		return begin;
	}
Copy the code

The problem

Q: Why do we start by getting a random element in the sequence and swapping it with the axis coordinate element?

A: To prevent extreme uneven number of elements around the axis point

Q: How and why are sequence boundaries set?

A: The sequence boundary is [begin, end), close left and open right. This setting is convenient to obtain the length of the sequence, and the last coordinate can also be easily obtained

The advanced

Select the pivot element at random. This is to prevent extreme cases such as sequences being ordered from large to small.

Time and space complexity

  • Best, average time complexity: O(nlogn)
  • Worst time complexity: O(n^2)
  • Space complexity: O(logn)
  • It’s an unstable sort