Sorting and Searching Algorithms in C

Sorting and searching are two of the most fundamental operations in computer science. Sorting arranges elements in a specific order (ascending or descending). Searching finds the position of a specific element in a collection. Every program that manages data relies on these operations.

Sorting Algorithms

1. Bubble Sort

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. In each pass, the largest unsorted element "bubbles up" to its correct position at the end.

Time Complexity: O(n²) — best for small arrays or nearly sorted data

#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]) {
                int temp  = arr[j];
                arr[j]    = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22};
    int n = 5;

    printf("Before: "); printArray(arr, n);
    bubbleSort(arr, n);
    printf("After : "); printArray(arr, n);

    return 0;
}

Output

Before: 64 34 25 12 22 
After : 12 22 25 34 64 

How Bubble Sort Works (Step by Step for {64, 34, 25})

Pass 1: 64 34 25 → 34 64 25 → 34 25 64
Pass 2: 34 25 64 → 25 34 64
Pass 3: 25 34 64 (sorted)

2. Selection Sort

Selection Sort finds the minimum element in the unsorted portion of the array and places it at the beginning. It divides the array into a sorted left part and an unsorted right part.

Time Complexity: O(n²)

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx])
                minIdx = j;
        }
        // Swap minimum with current position
        int temp       = arr[minIdx];
        arr[minIdx]    = arr[i];
        arr[i]         = temp;
    }
}

int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = 5;

    printf("Before: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);

    selectionSort(arr, n);

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

    return 0;
}

Output

Before: 29 10 14 37 13 
After : 10 13 14 29 37 

3. Insertion Sort

Insertion Sort works like sorting playing cards in hand. It picks one element at a time and inserts it into its correct position among the already-sorted elements.

Time Complexity: O(n²) worst case, O(n) for nearly sorted data — often fastest for small arrays

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j   = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {5, 2, 4, 6, 1, 3};
    int n = 6;

    printf("Before: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);

    insertionSort(arr, n);

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

    return 0;
}

Output

Before: 5 2 4 6 1 3 
After : 1 2 3 4 5 6 

4. Merge Sort

Merge Sort uses the divide and conquer strategy. It divides the array into two halves, recursively sorts each half, and then merges the two sorted halves. It is more efficient than the previous three algorithms for large datasets.

Time Complexity: O(n log n) — efficient and consistent

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];

    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else                arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = 7;

    printf("Before: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);

    mergeSort(arr, 0, n - 1);

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

    return 0;
}

Output

Before: 38 27 43 3 9 82 10 
After : 3 9 10 27 38 43 82 

5. Quick Sort

Quick Sort picks a pivot element and partitions the array so all elements smaller than the pivot come before it and all larger elements come after. It then recursively sorts the two partitions.

Time Complexity: O(n log n) average, O(n²) worst case — typically the fastest in practice

#include <stdio.h>

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i     = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
    int tmp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = tmp;
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = 6;

    printf("Before: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);

    quickSort(arr, 0, n - 1);

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

    return 0;
}

Output

Before: 10 7 8 9 1 5 
After : 1 5 7 8 9 10 

Sorting Algorithm Comparison

Searching Algorithms

1. Linear Search

Linear Search goes through each element one by one from the beginning until the target is found or the entire array is exhausted.

Time Complexity: O(n) — works on any array (sorted or unsorted)

#include <stdio.h>

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target)
            return i;   // return index where found
    }
    return -1;          // not found
}

int main() {
    int arr[] = {15, 30, 5, 72, 42, 18};
    int n = 6;
    int target = 42;

    int result = linearSearch(arr, n, target);

    if (result != -1)
        printf("Found %d at index %d\n", target, result);
    else
        printf("%d not found\n", target);

    return 0;
}

Output

Found 42 at index 4

2. Binary Search

Binary Search works only on a sorted array. It compares the target with the middle element. If they match, it returns the position. If the target is smaller, it searches the left half. If larger, it searches the right half. Each comparison eliminates half the remaining elements.

Time Complexity: O(log n) — much faster than linear search for large arrays

#include <stdio.h>

int binarySearch(int arr[], int n, int target) {
    int low  = 0;
    int high = n - 1;

    while (low <= high) {
        int mid = (low + high) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            low = mid + 1;   // target is in right half
        else
            high = mid - 1;  // target is in left half
    }
    return -1;  // not found
}

int main() {
    int arr[] = {5, 12, 18, 25, 36, 48, 65, 80};
    int n     = 8;
    int target = 36;

    int result = binarySearch(arr, n, target);

    if (result != -1)
        printf("Found %d at index %d\n", target, result);
    else
        printf("%d not found\n", target);

    return 0;
}

Output

Found 36 at index 4

Binary Search — Step Trace for target = 36

Array: 5  12  18  25  36  48  65  80
Index: 0   1   2   3   4   5   6   7

Step 1: low=0, high=7, mid=3 → arr[3]=25 < 36 → search right → low=4
Step 2: low=4, high=7, mid=5 → arr[5]=48 > 36 → search left → high=4
Step 3: low=4, high=4, mid=4 → arr[4]=36 == 36 → FOUND at index 4

Recursive Binary Search

int binarySearchRec(int arr[], int low, int high, int target) {
    if (low > high) return -1;  // base case: not found

    int mid = (low + high) / 2;

    if (arr[mid] == target)  return mid;
    if (arr[mid] < target)   return binarySearchRec(arr, mid + 1, high, target);
    return binarySearchRec(arr, low, mid - 1, target);
}

Linear Search vs Binary Search

Practical Example — Sort then Search

#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]) {
                int t = arr[j]; arr[j] = arr[j+1]; arr[j+1] = t;
            }
}

int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {45, 12, 67, 23, 89, 34};
    int n = 6;
    int target = 67;

    bubbleSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    int idx = binarySearch(arr, n, target);
    if (idx != -1)
        printf("Found %d at sorted index %d\n", target, idx);
    else
        printf("%d not found\n", target);

    return 0;
}

Output

Sorted array: 12 23 34 45 67 89 
Found 67 at sorted index 4

Summary

Sorting algorithms arrange data in order and differ in efficiency. For small datasets, Bubble, Selection, and Insertion sort are simple to implement. For large datasets, Merge Sort and Quick Sort are far more efficient at O(n log n). Searching algorithms locate elements in a collection. Linear Search is simple and works on any array, while Binary Search is dramatically faster but requires a sorted array. In real applications, sort once and then binary-search many times for maximum efficiency.