Sorting Algorithms in C: A Comprehensive Guide

Introduction

Sorting is a fundamental concept in computer science that involves arranging data in a particular order. In the C programming language, there are several sorting algorithms that can be used to arrange data in ascending or descending order. This tutorial will guide you through the most common sorting algorithms in C, including Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort, Heap Sort, Radix Sort, and Bucket Sort.

Selection Sort

Selection Sort is a simple comparison-based algorithm. The idea behind it is to divide the input into a sorted and an unsorted region. The values are swapped to place them in the correct order. Here’s how you can implement Selection Sort in C:

// Code snippet for Selection Sort

Sure, let’s add the code snippets for each sorting algorithm along with explanations.

Bubble Sort

Bubble Sort is one of the simplest sorting algorithms. It works by repeatedly swapping the adjacent elements if they are in the wrong order.
In other word, 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. The pass through the list is repeated until the list is sorted.

Here’s an example of how you can implement Bubble Sort in C:

#include <stdio.h>

void bubbleSort(int array[], int size) {
  for (int step = 0; step < size - 1; ++step) {
    for (int i = 0; i < size - step - 1; ++i) {
      if (array[i] > array[i + 1]) {
        // Swap if greater is at the rear position
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

In the above code, the bubbleSort function takes an array and its size as input. The outer loop, for (int step = 0; step < size - 1; ++step), runs size - 1 times. This is because the largest element will be at the end after the first pass, the second largest element will be at the second last position after the second pass, and so on. The inner loop, for (int i = 0; i < size - step - 1; ++i), is for comparing each element in the array with the next element, if (array[i] > array[i + 1]). If the current element is greater than the next element, they are swapped.

Insertion Sort

Insertion Sort is a simple sorting algorithm that works the way we sort playing cards in our hands. The array is virtually split into a sorted and an unsorted region. Values from the unsorted region are picked and placed at the correct position in the sorted region.

In other word, insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Here’s how you can implement Insertion Sort in C:

#include <stdio.h>

void insertionSort(int array[], int size) {
  for (int step = 1; step < size; step++) {
    int key = array[step];
    int j = step - 1;

    // Compare key with each element on the left of it until an element smaller than it is found
    // For descending order, change key<array[j] to key>array[j].
    while (key < array[j] && j >= 0) {
      array[j + 1] = array[j];
      --j;
    }
    array[j + 1] = key;
  }
}

In the above code, the insertionSort function takes an array and its size as input. The outer loop, for (int step = 1; step < size; step++), runs size - 1 times. This is because the first element is considered as sorted. The key element is the element that we intend to insert into the sorted portion of the array, and j is the last element in the sorted portion of the array. The inner loop, while (key < array[j] && j >= 0), shifts all elements in the sorted portion of the array that are greater than the key towards the right. After shifting, the key element can be inserted at j + 1 which is its correct position.

Selection Sort

Selection Sort is a simple comparison-based algorithm. The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

In short, selection Sort is a simple comparison-based algorithm. The idea behind it is to divide the input into a sorted and an unsorted region. The values are swapped to place them in the correct order. Here’s how you can implement Selection Sort in C:

#include <stdio.h>

void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min_idx = step;
    for (int i = step + 1; i < size; i++) {

      // To sort in descending order, change > to < in this line.
      if (array[i] < array[min_idx])
        min_idx = i;
    }

    // Swap the minimum element with the first element of the unsorted part
    int temp = array[step];
    array[step] = array[min_idx];
    array[min_idx] = temp;
  }
}

In the above code, the selectionSort function takes an array and its size as input. The outer loop, for (int step = 0; step < size - 1; step++), runs size - 1 times. This is because the last element will be automatically sorted after sorting all other elements. The variable min_idx stores the index of the smallest element. The inner loop, for (int i = step + 1; i < size; i++), is for finding the smallest element in the unsorted part of the array. If the current element is smaller than the element at min_idx, min_idx is updated. After finding the smallest element in the unsorted part of the array, it is swapped with the first element in the unsorted part of the array.

Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, sorts them separately, and then merges them. This is how you can implement Merge Sort in C:

#include <stdio.h>

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

  int L[n1], M[n2];

  for (int i = 0; i < n1; i++)
    L[i] = array[l + i];
  for (int j = 0; j < n2; j++)
    M[j] = array[m + 1 + j];

  int i, j, k;
  i = 0;
  j = 0;
  k = l;

  while (i < n1 && j < n2) {
    if (L[i] <= M[j]) {
      array[k] = L[i];
      i++;
    } else {
      array[k] = M[j];
      j++;
    }
    k++;
  }

  while (i < n1) {
    array[k] = L[i];
    i++;
    k++;
  }

  while (j < n2) {
    array[k] = M[j];
    j++;
    k++;
  }
}

void mergeSort(int array[], int l, int r) {
  if (l < r) {
    int m = l + (r - l) / 2;

    mergeSort(array, l, m);
    mergeSort(array, m + 1, r);

    merge(array, l, m, r);
  }
}

In the above code, the mergeSort function takes an array and two indices, l and r, as input. The array is recursively divided in half until the size becomes 1. The merge function is used to merge two halves. L[] and M[] are temporary arrays that store the two halves to merge.

Quick Sort

Quick Sort is a highly efficient sorting algorithm that works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. Here’s how you can implement Quick Sort in C:

#include <stdio.h>

void swap(int* a, int* b) {
  int t = *a;
  *a = *b;
  *b = t;
}

int partition(int array[], int low, int high) {
  int pivot = array[high];
  int i = (low - 1);

  for (int j = low; j < high; j++) {
    if (array[j] <= pivot) {
      i++;
      swap(&array[i], &array[j]);
    }
  }

  swap(&array[i + 1], &array[high]);
  return (i + 1);
}

void quickSort(int array[], int low, int high) {
  if (low < high) {
    int pi = partition(array, low, high);

    quickSort(array, low, pi - 1);
    quickSort(array, pi + 1, high);
  }
}

In the above code, the quickSort function takes an array and two indices, low and high, as input. The array is recursively divided around the pivot. The partition function is used to find the pivot and move all smaller elements to the left of the pivot and all larger elements to the right.

Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. Here’s how you can implement Heap Sort in C:

#include <stdio.h>

void heapify(int arr[], int n, int i) {
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest])
    largest = left;

  if (right < n && arr[right] > arr[largest])
    largest = right;

  if (largest != i) {
    swap(&arr[i], &arr[largest]);
    heapify(arr, n, largest);
  }
}

