Sorting Algorithms in C: Implementations of Bubble, Selection, and Insertion Sort

In computer science, sorting algorithms are a crucial part. They are used to arrange data in a specific order. This article will introduce three basic sorting algorithms: Bubble Sort, Selection Sort, and Insertion Sort, along with their corresponding implementations in C.

1. Bubble Sort

Algorithm Overview

Bubble sort is a simple exchange-based sorting algorithm. It repeatedly traverses the array to be sorted, comparing adjacent elements and swapping their positions, causing larger elements to gradually “float” to the top of the array (or smaller elements to sink to the bottom). This process continues until there are no more elements to swap.

Time Complexity

• Worst case: O(n^2)
• Average case: O(n^2)
• Best case: O(n)

C Implementation

#include <stdio.h>
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;
            }
        }
    }
}
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArray(arr, n);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

2. Selection Sort

Algorithm Overview

Selection sort is a simple and intuitive comparison-based algorithm. It repeatedly selects the smallest (or largest) element from the unsorted portion and places it at the end of the sorted portion. This process continues until all elements are sorted.

Time Complexity

• Worst case: O(n^2)
• Average case: O(n^2)
• Best case: O(n^2)

C Implementation

#include <stdio.h>
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // Find the position of the minimum value
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the found minimum value with the value at position i
        if(minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}
void printArray(int arr[], int size) {
   for (int i=0; i<size; i++)
       printf("%d ", arr[i]);
   printf("\n");
}
int main() {
   int array[] ={64, 25, 12, 22, 11};
   int n=sizeof(array)/sizeof(array[0]);
   printf("Original array: \n");
   printArray(array, n);
   selectionSort(array, n);
   printf("Sorted array: \n");
   printArray(array, n);
   return(0);
}

3. Insertion Sort

Algorithm Overview

Insertion sort is a commonly used method for small datasets that is both simple and efficient. At each step, it inserts a new element into the already sorted sublist, forming a larger ordered list. This process repeats until all input data has been processed.

Time Complexity

• Worst case: O(n^2)
• Average case: O(n^2)
• Best case (already sorted): O(n)

C Implementation

#include <stdio.h>
void insertionSort(int array[], int length) {
    for(int step=1; step<length; step++) {
        // Current element to be inserted
        int key=array[step];
        // Index for finding the position to insert key
        int j=step-1;
        while(j>=0 && array[j]>key) {
            array[j+1]=array[j];
            --j;
        }
        array[j+1]=key; // Insert current number
    }
}
void printArray(int array[], int length) {
    for(int index=0; index<length; index++) {
        printf("%d ", array[index]);
    }
    printf("\n");
}
int main() {
    int data[]={9, 5, 6, 4, 8};
    unsigned long length=sizeof(data)/sizeof(data[0]);
    printf("Original array:\n");
    printArray(data, length);
    insertionSort(data, length);
    printf("Sorted array:\n");
    printArray(data, length);
    return 0;
}

Conclusion

This article introduced three basic and commonly used sorting algorithms in C, including Bubble Sort, Selection Sort, and Insertion Sort. Although these algorithms are not very efficient, they are very helpful for learning and understanding fundamental concepts. In practical applications, we often use more efficient and complex data structures and algorithms to handle large datasets. However, mastering these foundational concepts is an important step towards becoming an excellent programmer.