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 comparisonbased 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;
}
}
}
}
CIn 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;
}
}
CIn 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 comparisonbased 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 comparisonbased 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;
}
}
CIn 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 divideandconquer 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);
}
}
CIn 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 subarrays, 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);
}
}
CIn 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 comparisonbased 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);
}
}
CIn 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 noncomparative 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);
}
CIn 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;
}
CIn 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)

Which is the best sorting algorithm in C?
The “best” sorting algorithm can depend on the specific requirements of your program. Quick Sort is generally considered the fastest on average, but Merge Sort uses less worstcase time complexity and is more efficient with large datasets. If stability is a concern (i.e., maintaining the relative order of equal sort keys), then Merge Sort would be preferred.

What is a sorting algorithm in C?
A sorting algorithm in C is a method used to rearrange a list of elements in a particular order (ascending or descending). The order is determined based on the comparison operator used in the algorithm. Examples of sorting algorithms include Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort, Heap Sort, Radix Sort, and Bucket Sort.

What is the easiest sort algorithm in C?
The easiest sorting algorithm to understand and implement is probably Bubble Sort. It works by repeatedly swapping adjacent elements if they are in the wrong order. However, it’s not the most efficient algorithm for large datasets.

What are the four sort algorithms in C?
There are many sorting algorithms available, but four common ones you might come across are:
a) Bubble Sort: Simple and easy to implement, but not very efficient with large data.
b) Quick Sort: Very efficient, but can be complex to understand and implement.
c) Merge Sort: Efficient and easier to understand than Quick Sort, but uses more memory.
d) Heap Sort: Efficient like Quick Sort and Merge Sort, and doesn’t use extra memory, but can be complex to implement. 
How does Bubble Sort work in C?
Bubble Sort works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no more swaps are needed, indicating that the list is sorted.

How does Insertion Sort work in C?
Insertion Sort works by dividing the list into a sorted and an unsorted region. The values from the unsorted region are picked and placed at the correct position in the sorted region. This process continues until all the values are moved to the sorted region.

How does Selection Sort work in C?
Selection Sort divides the input into a sorted and an unsorted region. It repeatedly selects the smallest (or largest, depending on the sorting order) element from the unsorted region, and moves that to the sorted region. This process continues until all elements have been moved to the sorted region.

How does Merge Sort work in C?
Merge Sort is a divideandconquer algorithm that divides the input array into two halves, sorts them separately, and then merges them. The array is recursively divided in half until the size becomes 1. Then, all the half arrays are merged back together in the correct order.

How does Quick Sort work in C?
Quick Sort is a divideandconquer algorithm that works by selecting a ‘pivot’ element from the array and partitioning the other elements into two subarrays, according to whether they are less than or greater than the pivot. The process is then recursively applied to the subarrays.

How does Heap Sort work in C?
Heap Sort works by visualizing the elements of the array as a special kind of complete binary tree called a heap. The heap is constructed and the largest value (in a max heap) or the smallest value (in a min heap) is placed into the sorted array. The heap is updated to remove this value, and the process continues until the heap is empty and all elements have been placed into the sorted array.