void heapSort(int arr[], int n) {
  for (int i = n / 2 - 1; i >= 0; i--)
    heapify(arr, n, i);

  for (int i = n - 1; i >= 0; i--) {
    swap(&arr[0], &arr[i]);
    heapify(arr, i, 0);
  }
}

In the above code, the heapSort function takes an array and its size as input. The array is turned into a max heap using the heapify function. Then, the largest element is moved to the end of the array, the size of the heap is reduced by one, and the heapify process is repeated until the heap size becomes 1.

Radix Sort

Radix Sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. Here’s how you can implement Radix Sort in C:

#include <stdio.h>

int getMax(int array[], int n) {
  int max = array[0];
  for (int i = 1; i < n; i++)
    if (array[i] > max)
      max = array[i];
  return max;
}

void countingSort(int array[], int size, int place) {
  const int max = 10;
  int output[size];
  int count[max];

  for (int i = 0; i < max; ++i)
    count[i] = 0;

  for (int i = 0; i < size; i++)
    count[(array[i] / place) % max]++;

  for (int i = 1; i < max; i++)
    count[i] += count[i - 1];

  for (int i = size - 1; i >= 0; i--) {
    output[count[(array[i] / place) % max] - 1] = array[i];
    count[(array[i] / place) % max]--;
  }

  for (int i = 0; i < size; i++)
    array[i] = output[i];
}

void radixsort(int array[], int size) {
  int max = getMax(array, size);
  for (int place = 1; max / place > 0; place *= 10)
    countingSort(array, size, place);
}

In the above code, the radixsort function takes an array and its size as input. The maximum element is found and the array is sorted according to each digit from the least significant digit to the most significant digit. The countingSort function is used to sort elements based on significant places.

Bucket Sort

Bucket Sort is a comparison sort algorithm that operates on elements by dividing them into different buckets and then sorting these buckets individually. Each bucket is sorted individually using a separate sorting algorithm. Here’s how you can implement Bucket Sort in C:

#include <stdio.h>
#include <stdlib.h>

void bucketSort(float arr[], int n) {
  // Create n empty buckets
  float* b[n];
  for (int i = 0; i < n; i++) {
    b[i] = NULL;
  }

  // Insert array elements into their respective buckets
  for (int i = 0; i < n; i++) {
    int bi = n * arr[i]; // Index in bucket
    b[bi] = (float*)realloc(b[bi], (bi + 1) * sizeof(float));
    b[bi][bi] = arr[i];
  }

  // Sort individual buckets
  for (int i = 0; i < n; i++) {
    qsort(b[i], i, sizeof(float), compareFloats);
  }

  // Concatenate all buckets into arr[]
  int index = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
      arr[index++] = b[i][j];
    }
  }
}

int compareFloats(const void* a, const void* b) {
  float arg1 = *(const float*)a;
  float arg2 = *(const float*)b;

  if (arg1 < arg2) return -1;
  if (arg1 > arg2) return 1;
  return 0;
}

In the above code, the bucketSort function takes an array and its size as input. The array elements are distributed into a number of buckets. Then, each bucket is sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. The compareFloats function is used to compare two floats, which is needed for the qsort function.

Conclusion

Sorting algorithms are a crucial part of programming and understanding how they work is essential for any programmer. This guide has provided an overview of the most common sorting algorithms in C, along with examples of how to implement them.

Frequently Asked Questions (FAQ)

Related Tutorials

1. Command Line Arguments in C
2. Function Pointers in C
3. Efficient Memory Management in C
4. Hashing in C
5. Multithreading in C
6. Network Programming in C
7. Building a Web Server in C
8. Introduction to Algorithms in C
9. Advanced Algorithms in C
10. Building a Chat Application in C
11. Searching Algorithms in C