Introduction
When choosing a sorting algorithm, one would hope for the least number of comparisons, swaps and space allocations possible. However, there is no perfect sorting method in the world, and trade-offs must be made among comparisons, swaps, and space allocation.
Many comparisons – Few swaps – Not require additional space allocation
Selection Sort is a classic example of such an algorithm. In Selection Sort, the algorithm traverses the array multiple times. Each time it traverses, it looks for the smallest (or largest) element in the remaining unsorted portion, and then swaps it with the first element of the unsorted portion. Therefore, although the number of comparisons is high (almost O(n^2)), the number of swaps is relatively low, with a maximum of n-1 swaps.
Few comparisons – Few swaps – Not require additional space allocation
Bubble Sort somewhat meets this criterion to a certain extent. It works by repeatedly traversing through the array to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The number of comparisons in Bubble Sort can be close to that of Selection Sort, but a swap is performed every time a comparison finds items in the wrong order, leading to potentially a large number of swaps in the worst-case scenario (when the array is completely in reverse order).
Few comparisons – Few swaps – Require additional space allocation
Merge Sort is a representative of this category. Merge Sort has a time complexity of O(n log n) in the best, worst, and average cases, with a relatively lower number of comparisons and swaps (actually, copying of array elements). However, it requires additional space to temporarily store the elements being merged, with a space complexity of O(n), meaning it needs a significant amount of allocated space.
Analysis of Time Spent on Various Operations
Through a simple experiment to measure the execution time of comparisons, swaps and space allocations, the actual running results have a significant relationship with prefetch, cache hit/miss, compiler optimization, malloc implementation, and there will be some differences from the test below. However, generally speaking, the time spent on swaping and space allocations is definitely higher than that of comparisons.
When the sorting time >> space allocation time, algorithms that tend to allocate a large amount of space to reduce sorting time are usually preferred.
Experimental Environment:
Computer: M2 Air,
Compiler: gcc -O0
Space Allocation: Array of 10,000 integer unitsSingle Action Measurement:
Total time spent on write operations: 4 clocks
Total time spent on read operations: 2 clocks
Total time spent on comparison operations: 0.5 clocks
Total time spent on dynamic memory allocation operations: 20 clocks