A C project focused on implementing common sorting algorithms and understanding time complexity through Big O notation. This repository follows the ALX project requirements and uses a consistent coding style across all implementations.
The repository contains multiple sorting algorithm implementations, each with its own test driver and complexity file (O files). These algorithms are used to compare behavior, performance, and trade-offs in different real-world scenarios.
| # | Algorithm | File(s) | Typical Time Complexity | Notes |
|---|---|---|---|---|
| 0 | Bubble Sort | 0-bubble_sort.c |
O(n^2) | Simple comparison sort |
| 1 | Insertion Sort (List) | 1-insertion_sort_list.c |
O(n^2) | Works on doubly linked list |
| 2 | Selection Sort | 2-selection_sort.c |
O(n^2) | In-place, poor for large inputs |
| 3 | Quick Sort (Lomuto) | 3-quick_sort.c |
O(n log n) average, O(n^2) worst | Partition-based divide and conquer |
| 4 | Shell Sort | 100-shell_sort.c |
O(n^2) worst | Gap-based optimization of insertion sort |
| 5 | Cocktail Shaker Sort | 101-cocktail_sort_list.c |
O(n^2) | Bidirectional bubble sort |
| 6 | Counting Sort | 102-counting_sort.c |
O(n + k) | Best for integers with limited range |
| 7 | Merge Sort | 103-merge_sort.c |
O(n log n) | Stable divide-and-conquer algorithm |
| 8 | Heap Sort | 104-heap_sort.c |
O(n log n) | In-place selection sort using heap |
| 9 | Radix Sort | 105-radix_sort.c |
O(nk) | Non-comparison sort for integers |
| 10 | Bitonic Sort | 106-bitonic_sort.c |
O(n log^2 n) | Parallel-friendly sorting network |
| 11 | Quick Sort (Hoare) | 107-quick_sort_hoare.c |
O(n log n) average, O(n^2) worst | Alternate partition scheme |
sorting_algorithms/
├── 0-O # Bubble sort complexity notes
├── 0-bubble_sort.c # Bubble sort implementation
├── 0-main.c # Bubble sort test driver
├── 1-O # Insertion sort complexity notes
├── 1-insertion_sort_list.c # List insertion sort
├── 1-main.c # Insertion sort test driver
├── 2-O # Selection sort complexity notes
├── 2-selection_sort.c # Selection sort implementation
├── 2-main.c # Selection sort test driver
├── 3-O # Quick sort complexity notes
├── 3-quick_sort.c # Quick sort implementation
├── 3-main.c # Quick sort test driver
├── 100-O # Shell sort complexity notes
├── 100-shell_sort.c # Shell sort implementation
├── 100-main.c # Shell sort test driver
├── 101-O # Cocktail sort complexity notes
├── 101-cocktail_sort_list.c# Cocktail sort on doubly linked list
├── 101-main.c # Cocktail sort test driver
├── 102-O # Counting sort complexity notes
├── 102-counting_sort.c # Counting sort implementation
├── 102-main.c # Counting sort test driver
├── 103-O # Merge sort complexity notes
├── 103-merge_sort.c # Merge sort implementation
├── 103-main.c # Merge sort test driver
├── 104-O # Heap sort complexity notes
├── 104-heap_sort.c # Heap sort implementation
├── 104-main.c # Heap sort test driver
├── 105-O # Radix sort complexity notes
├── 105-radix_sort.c # Radix sort implementation
├── 105-main.c # Radix sort test driver
├── 106-O # Bitonic sort complexity notes
├── 106-bitonic_sort.c # Bitonic sort implementation
├── 106-main.c # Bitonic sort test driver
├── 107-O # Quick sort (Hoare) complexity notes
├── 107-quick_sort_hoare.c # Hoare partition quick sort
├── 107-main.c # Hoare quick sort test driver
├── deck.h # Card deck structure used in advanced task
├── print_array.c # Shared array-printing utility
├── push.sh # Helper script
├── sort.h # Function prototypes and list structure
├── README.md # Project documentation
└── merge # Binary artifact or helper file
- Ubuntu 20.04 or compatible Linux environment
- GCC compiler
- C standard:
gnu89 - Warning flags enabled:
gcc -Wall -Wextra -Werror -pedantic -std=gnu89The project follows Betty coding style conventions and emphasizes clean, readable C code.
Each algorithm has a dedicated main file used for testing. Build a specific task with:
gcc -Wall -Wextra -Werror -pedantic -std=gnu89 0-main.c 0-bubble_sort.c print_array.c -o bubbleRun it with:
./bubbleFor other algorithms, replace the file names accordingly. For example:
gcc -Wall -Wextra -Werror -pedantic -std=gnu89 3-main.c 3-quick_sort.c print_array.c -o quick
./quickThis project focuses on understanding complexity in practice:
- Best for ordering small datasets: Bubble, Insertion, Selection
- Best average performance: Merge Sort, Quick Sort, Heap Sort
- Best for limited integer ranges: Counting Sort, Radix Sort
- Useful for linked list structures: Insertion Sort, Cocktail Sort
- Efficient for larger, structured workloads: Merge Sort and Heap Sort
- Implement sorting algorithms in C
- Understand algorithm behavior on different input sizes
- Evaluate time complexity using Big O notation
- Compare stability, memory use, and efficiency
- Practice structured problem-solving and code organization
- Aly Alsayed
- Nwogha Michael Chimdinma
This repository is intended for educational purposes and is designed to help students understand how different sorting algorithms operate, when to use them, and how their performance changes with input size.