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

  • Bubble, select, insert, merge, hill, and heap sort are all comparison based sorts

    • Minimum average time complexity O(nlogn)

  • Counting sort, bucket sort, and radix sort are not comparison – based sorts

    • Using space for time, sometimes the average time complexity can be less than order nlogn.

What is radix sort

  • Radix sort belongs to “distribution sort”, also called “bucket sort” or “bin sort”, as its name implies, it allocates the sorted elements to some “buckets” through partial information of key values. Radix sort is a stable sort, whose time complexity is O (nlog(r)m), where R is the radix taken and M is the number of heaps. In some cases, radix sort is more efficient than other stability sort

Implementation method

  • MSD method (Most Significant Digit First) : In the same group, the key codes k1 are equal, and then the groups are sorted into subgroups according to K2. After that, the following key codes are sorted into subgroups until the subgroups are sorted according to the lowest key code KD. Then connect the groups together to get an ordered sequence.
  • The Least Significant Digit first method, referred to as LSD method: firstly sort from kd, then sort kD-1, repeat in turn, until k1 is sorted and then an ordered sequence is obtained.

Algorithm thought

The first step

Taking LSD as an example, suppose you had a string of values as follows:

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

First, assign values from the units digit to buckets numbered 0 through 9 as values are visited:

0 1 81 2 22 3 73 93 43 4 14 5 55 65 6 7 8 28 9Copy the code

The second step

The values in these buckets are then reconcatenated to form the following sequence:

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

Then the allocation is made again, this time by ten digits:

0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
Copy the code

The third step

The values in these buckets are then reconcatenated to form the following sequence:

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

At this point the whole sequence is sorted; If the sorted object has more than three digits, the above actions continue until the highest digit is reached.

  • LSD’s radix sort is suitable for sequences with small bits, and MSD is more efficient if the number of bits is large. MSD is the opposite of LSD in that it starts with a high digit base and does not immediately merge it back into an array. Instead, it creates “buckets” in each bucket and assigns the value in each bucket to the next digit. After allocating the lowest number of digits, merge it back into a single array.

Algorithm stability

  • Radix sort is a stable sort 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
  • Radix sorts are not in-place

Space-time complexity

  • Best, Worst, average time complexity: O(d*(n+k))

    • D is the largest number of digits and k is base

  • Space complexity: O(n+ K)

code

  • In the counting sort of the ten sorting algorithms, the simplest implementation is first used to find the maximum value, used to create an array, and then iterated out, counting the number of elements, and finally in accordance with the order of assignment

  • Radix sort internal implementation can use counting sort ideas

package YZ.Sort;

public class RadixSort extends Sort<Integer> {

	@Override
	protected void sort() {
		int max = array[0];
		for (int i = 1; i < array.length; i++) {
			if(array[i]>max) { max = array[i]; }} // Single digit: Array [I] / 1%10 = 3 // ten: array[I] / 10%10 = 9 // hundreds: array[I] / 100%10 = 5 // thousands: array[I] / 1000%10 =...for(int divider = 1; divider <= max; divider*=10) { sort(divider); }} protected void sort(int Divider) {// TODO auto-generated method stub // Open memory space, save times int[] counts = new int[10]; // Count the number of occurrences of each integerfor(int i = 0; i < array.length; i++) { counts[array[i]/divider%10]++; }// O(n) // summation timesfor(int i = 1; i < counts.length; i++) { counts[i]+= counts[i-1]; Int [] newArray = new int[array.length];for(int i = array.length-1; i >=0 ; I --) {// Get the index of the element in counts int index = array[I]/ Divider %10; //count [index]; NewArray [--counts[index]] = array[I]; } // Assign an ordered array to arrayfor(int i = 0; i < newArray.length; i++) { array[i] = newArray[i]; }}}Copy the code

The results of

Data sources:

Generate 20000 data randomly from 1 to 80,000 to test

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

The results are as follows

[CountingSort] Stability: true Time: 0.005s(5ms) Comparison count: 0 Exchange count: 0

[QuickSort] Stability: false Time: 0.009s(9ms) Comparison count: 332,700 Exchange count: 13,200

[MergeSort] Stability: true Time: 0.01s(10ms) Comparison times: 261,000 exchange times: 0

【RadixSort】 Stability: true Time: 0.014s(14ms) Comparison times: 0 exchange times: 0

[ShellSort] Stability: false Time: 0.016s(16ms) Comparison times: 433,400 exchange times: 0

【HeapSort】 Stability: false Time: 0.023s(23ms) Comparison number: 510,900 exchange number: 20000

Stability: true Time: 0.514s(514ms) Comparison times: 200 million exchange times: 200 million

[InsertionSort1] Stability: true Time-consuming: 1.362s(1362ms) Comparison times: 99351,500 exchange times: 99331,500

[BubbleSort] Stability: True Time: 2.529s(2529ms) Compare times: 200 million swap times: 99331,500

Code Address:

  • The code in git is at github