Skills101

AdvancedC Programming · Lesson 18 of 21 · Updated ·

Searching and Sorting Programs in C — Linear and Binary Search, Bubble, Selection and Insertion Sort

Searching and sorting are the first "real" algorithms most students write in C, and they appear in every BCA, B.Tech and MCA lab file. Interviewers also like them because they test loops, arrays and careful thinking about boundaries. This lesson gives one clean version of each program, traces it, and compares them.

Throughout, n is the number of elements, and we count comparisons to see how much work each algorithm does.

Check each element from the start until you find the target. It works on any array, sorted or not.

#include <stdio.h>

int linear_search(const int a[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (a[i] == key)
            return i;          /* found: return the index */
    return -1;                 /* not found */
}

int main(void) {
    int roll[] = {41, 7, 33, 19, 25, 8};
    int n = sizeof(roll) / sizeof(roll[0]);
    printf("%d %d\n", linear_search(roll, n, 19), linear_search(roll, n, 50));
    return 0;
}
3 -1

Worst case: n comparisons (the key is last or missing). Time complexity O(n).

If the array is sorted, we can do much better. Look at the middle element:

  • equal to the key → found;
  • key is smaller → it can only be in the left half;
  • key is larger → it can only be in the right half.

Each step throws away half of the remaining elements, so it needs only about log₂ n steps. For 1,000,000 elements that is about 20 steps instead of up to 1,000,000.

Binary search for 37 in a sorted array of 9 elements: step 1 checks the middle value 30 and goes right, step 2 checks 45 and goes left, step 3 checks 37 and finds it at index 5

#include <stdio.h>

int binary_search(const int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   /* avoids overflow of low + high */
        if (a[mid] == key)
            return mid;
        else if (a[mid] < key)
            low = mid + 1;                  /* search the right half */
        else
            high = mid - 1;                 /* search the left half */
    }
    return -1;
}

int main(void) {
    int a[] = {4, 9, 15, 23, 30, 37, 45, 51, 60};
    int n = sizeof(a) / sizeof(a[0]);
    printf("%d %d %d\n", binary_search(a, n, 37), binary_search(a, n, 4), binary_search(a, n, 40));
    return 0;
}
5 0 -1

Three details matter:

  • The loop condition is low <= high (with <, a one-element range is never checked).
  • Move to mid + 1 or mid - 1, never just mid, or the loop can run forever.
  • low + (high - low) / 2 gives the same middle as (low + high) / 2 but cannot overflow for very large indexes.

3. Bubble sort

Compare neighbours and swap them if they are in the wrong order. After the first pass, the largest element has "bubbled" to the end. After pass 2, the second largest is in place, and so on.

An important improvement: if a whole pass makes no swap, the array is already sorted and we can stop.

#include <stdio.h>

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

void bubble_sort(int a[], int n) {
    for (int pass = 0; pass < n - 1; pass++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - pass; j++) {   /* the last 'pass' items are already in place */
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                swapped = 1;
            }
        }
        printf("after pass %d: ", pass + 1);
        print(a, n);
        if (!swapped)
            break;                                  /* already sorted */
    }
}

int main(void) {
    int a[] = {5, 1, 4, 2, 8};
    bubble_sort(a, 5);
    return 0;
}
after pass 1: 1 4 2 5 8
after pass 2: 1 2 4 5 8
after pass 3: 1 2 4 5 8

Pass 3 made no swaps, so the loop stopped early. Worst case O(n²); best case (already sorted) O(n) thanks to the swapped flag.

4. Selection sort

Find the smallest element in the unsorted part and swap it to the front. Repeat for the rest.

#include <stdio.h>

void selection_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[min])
                min = j;
        int t = a[i]; a[i] = a[min]; a[min] = t;   /* at most one swap per pass */
    }
}

int main(void) {
    int a[] = {64, 25, 12, 22, 11};
    selection_sort(a, 5);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}
11 12 22 25 64

Selection sort always makes about n²/2 comparisons, even on sorted input, so it is O(n²) in every case. Its one advantage: it makes at most n − 1 swaps, useful when writing to memory is expensive.

