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

NameBestAverageWorstMemory
Bubble SortC: n
S: 0
C: (n²-n)/2 – P
S: (n²-n)/4 – P
C: (n²-n)/2
S: (n²-n)/2
1
Cocktail SortC: 2n
S: 0
C: (n²-n)/2 – 2P
S: (n²-n)/4 – 2P
C: (n²-n)/2
S: (n²-n)/4
1
Comb SortC: 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 SortC: n
I: 0
C: n²/4+n/2
I: 2e⁰′⁶ⁿ
C: n²/2
I: 4e⁰′⁶ⁿ
1
Proportional Exchange SortTBDTBDTBD
Quick SortC: 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 SortC: 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 SortC: 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

Search

Subscribe to the mailing list

Follow N64 Squid

  • RSS Feed
  • YouTube

Random featured posts