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.
1. Linear search
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).
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.
#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 + 1ormid - 1, never justmid, or the loop can run forever. low + (high - low) / 2gives the same middle as(low + high) / 2but 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.
#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.
| 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)orlow = midin binary search. - Inner loop of bubble sort running to
ninstead ofn - 1, soa[j + 1]reads past the end. - In insertion sort, testing
a[j] > keybeforej >= 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.