Exchange Sorts
These are sorting algorithms that rely on making comparisons and exchanging them if they are out of order.
Exchange sort list
Here is a list of all the Exchange Sorts that I’ve analysed:
Bubble Sort
Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the entire list is sorted, with larger elements "bubbling" to the end.
Cocktail Sort
Cocktail sort, also known as shaker sort, is a variation of the bubble sort algorithm that sorts a list by moving through it bidirectionally, comparing and swapping adjacent elements in both directions.
Comb Sort
Comb Sort works by repeatedly comparing and swapping adjacent elements with a diminishing gap between them until the gap becomes 1, resembling the teeth of a comb.
Hanoi Sort
Hanoi Sort is a sorting algorithm based on the Tower of Hanoi data structure where elements are moved from one 'peg' to another without putting a larger item on a smaller one.
Quick Sort
Quick sort is a widely used, efficient, and divide-and-conquer sorting algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, with elements smaller than the pivot on one side and larger on the other.
Slow Sort
Slow sort is a humorous, intentionally inefficient sorting algorithm designed as a parody of sorting algorithms. It repeatedly searches for the largest unsorted element in the list and swaps it with the last element until the entire list is sorted.
Stooge Sort
Stooge sort is an inefficient recursive sorting algorithm. It works by recursively sorting the first two-thirds and last two-thirds of the list and then recursively sorting the first two-thirds again.
Time complexity
| Name | Best | Average | Worst | Memory |
|---|---|---|---|---|
| Bubble Sort | C: n S: 0 | C: (n²-n)/2 – P S: (n²-n)/4 – P | C: (n²-n)/2 S: (n²-n)/2 | 1 |
| Cocktail Sort | C: 2n S: 0 | C: (n²-n)/2 – 2P S: (n²-n)/4 – 2P | C: (n²-n)/2 S: (n²-n)/4 | 1 |
| Comb Sort | C: n log(n) S: 0 | C: 2n log(n) S: 0.4n log(n) | C: 4n log(n) S: 0.5n log(n) | 1 |
| Hanoi Sort | C: n I: 0 | C: n²/4+n/2 I: 2e⁰′⁶ⁿ | C: n²/2 I: 4e⁰′⁶ⁿ | 1 |
| Proportional Exchange Sort | TBD | TBD | TBD | |
| Quick Sort | C: n log(n) I: n | C: n log(n) + 2n I: 0.8 n log(n) | C: (n²-n)/2 S: (n²-n)/2 | 1 |
| Slow Sort | C: n^(log(n)/2.175) S: 0 | C: n^(log(n)/2.175) S: n²/4 | C: n^(log(n)/2.175) S: (n²-n)/2 | 1 |
| Stooge Sort | C: 0.92n^(log2(3)/log2(1.5)) S: 0 | C: 0.92n^(log2(3)/log2(1.5)) S: n²/4 | C: 0.92n^(log2(3)/log2(1.5)) S: n²/2 | 1 |
