A program to show the execution time and the variaty of sorting algorithms in C language. There are 48 sorting algorithms avaliable distributed in 8 different categories.
On program settings there are avaliable modifications noted in table below:
| Configuration | Default |
|---|---|
| Sorting case | Random |
| Random interval | 32 |
| Length of array | 10 |
| Save results in a text file | NO |
| Display arrays | YES |
| Display execution time | YES |
Note: you need to have the GCC compiler installed in your machine to execute the instructions below to run the program.
Open a terminal and go to project's directory. Execute make in terminal allow to compile the program. Commands avaliable to execute with make (make ${command}):
| Command | Description |
|---|---|
| clean | Clear all objects generated |
| cr | Compile and run |
| rmproper | Clear all object files |
| run | Execute main program |
On Command Prompt or PowerShell and go to project's directory and execute execute.bat.
| Algorithm | Worst case | Best case | Average | Space complexity | In-place | Stable | Notes |
|---|---|---|---|---|---|---|---|
| Bad Sort | O(N³) | O(N³) | O(N³) | O(1) | ✔️ | ❌ | |
| Bogo Bogo Sort | O(infinity) | O(N²) | O((N+1)!) | O(1) | ✔️ | ❌ | The worst case can be unbounded due to random manipulation |
| Bogo Sort | O(infinity) | O(N) | O((N+1)!) | O(1) | ✔️ | ❌ | The worst case can be unbounded due to random manipulation |
| Bubble Bogo Sort | O(infinity) | O(N) | O((N+1)!) | O(1) | ✔️ | ✔️ | The worst case can be unbounded due to random manipulation |
| Cocktail Bogo Sort | O(infinity) | O(N) | O((N+1)!) | O(1) | ✔️ | ❌ | The worst case can be unbounded due to random manipulation |
| Exchange Bogo Sort | O(infinity) | O(N) | O((N+1)!) | O(1) | ✔️ | ❌ | The worst case can be unbounded due to random manipulation |
| Less Bogo Sort | O(infinity) | O(N²) | O((N+1)!) | O(1) | ✔️ | ❌ | The worst case can be unbounded due to random manipulation |
| Pancake Sort | O(N²) | O(N²) | O(N²) | O(1) | ✔️ | ❌ | |
| Silly Sort | O(N²) | O(N²) | O(N²) | O(1) | ✔️ | ❌ | |
| Sleep Sort | O(INT_MAX) | O(max(input) + N) | O(max(input) + N) | O(N) | ❌ | ✔️ | Take use of CPU scheduler to sort |
| Slow Sort | O(N*N!) | O(N) | O((N+1)!) | O(1) | ✔️ | ❌ | |
| Spaghetti Sort | O(N) | O(N) | O(N) | O(N) | ❌ | ✔️ | |
| Stooge Sort |  |
|
|
O(N) | ❌ | ❌ | |
| Bubble Sort | O(N²) | O(N) | O(N²) | O(1) | ✔️ | ✔️ | |
| Circle Sort | O(N log N log N) | O(N log N) | O(N log N) | O(1) | ✔️ | ❌ | |
| Cocktail Shaker Sort | O(N²) | O(N²) | O(N²) | O(1) | ✔️ | ✔️ | |
| Comb Sort | O(N²) | O(N log N) |  |
O(1) | ✔️ | ❌ | P is the number of increments |
| Dual Pivot Quick Sort | O(N²) | O(N log N) | O(N log N) | O(log N) | ✔️ | ❌ | |
| Gnome Sort | O(N²) | O(N) | O(N²) | O(1) | ✔️ | ✔️ | |
| Odd-Even Sort | O(N²) | O(N) | O(N²) | O(1) | ✔️ | ✔️ | |
| Optimized Bubble Sort | O(N²) | O(N) | O(N²) | O(1) | ✔️ | ✔️ | |
| Optimized Cocktail Shaker Sort | O(N²) | O(N) | O(N²) | O(1) | ✔️ | ✔️ | |
| Optimized Gnome Sort | O(N²) | O(N) | O(N²) | O(1) | ✔️ | ✔️ | |
| Quick Sort | O(N²) | O(N log N) | O(N log N) | O(log N) | ✔️ | ❌ | |
| Quick Sort 3-way | O(N²) | O(N) | O(N log N) | O(log N) or O(N) | ✔️ | ❌ | |
| Stable Quick Sort | O(N²) | O(N log N) | O(N log N) | O(N) | ✔️ | ✔️ | |
| Tim Sort | O(N log N) | O(N) | O(N log N) | O(N) | ❌ | ✔️ | |
| AVL Tree Sort | O(N log N) | O(N) | O(N log N) | O(N) | ❌ | ✔️ | In worst case, O(N²) when using Binary Search Tree and O(N log N) when using Self-Balanced Binary Search Tree |
| Binary Insertion Sort | O(N log N) | O(N) | O(N log N) | O(1) | ✔️ | ✔️ | |
| Cycle Sort | O(N²) | O(N²) | O(N²) | O(1) | ✔️ | ❌ | |
| Insertion Sort | O(N²) | O(N) | O(N²) | O(1) | ✔️ | ✔️ | |
| Patience Sort | O(N log N) | O(N) | O(N log N) | O(N) | ❌ | ✔️ | |
| Shell Sort |  or O(N log² N) |
O(N log N) | O(N^1.25) to O(N²) | O(1) | ✔️ | ❌ | |
| Tree Sort | O(N²) | O(N log N) | O(N log N) | O(N) | ❌ | ✔️ | In worst case, O(N²) when using Binary Search Tree and O(N log N) when using Self-Balanced Binary Search Tree |
| Bottom-up Merge Sort | O(N log N) | O(N log N) | O(N log N) | O(N) | ❌ | ✔️ | |
| In-Place Merge Sort | O(N²) | O(N²) | O(N²) | O(log N) | ✔️ | ✔️ | |
| Merge Sort | O(N log N) | O(N log N) | O(N log N) | O(N) | ❌ | ✔️ | |
| Bitonic Sort | O(log² N) | O(log² N) | O(log² N) | O(N log² N) | ✔️ | ❌ | |
| Pairwise Network Sort |  or O(N log N) |
O(N log N) | O(N log N) |  |
✔️ | ❌ | Worst case is using parallel time and space complexity non-parallel time |
| Bucket Sort | O(N²) | O(N+k) | O(N+k) | O(N+k) | ❌ | ✔️ | k is the number of buckets |
| Counting Sort | O(N+k) | O(N+k) | O(N+k) | O(N+k) | ❌ | ✔️ | k is the range of input data |
| Gravity (Bead) Sort | O(S) | O(1) or  |
O(N) | O(N²) | ❌ | ✔️ | S is the sum of array elements, O(1) cannot be implemented in practice |
| Pigeonhole Sort | O(N+n) | O(N+n) | O(N+n) | O(N+n) | ❌ | ✔️ | N is the number of elements and n is the range of input data |
| Radix LSD Sort | O(NW) | O(NW) | O(NW) | O(N) | ❌ | ✔️ | W is the maxumum element width (bits) |
| Double Selection Sort | O(N²) | O(N²) | O(N²) | O(1) | ✔️ | ❌ |  Comparisons |
| Max Heap Sort | O(N log N) | O(N log N) | O(N log N) | O(1) | ✔️ | ❌ | |
| Min Heap Sort | O(N log N) | O(N log N) | O(N log N) | O(1) | ✔️ | ❌ | |
| Selection Sort | O(N²) | O(N²) | O(N²) | O(1) | ✔️ | ❌ |  Comparisons |