5. Insertion sort

This is how most people sort a hand of playing cards. Take the next element and slide it left into its correct place among the already-sorted elements.

Insertion sort of 7 3 5 1: in each row the next card, marked in orange, is slid left past larger values until it fits, giving 3 7 5 1, then 3 5 7 1, then 1 3 5 7

#include <stdio.h>

void insertion_sort(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) {    /* shift bigger elements right */
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;                    /* drop key into the gap */
    }
}

int main(void) {
    int a[] = {7, 3, 5, 1};
    insertion_sort(a, 4);
    for (int i = 0; i < 4; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}
1 3 5 7

On a nearly sorted array the while loop hardly runs, so insertion sort is close to O(n). That is why real library sorts often switch to insertion sort for small pieces of the array.

6. Counting the work

Here we count the comparisons each sort makes on the same 8 numbers, in three situations:

#include <stdio.h>
#include <string.h>

long cmp;

void bubble(int a[], int n) {
    for (int p = 0; p < n - 1; p++) {
        int sw = 0;
        for (int j = 0; j < n - 1 - p; j++) {
            cmp++;
            if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; sw = 1; }
        }
        if (!sw) break;
    }
}

void selection(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int m = i;
        for (int j = i + 1; j < n; j++) { cmp++; if (a[j] < a[m]) m = j; }
        int t = a[i]; a[i] = a[m]; a[m] = t;
    }
}

void insertion(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0) {
            cmp++;
            if (a[j] <= key) break;
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

int main(void) {
    int data[3][8] = {{1, 2, 3, 4, 5, 6, 7, 8}, {6, 2, 8, 1, 7, 3, 5, 4}, {8, 7, 6, 5, 4, 3, 2, 1}};
    const char *name[] = {"sorted ", "random ", "reverse"};
    void (*sorts[])(int[], int) = {bubble, selection, insertion};
    printf("input    bubble selection insertion\n");
    for (int d = 0; d < 3; d++) {
        printf("%s", name[d]);
        for (int s = 0; s < 3; s++) {
            int a[8];
            memcpy(a, data[d], sizeof a);
            cmp = 0;
            sorts[s](a, 8);
            printf(" %8ld", cmp);
        }
        printf("\n");
    }
    return 0;
}
input    bubble selection insertion
sorted         7       28        7
random        25       28       20
reverse       28       28       28

Selection sort does 28 comparisons (8 × 7 / 2) no matter what. Bubble and insertion sort adapt: only 7 comparisons when the data is already sorted.

AlgorithmBestAverageWorstExtra memoryStable?
Linear searchO(1)O(n)O(n)O(1)—
Binary search (sorted input)O(1)O(log n)O(log n)O(1)—
Bubble sort (with flag)O(n)O(n²)O(n²)O(1)yes
Selection sortO(n²)O(n²)O(n²)O(1)no
Insertion sortO(n)O(n²)O(n²)O(1)yes

A sort is stable if equal elements keep their original order. This matters when you sort students by marks and want students with equal marks to stay in roll-number order. For large data, use faster O(n log n) methods such as merge sort, quick sort or the library's qsort.

Common mistakes

  • Running binary search on an unsorted array — it returns wrong answers without any error.
  • Writing while (low < high) or low = mid in binary search.
  • Inner loop of bubble sort running to n instead of n - 1, so a[j + 1] reads past the end.
  • In insertion sort, testing a[j] > key before j >= 0 — the order matters, because && stops at the first false condition.
  • Forgetting that arrays are passed as pointers: the function sorts the caller's array itself.

Quick recap

  • Linear search: any array, O(n). Binary search: sorted array only, O(log n).
  • Bubble sort swaps neighbours; with a "no swap" flag its best case is O(n).
  • Selection sort picks the minimum each pass: always O(n²) comparisons, at most n − 1 swaps.
  • Insertion sort slides each element into place: fast on nearly sorted data.
  • All three simple sorts are O(n²) in the worst case and sort in place; bubble and insertion are stable.

Practice what you learned

📝 Quiz: Searching and Sorting in C5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →