This is the 17th day of my participation in the August Challenge
Comparison of sorting algorithms
In terms of time complexity
Simple selection sort, direct insertion sort bubble sort and the average of time complexity is O (n ^ 2), and the implementation process is relatively simple, but direct insertion sort bubble sort and the best cases, the time complexity of time complexity O (n) can be achieved, while simple selection sort has nothing to do with the sequence of the initial state. As an extension of insertion sort, Hill sort can achieve high efficiency for large scale sorting, but its exact asymptotic time is not obtained at present. Heap sort takes advantage of a data structure called a heap, which can be built in linear time. And the sorting process is done in order nlog2n. Quicksort is based on the idea of divide-and-conquer. Although the worst case of quicksort time will reach O(N ^ 2), but the average performance of quicksort can reach O(N log2n), which is often superior to other sorting algorithms in practical applications. Merge sort is also based on the idea of divide-and-conquer, but its best, worst and average time complexity are O(nlog2n) because its split sub-sequence is independent of the initial sequence.
In terms of spatial complexity
Simple selection sort, insertion sort, bubble sort, Hill sort, and heap sort all require only constant auxiliary space. Quicksort uses only a small auxiliary stack in space for recursion, with an average size of O(log2n), although it may grow to O(n) in the worst case. In the merge operation, two-way merge sort needs more auxiliary space for element replication, with a size of O(n). Although there are methods to overcome this shortcoming, the cost is that the algorithm will be very complicated and the time complexity will increase.
In terms of stability
Insertion sort, bubble sort, merge sort and radix sort are stable sorting methods, while simple selection sort, quicksort, hill sort and heap sort are unstable sorting methods.
Other features
-
Bubble sort and heap sort produce the current maximum and minimum values after each run
-
Quicksort determines the final position of an element in a single run