This post was originally posted on my blog

preface

This series includes ten classic sorting algorithms.

  • The language used is Java
  • The structure is: define abstract classesSortIt implements swap, size comparison and so on. For example, if you swap two values, just pass in the subscript. All other concretely sorted classes inherit from abstract classesSort. So we can focus on the algorithm itself.
/* * Return value is 0, indicating array[i1] == array[i2] * return value is less than 0, indicating array[i1] < array[i2] * return value is greater than 0, indicating array[i1] < array[i2] * return value is greater than 0. Array [i1] > array[i2] */ protected int CMP (int i1, int i2) {return array[i1].compareTo(array[i2]);
	}
	
	protected int cmp(T v1, T v2) {
		return v1.compareTo(v2);
	}
	
	protected void swap(int i1, int i2) {
		T tmp = array[i1];
		array[i1] = array[i2];
		array[i2] = tmp;
	}

Copy the code

What is quicksort

  • Quicksort is an improvement on bubbling sort. Quicksort was proposed by C. A. R. Hoare in 1960. Its basic idea is: by a trip to sort to sort data split into separate two parts, one part of all the data are smaller than the other part of all data, and then of the two parts data respectively according to the method of quick sort, the entire sorting process can be recursive, to achieve the whole data into an orderly sequence

Algorithm thought

Quicksort algorithm realizes sorting through multiple comparison and exchange, and its sorting process is as follows:

  • We start by setting a boundary that divides the array into left and right parts.

  • Centralize data greater than or equal to the boundary to the right of the array, and data less than the boundary to the left of the array. At this point, each element in the left part is less than or equal to the boundary value, and each element in the right part is greater than or equal to the boundary value.

  • Then, the data on the left and right can be sorted independently. For the left side of the array, you can take a boundary value and divide that part of the data into left and right parts, again placing a smaller value on the left and a larger value on the right. The array data on the right can be treated similarly.

  • Repeat the above process, and you can see that this is a recursive definition. After recursively ordering the left side, recursively ordering the right side. When the sorting of the left and right parts of the data is complete, the sorting of the entire array is complete.

Algorithm analysis

Time complexity

  • In the case of a fairly uniform number of elements around the axis, which is also the best case O(nlogn)
  • If the number of elements around the axis is extremely uneven, the worst case is O(n^2).
  • In order to reduce the probability of the worst case, axis elements are selected randomly

Spatial complexity

  • The reason for recursive calls is order nlogn in space.

Algorithm stability

  • Quicksort is an unstable sorting algorithm.

Is it in place

  • What is the in situ algorithm?
    • Not dependent on additional resources or on a few additional resources, relying only on the output to override the input
    • The spatial complexity of 𝑂(1) can be considered as in situ algorithm
  • The non-in-situ algorithm is called not-in-place or out-of-place
  • Quicksort is in-place

code

Code logic

  • Select a pivot point element from the sequence (Pivot)

    • Let’s say I pick the element at position 0 every time

  • Using pivot, the sequence is divided into 2 subsequences

    • Place the element less than pivot to the left of pivot
    • Place the element greater than pivot to the right of pivot
    • The element equal to Pivot can be placed on either side

  • Perform the previous two steps on the subsequence until it can no longer be split (only one element is left in the subsequence)

  • The nature of quicksort

    • Gradually convert each element into an axis point element
package YZ.Sort;

public class QuickSort<T extends Comparable<T>> extends Sort<T>   {

	@Override
	protected void sort() { sort(0, array.length); * @param begin * @param end */ private void sort(int begin,int end) {private void sort(int begin,int end) {if (end-begin<2) {
			return; O(n) int mid = pivotIndex(begin, end); Sort (begin,mid); sort(mid+1, end); } /** * constructs the axis element * @ in the range [begin, end]return*/ private int pivotIndex(int begin,int end) {// Select a pivotIndex(int begin,int end) to swap(begin, begin+(int)Math.random()*(end-begin)); T pivot = array[begin]; end--;while (begin<end) {
			while (begin<end) {
				if(CMP (pivot, array[end])<0) {// Right element > end--; }else{// right element <= array[begin++] = array[end];break; //breakExit, start from the other side}}while (begin<end) {
				if(CMP (pivot, array[begin])>0) {// Start ++; }else{// Left element >= array[end--] = array[begin];break; //breakExit, starting from the other side (end)}}} // Place the backup pivot element in the final position array[begin] = pivot; // Returns the position of the pivot elementreturnbegin; }}Copy the code

validation

Use the following data source

Integer[] array = Integers.random(20000, 1, 80000);

The result is:

【BubbleSort】 Stability: true Time: 2.494s(2494ms

BubbleSort1 Stability: true Time: 1.95s(1950ms) Comparison number: 200 million swap number: 99508,400

[BubbleSort2] Stability: true Time: 2.048s(2048ms

[InsertionSort1] Stability: true Time: 1.125s(1125ms) Comparison times: 995.28,400 exchange times: 995.508,400

[InsertionSort2] Stability: true Time: 0.772s(772ms) Comparison times: 995.28,400 exchange times: 0

[InsertionSort3] Stability: true Time: 0.546s(546ms) Comparison times: 25800 exchange times: 0

Stability: true Time: 0.458s(458ms) Comparison times: 200 million exchange times: 200 million

【HeapSort】 Stability: false Time: 0.013s(13ms) Comparison number: 510,800 exchange number: 20000

[QuickSort] Stability: false Time: 0.01s(10ms) Comparison count: 3200000 Exchange count: 13,200

[MergeSort] Stability: true Time: 0.011s(11ms) Comparison times: 260,800 exchange times: 0

It turns out that quicksort performance is pretty good.

The code address

  • The code in git is at github