Mastering Sorting Algorithms in C: A Comprehensive Guide

Sorting is one of the most fundamental operations in computer science, with applications ranging from organizing data for efficient retrieval to optimizing search algorithms and improving the performance of various applications.

Related: Searching algorithms in C

In this comprehensive guide, we will explore several sorting algorithms implemented in the C programming language. From simple and intuitive methods to more complex and efficient ones, we’ll cover everything you need to know to master sorting algorithms in C.

1. 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. It is named for the way smaller elements “bubble” to the top of the list with each pass through the array.

Here’s how the bubble sort algorithm works:

1. Start at the Beginning: The algorithm begins by starting at the first element of the list.
2. Compare Adjacent Elements: It compares each pair of adjacent elements in the list, starting from the beginning.
3. Swap if Necessary: If the two adjacent elements are in the wrong order (i.e., the element on the left is greater than the element on the right), the algorithm swaps them.
4. Move to the Next Pair: After comparing and possibly swapping adjacent elements, the algorithm moves to the next pair of elements in the list and repeats steps 2 and 3.
5. Repeat Until Sorted: The algorithm continues this process of comparing and swapping elements until no more swaps are needed, indicating that the list is sorted.
6. Optimization: An optimization can be made by noting that after each pass through the list, the largest element will “bubble up” to its correct position at the end of the list. Therefore, on each subsequent pass, the algorithm can ignore the last i elements, where i is the number of passes made so far.

Here’s a simple implementation of the bubble sort algorithm in C:

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Swap arr[j] and arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

In this implementation:

• arr[] is the array to be sorted.
• n is the number of elements in the array.

The function sorts the array arr[] in ascending order using the bubble sort algorithm.

Bubble sort has a time complexity of O(n^2) in the worst-case scenario, where n is the number of elements in the array. Despite its simplicity, bubble sort is not very efficient for sorting large arrays, especially when compared to more advanced sorting algorithms like quick sort or merge sort. However, it is easy to implement and understand, making it a good starting point for learning about sorting algorithms.

2. Selection Sort

Selection sort is a simple and intuitive sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted portion of the list and swaps it with the first unsorted element. It sorts the array by dividing it into two subarrays: the sorted subarray and the unsorted subarray.

Here’s how the selection sort algorithm works:

1. Divide the Array: The algorithm divides the array into two subarrays: the sorted subarray and the unsorted subarray. Initially, the sorted subarray is empty, and the unsorted subarray contains all the elements of the array.
2. Find the Smallest Element: The algorithm searches the unsorted subarray to find the smallest element.
3. Swap with the First Unsorted Element: Once the smallest element is found, the algorithm swaps it with the first element of the unsorted subarray. This effectively adds the smallest element to the end of the sorted subarray and removes it from the unsorted subarray.
4. Repeat: The algorithm repeats steps 2 and 3 for the remaining elements of the unsorted subarray until the entire array is sorted.
5. Termination: The algorithm terminates when the entire array has been sorted, and the unsorted subarray becomes empty.

Here’s a simple implementation of the selection sort algorithm in C:

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_index = i;
        // Find the index of the smallest element in the unsorted subarray
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        // Swap the smallest element with the first unsorted element
        int temp = arr[i];
        arr[i] = arr[min_index];
        arr[min_index] = temp;
    }
}

In this implementation:

• arr[] is the array to be sorted.
• n is the number of elements in the array.

The function sorts the array arr[] in ascending order using the selection sort algorithm.

Selection sort has a time complexity of O(n^2) in all cases, where n is the number of elements in the array. Despite its simplicity, selection sort is not very efficient for sorting large arrays, especially when compared to more advanced sorting algorithms like quick sort or merge sort. However, it has the advantage of requiring only a constant amount of additional memory space, making it useful in situations where memory is limited.

3. Insertion Sort

Insertion sort algorithm proceeds by building the final sorted array one element at a time. It works by repeatedly taking one element from the unsorted part of the array and inserting it into its correct position in the sorted part of the array. At each step, the algorithm expands the sorted portion of the array by one element.

Here’s how the insertion sort algorithm works:

1. Start with the First Element: The algorithm considers the first element of the array as the initial sorted portion.
2. Insertion Step: For each subsequent element in the unsorted portion of the array:
   • The algorithm compares the element with each element in the sorted portion, starting from the end.
   • It moves each element in the sorted portion that is greater than the current element one position to the right.
   • Once it finds the correct position for the current element (i.e., a position where the element to its left is smaller and the element to its right is larger), it inserts the current element into that position.
3. Repeat: The algorithm repeats the insertion step for each element in the unsorted portion of the array until the entire array is sorted.
4. Termination: The algorithm terminates when all elements have been inserted into their correct positions, and the entire array becomes sorted.

Here’s a simple implementation of the insertion sort algorithm in C:

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

In this implementation:

