A comprehensive educational resource for mastering sorting algorithms through multi-language implementations and interactive visualizations.
SortingAlgorithms is an educational repository designed to help developers understand and master fundamental sorting techniques. This project features clean, well-documented implementations of 6 essential sorting algorithms across multiple programming languages (C, C++, Python), complete with complexity analysis and practical examples.
Experience sorting algorithms in action! Visit our interactive visualization tool:
The companion website provides:
- Real-time algorithm animations
- Step-by-step execution visualization
- Interactive controls to understand each sorting technique
- Visual comparison of different algorithms
| Algorithm | Time Complexity (Best) | Time Complexity (Average) | Time Complexity (Worst) | Space Complexity | Stable | In-Place |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ Yes | ✅ Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | ❌ No | ✅ Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ Yes | ✅ Yes |
| Shell Sort | O(n log n) | O(n^(4/3)) | O(n²) | O(1) | ❌ No | ✅ Yes |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | ✅ Yes | ❌ No |
| Radix Sort | O(d × n) | O(d × n) | O(d × n) | O(n + k) | ✅ Yes | ❌ No |
where n = number of elements, k = range of input, d = number of digits
SortingAlgorithms/
├── BubbleSort/
│ ├── bubble_sort.c
│ ├── bubble_sort.cpp (Coming Soon)
│ ├── bubble_sort.py (Coming Soon)
│ └── README.md
├── SelectionSort/
│ ├── selection_sort.c
│ ├── selection_sort.cpp (Coming Soon)
│ ├── selection_sort.py (Coming Soon)
│ └── README.md
├── InsertionSort/
│ ├── insertion_sort.c
│ ├── insertion_sort.cpp (Coming Soon)
│ ├── insertion_sort.py (Coming Soon)
│ └── README.md
├── ShellSort/
│ ├── shell_sort.c
│ ├── shell_sort.cpp (Coming Soon)
│ ├── shell_sort.py (Coming Soon)
│ └── README.md
├── CountingSort/
│ ├── counting_sort.c
│ ├── counting_sort.cpp (Coming Soon)
│ ├── counting_sort.py (Coming Soon)
│ └── README.md
├── RadixSort/
│ ├── radix_sort.c
│ ├── radix_sort.cpp (Coming Soon)
│ ├── radix_sort.py (Coming Soon)
│ └── README.md
├── README.md
└── LICENSE
-
For C implementations:
- GCC compiler (version 7.0 or higher)
- Make (optional, for build automation)
-
For C++ implementations: (Coming Soon)
- G++ compiler (version 7.0 or higher)
-
For Python implementations: (Coming Soon)
- Python 3.7 or higher
Each algorithm folder contains its own implementation. Navigate to the desired folder and compile:
# Navigate to algorithm folder
cd BubbleSort
# Compile the C code
gcc bubble_sort.c -o bubble_sort
# Run the executable
./bubble_sortOr use the following one-liner:
gcc bubble_sort.c -o bubble_sort && ./bubble_sortDescription: Repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order. The process repeats until the list is sorted.
Best Use Cases:
- Small datasets
- Educational purposes
- Nearly sorted data
Advantages:
- Simple to understand and implement
- Stable sorting algorithm
- In-place sorting (no extra memory needed)
Disadvantages:
- Very inefficient for large datasets
- O(n²) time complexity
Description: Divides the input into sorted and unsorted regions. Repeatedly selects the smallest (or largest) element from the unsorted region and moves it to the end of the sorted region.
Best Use Cases:
- Small datasets
- When memory write operations are costly
- When simplicity is preferred over efficiency
Advantages:
- Simple implementation
- Performs well with small lists
- Minimum number of swaps (O(n))
Disadvantages:
- Inefficient on large lists
- Not stable by default
- Always O(n²) comparisons
Description: Builds the final sorted array one item at a time. Takes each element and inserts it into its correct position in the already sorted portion.
Best Use Cases:
- Small datasets
- Nearly sorted data
- Online sorting (sorting data as it's received)
Advantages:
- Simple and intuitive
- Efficient for small data sets
- Adaptive: O(n) for nearly sorted data
- Stable and in-place
Disadvantages:
- Inefficient for large datasets
- O(n²) time complexity in worst case
Description: A generalization of insertion sort that allows exchange of items that are far apart. It starts by sorting pairs of elements far apart from each other, then progressively reducing the gap.
Best Use Cases:
- Medium-sized datasets
- When quicksort/mergesort overhead is too high
- Embedded systems with limited memory
Advantages:
- Faster than insertion/bubble/selection sort
- In-place sorting
- No quadratic worst-case scenarios for good gap sequences
Disadvantages:
- Not stable
- Optimal gap sequence is unknown
- Complexity depends on gap sequence
Description: A non-comparison based sorting algorithm that works by counting the number of objects having distinct key values. Uses this count to calculate positions of elements.
Best Use Cases:
- When range of input values (k) is not significantly larger than n
- Sorting integers within a known range
- As a subroutine for radix sort
Advantages:
- Linear time complexity O(n + k)
- Stable sorting algorithm
- Efficient when range is limited
Disadvantages:
- Requires extra space proportional to range
- Only works with non-negative integers (or requires offset)
- Inefficient when range k >> n
Description: A non-comparison based sorting algorithm that processes individual digits. Sorts numbers digit by digit, starting from the least significant digit to the most significant digit.
Best Use Cases:
- Sorting large sets of integers
- Fixed-length string sorting
- When data has multiple keys
Advantages:
- Linear time complexity for fixed-length integers
- Stable sorting algorithm
- Efficient for large datasets with small digit count
Disadvantages:
- Requires stable intermediate sorting (usually counting sort)
- Space complexity O(n + k)
- Less flexible than comparison-based sorts
Start with these algorithms to understand sorting fundamentals:
- Bubble Sort - Understand the basic concept of sorting
- Selection Sort - Learn about finding minimum/maximum
- Insertion Sort - Grasp the concept of building sorted sequences
Progress to more efficient algorithms: 4. Shell Sort - Introduction to gap-based sorting 5. Counting Sort - Learn non-comparison based sorting
Master specialized techniques: 6. Radix Sort - Digit-by-digit processing
For a dataset of 10,000 elements:
| Algorithm | Random Data | Nearly Sorted | Reverse Sorted |
|---|---|---|---|
| Bubble Sort | ~100s | ~0.5s | ~200s |
| Selection Sort | ~50s | ~50s | ~50s |
| Insertion Sort | ~50s | ~0.01s | ~100s |
| Shell Sort | ~0.5s | ~0.1s | ~1s |
| Counting Sort | ~0.001s* | ~0.001s* | ~0.001s* |
| Radix Sort | ~0.005s* | ~0.005s* | ~0.005s* |
*Assuming limited range of values
Note: Actual performance depends on implementation, hardware, and data characteristics.
- Dataset is very small (< 10 elements)
- Learning/teaching sorting concepts
- Data is already nearly sorted
- Memory writes are expensive
- Dataset is small
- Simplicity is more important than speed
- Dataset is small or nearly sorted
- Building sorted list incrementally
- Stability is required
- Dataset is medium-sized (100-5000 elements)
- Want better performance than O(n²) without recursion
- Memory is limited
- Sorting integers with a small range
- Need linear time complexity
- Stability is important
- Sorting large sets of integers or fixed-length strings
- Range of values is large but digit count is small
- Need stable, non-comparison based sorting
- Add C++ implementations for all algorithms
- Add Python implementations for all algorithms
- Include performance benchmarking tools
- Add unit tests for each implementation
- Create visual comparison graphs
- Add hybrid sorting algorithms (TimSort, IntroSort)
- Include advanced algorithms (MergeSort, QuickSort, HeapSort)
- Add parallel/concurrent sorting implementations
- Create detailed video tutorials
- Add algorithm animation GIFs to each README
Contributions are welcome! Here's how you can help:
- Fork the repository
- Create a new branch (
git checkout -b feature/improvement) - Make your changes
- Test thoroughly
- Commit your changes (
git commit -am 'Add new feature') - Push to the branch (
git push origin feature/improvement) - Create a Pull Request
- Ensure code is well-commented and follows the existing style
- Add or update README files for new algorithms
- Test your implementations with various input cases
- Update the main README if adding new algorithms
This project is licensed under the MIT License - see the LICENSE file for details.
Fakrul Islam
- 🎓 Bachelor's in Computer Engineering, Politecnico di Torino
- 💼 LinkedIn: Fakrul Islam Arif
- 🌐 Interactive Project: learnsorting.lovable.app
- Thanks to the computer science community for comprehensive sorting algorithm documentation
- Interactive visualizations powered by Lovable
- Inspired by classic computer science textbooks and courses
- "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein
- "The Art of Computer Programming, Vol. 3: Sorting and Searching" by Donald Knuth
- "Algorithms" by Robert Sedgewick and Kevin Wayne
- Visualgo - Algorithm visualizations
- GeeksforGeeks Sorting - Detailed explanations
- Big-O Cheat Sheet - Complexity reference
If you found this repository helpful, please consider giving it a ⭐️!
Happy Sorting! 🎉
Learn. Code. Visualize. Master.