Sorting in C

Sorting is the process of arranging data in a specific order — usually ascending or descending.

A good sorting algorithm makes searching, analyzing, and processing data easier.

Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. After each pass, the largest unsorted element “bubbles up” to the end.

Algorithm (Pseudocode)

repeat for n-1 passes:
    for i = 0 to n-2:
        if a[i] > a[i+1]:
            swap a[i], a[i+1]

C Implementation

void bubbleSort(int a[], int n) {
    for (int pass = 0; pass < n-1; pass++) {
        for (int i = 0; i < n-pass-1; i++) {
            if (a[i] > a[i+1]) {
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
        }
    }
}

Example

Input: 5 3 2 4
Pass 1 → 3 2 4 5  
Pass 2 → 2 3 4 5  
Pass 3 → 2 3 4 5  

Time Complexity: O(n²)

Selection sort finds the **minimum** element from the unsorted part of the array and swaps it with the first element of that part.

Algorithm (Pseudocode)

for i = 0 to n-1:
    min = i
    for j = i+1 to n-1:
        if a[j] < a[min]:
            min = j
    swap a[i], a[min]

C Implementation

void selectionSort(int a[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < n; j++) {
            if (a[j] < a[minIndex])
                minIndex = j;
        }
        int temp = a[i];
        a[i] = a[minIndex];
        a[minIndex] = temp;
    }
}

Example

Input: 29 10 14 37 13
Select 10 → swap with 29  
Select 13 → swap with 14  
Result: 10 13 14 29 37

Time Complexity: O(n²)

In insertion sort, elements are inserted one by one into their correct position in the already sorted part of the array.

Algorithm (Pseudocode)

for i = 1 to n-1:
    key = a[i]
    j = i - 1
    while j >= 0 and a[j] > key:
        a[j+1] = a[j]
        j--
    a[j+1] = key

C Implementation

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;

        while (j >= 0 && a[j] > key) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }
}

Example

Input: 5 2 4 6 1  
Insert 2 → 2 5 4 6 1  
Insert 4 → 2 4 5 6 1  
Insert 6 → 2 4 5 6 1  
Insert 1 → 1 2 4 5 6

Time Complexity: O(n²) average, Best Case: O(n) when array already sorted.

#include <stdio.h>

void bubbleSort(int a[], int n);
void selectionSort(int a[], int n);
void insertionSort(int a[], int n);

int main() {
    int n, choice;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int a[n];
    printf("Enter %d numbers: ", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    printf("\n1. Bubble Sort\n2. Selection Sort\n3. Insertion Sort\n");
    printf("Choose method: ");
    scanf("%d", &choice);

    if (choice == 1) bubbleSort(a, n);
    else if (choice == 2) selectionSort(a, n);
    else insertionSort(a, n);

    printf("\nSorted Array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}