• arr[] is the array to be sorted.
• n is the number of elements in the array.

The function sorts the array arr[] in ascending order using the insertion sort algorithm.

Insertion sort has a time complexity of O(n^2) in the worst-case scenario, where n is the number of elements in the array. Despite its simplicity, insertion sort can be very efficient for sorting small arrays or nearly sorted arrays. It also has the advantage of being an in-place sorting algorithm, meaning it requires only a constant amount of additional memory space, making it useful in situations where memory is limited.

4. Merge Sort

Merge sort is a divide-and-conquer sorting algorithm that works by dividing the input array into two halves, sorting each half recursively, and then merging the sorted halves to produce the final sorted array. It is known for its efficiency and stability.

Here’s how the merge sort algorithm works:

1. Divide: The algorithm divides the array into two halves. This step is repeated recursively until each subarray contains only one element, which is inherently sorted.
2. Conquer: The algorithm sorts each subarray. This is done by recursively applying the merge sort algorithm to each half of the array.
3. Merge: The sorted subarrays are merged to produce a single sorted array. This is done by comparing the elements of the two subarrays and selecting the smaller (or larger) element at each step to form the merged array.
4. Repeat: Steps 1-3 are repeated recursively until the entire array is sorted.
5. Termination: The algorithm terminates when each subarray contains only one element and cannot be further divided.

Here’s a simple implementation of the merge sort algorithm in C:

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];

    // Copy data to temporary arrays L[] and R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // Merge the temporary arrays back into arr[l..r]
    int i = 0; // Initial index of first subarray
    int j = 0; // Initial index of second subarray
    int k = l; // Initial index of merged subarray
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // Same as (l+r)/2, but avoids overflow for large l and r
        int m = l + (r - l) / 2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        // Merge the sorted halves
        merge(arr, l, m, r);
    }
}

In this implementation:

• arr[] is the array to be sorted.
• l and r are the indices of the first and last elements of the subarray to be sorted.

The function sorts the array arr[] in ascending order using the merge sort algorithm.

Merge sort has a time complexity of O(n log n) in all cases, where n is the number of elements in the array. It is highly efficient and stable, making it suitable for sorting large arrays or datasets. Additionally, merge sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the sorted array.

5. Quick Sort

Finally, quick sort is a highly efficient sorting algorithm based on the divide-and-conquer strategy. It works by selecting a pivot element from the array and partitioning the other elements into two subarrays: elements less than the pivot and elements greater than the pivot. The subarrays are then recursively sorted using the same process until the entire array is sorted.

Here’s how the quick sort algorithm works:

1. Choose a Pivot: The algorithm selects a pivot element from the array. There are various methods for choosing a pivot, but a common approach is to select the last element of the array.
2. Partitioning: The array is partitioned into two subarrays: elements less than the pivot and elements greater than the pivot. This is done by iterating through the array and moving elements to the left or right of the pivot based on their values.
3. Recursion: The quick sort algorithm is recursively applied to the subarrays created in the previous step. This process continues until each subarray contains only one element, which is inherently sorted.
4. Combine: Once the subarrays are sorted, they are combined to produce the final sorted array. This step is usually trivial, as the subarrays are already sorted.
5. Termination: The algorithm terminates when each subarray contains only one element and cannot be further divided.

Here’s a simple implementation of the quick sort algorithm in C:

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Pivot (last element)
    int i = (low - 1); // Index of smaller element

    for (int j = low; j <= high - 1; j++) {
        // If current element is smaller than or equal to pivot
        if (arr[j] <= pivot) {
            i++; // Increment index of smaller element
            // Swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // Swap arr[i + 1] and arr[high] (or pivot)
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // Partitioning index
        int pi = partition(arr, low, high);

        // Recursively sort elements before partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

In this implementation:

• arr[] is the array to be sorted.
• low and high are the indices of the first and last elements of the subarray to be sorted.

The function sorts the array arr[] in ascending order using the quick sort algorithm.

Quick sort has an average-case time complexity of O(n log n), where n is the number of elements in the array. However, it can degrade to O(n^2) in the worst-case scenario (e.g., if the pivot is always the smallest or largest element). Despite this, quick sort is highly efficient in practice and is widely used in various applications. Additionally, quick sort is an in-place sorting algorithm, meaning it requires only a constant amount of additional memory space, making it suitable for sorting large arrays or datasets.

Conclusion

In this comprehensive guide, we’ve covered several sorting algorithms implemented in the C programming language. Each algorithm has its own advantages and disadvantages, and choosing the right algorithm depends on factors such as the size of the input, the distribution of data, and the desired performance characteristics.

By understanding these sorting algorithms and their implementations in C, you’ll be better equipped to tackle a wide range of sorting tasks and optimize the performance of your programs. Whether you’re sorting small arrays or large datasets, mastering these sorting algorithms is an essential skill for any programmer.