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

Source: https://skills101.in/learn/c-programming/c-sorting-and-searching — Skills101 free tutorial (C Programming). Updated 2026-11-21.

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.

## 1. Linear search

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

```c
#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;
}
```

```text
3 -1
```

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

## 2. Binary search

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](https://skills101.in/learn-img/c-programming/binary-search-steps.svg)

```c
#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;
}
```

```text
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.

```c
#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;
}
```

```text
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.

```c
#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;
}
```

```text
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](https://skills101.in/learn-img/c-programming/insertion-sort-trace.svg)

```c
#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;
}
```

```text
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:

```c
#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;
}
```

```text
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.

| Algorithm | Best | Average | Worst | Extra memory | Stable? |
|---|---|---|---|---|---|
| Linear search | O(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 sort | O(n²) | O(n²) | O(n²) | O(1) | no |
| Insertion sort | O(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 quiz and free certificate: https://skills101.in/learn/c-programming/c-sorting-and-searching