Master Search & Sort Algorithms in C: Linear, Binary, Bubble, Insertion, Quick, Merge

1 Linear Search

1.1 Problem

Linear search, also known as sequential search, checks each element of an array from one end until the target element is found.

1.2 Steps

The implementation follows these steps:

#include <stdio.h>

typedef char DataType;

int mySearch(DataType *ts, int n, const DataType d) {
    for (int i = 0; i < n; i++) {
        if (ts[i] == d)
            return i;
    }
    return -1;
}

int main() {
    char cs[6] = {'*','A','B','C','D','E'};
    printf("%d
", mySearch(cs, 6, '*'));
    printf("%d
", mySearch(cs, 6, 'A'));
    printf("%d
", mySearch(cs, 6, 'D'));
    printf("%d
", mySearch(cs, 6, 'C'));
    return 0;
}

2 Binary Search

2.1 Problem

Binary search (also called half‑interval search) finds a target value in a sorted array by repeatedly dividing the search interval in half.

2.2 Steps

Implementation steps include defining lower and upper bounds, calculating the middle index, comparing the middle element with the target, and adjusting bounds until the element is found or the interval is empty.

#include <stdio.h>

typedef char DataType;

int mySearch(DataType *ts, int n, const DataType d) {
    int L = 0;
    int R = n - 1;
    while (L <= R) {
        int M = (L + R) / 2;
        if (ts[M] == d)
            return M;
        if (ts[M] < d)
            L = M + 1;
        else
            R = M - 1;
    }
    return -1;
}

int main() {
    char cs[6] = {'*','A','B','C','D','E'};
    printf("%d
", mySearch(cs, 6, '*'));
    printf("%d
", mySearch(cs, 6, 'A'));
    printf("%d
", mySearch(cs, 6, 'D'));
    printf("%d
", mySearch(cs, 6, 'C'));
    return 0;
}

3 Bubble Sort

3.1 Problem

Bubble sort repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order, bubbling the largest unsorted element to its final position each pass.

3.2 Steps

The algorithm uses two nested loops: an outer loop for each pass and an inner loop for adjacent comparisons. A flag can stop the algorithm early when the array is already sorted.

#include <stdio.h>

typedef int DataType;

void bubble(DataType *a, int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = true;
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                DataType t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                flag = false;
            }
        }
        if (flag) break;
    }
}

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

int main() {
    int a[10] = {3,2,4,5,7,8,9,1,6,0};
    bubble(a, 10);
    print(a, 10);
    return 0;
}

4 Insertion Sort

4.1 Problem

Insertion sort builds a sorted array one element at a time by inserting each unsorted element into its correct position within the already sorted portion.

4.2 Steps

For each element starting from index 1, store it in a temporary variable, shift larger sorted elements to the right, and insert the temporary value at the correct location.

#include <stdio.h>

typedef int DataType;

void insert(DataType *a, int n) {
    for (int i = 1; i < n; i++) {
        DataType t = a[i];
        int j = i;
        while (j > 0 && a[j - 1] > t) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = t;
    }
}

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

int main() {
    int a[10] = {3,2,4,5,7,8,9,1,6,0};
    insert(a, 10);
    print(a, 10);
    return 0;
}

5 Selection Sort

5.1 Problem

Selection sort repeatedly selects the smallest remaining element and swaps it with the element at the current position.

5.2 Steps

For each position, find the minimum element in the unsorted portion and swap it with the element at the current index.

#include <stdio.h>

typedef int DataType;

void selects(DataType *a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[k])
                k = j;
        }
        if (k != i) {
            DataType tmp = a[k];
            a[k] = a[i];
            a[i] = tmp;
        }
    }
}

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

int main() {
    int a[10] = {3,2,4,5,7,8,9,1,6,0};
    selects(a, 10);
    print(a, 10);
    return 0;
}

6 Quick Sort

6.1 Problem

Quick sort partitions an array around a pivot so that elements less than the pivot are on the left and greater elements on the right, then recursively sorts the sub‑arrays.

6.2 Steps

The algorithm stops when the sub‑array size is one or zero. It uses two indices moving inward to swap out‑of‑order elements, then recursively sorts the left and right partitions.

#include <stdio.h>

typedef int DataType;

void qsorts(DataType *a, int n) {
    if (n <= 1) return;
    int L = 0;
    int R = n - 1;
    while (L < R) {
        while (L < R && a[L] <= a[R]) R--;
        DataType t = a[L];
        a[L] = a[R];
        a[R] = t;
        while (L < R && a[L] <= a[R]) L++;
        t = a[L];
        a[L] = a[R];
        a[R] = t;
    }
    qsorts(a, L);
    qsorts(a + L + 1, n - L - 1);
}

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

int main() {
    int a[10] = {3,2,4,5,7,8,9,1,6,0};
    qsorts(a, 10);
    print(a, 10);
    return 0;
}

7 Merge Sort

7.1 Problem

Merge sort recursively divides an array into halves, sorts each half, and then merges the sorted halves into a single ordered array.

7.2 Steps

The algorithm uses a recursive function to split the array, a merge function that combines two sorted sub‑arrays using a temporary buffer, and copies the merged result back into the original array.

#include <stdlib.h>
#include <stdio.h>

#define SIZE 8

void Merge(int sourceArr[], int startIndex, int midIndex, int endIndex) {
    int start = startIndex;
    int i, j, k;
    int tempArr[SIZE];
    for (i = midIndex + 1, j = startIndex; startIndex <= midIndex && i <= endIndex; j++) {
        if (sourceArr[startIndex] <= sourceArr[i])
            tempArr[j] = sourceArr[startIndex++];
        else
            tempArr[j] = sourceArr[i++];
    }
    if (startIndex <= midIndex)
        for (k = 0; k <= midIndex - startIndex; k++)
            tempArr[j + k] = sourceArr[startIndex + k];
    if (i <= endIndex)
        for (k = 0; k <= endIndex - i; k++)
            tempArr[j + k] = sourceArr[i + k];
    for (i = start; i <= endIndex; i++)
        sourceArr[i] = tempArr[i];
}

void MergeSort(int sourceArr[], int startIndex, int endIndex) {
    if (startIndex < endIndex) {
        int midIndex = (startIndex + endIndex) / 2;
        MergeSort(sourceArr, startIndex, midIndex);
        MergeSort(sourceArr, midIndex + 1, endIndex);
        Merge(sourceArr, startIndex, midIndex, endIndex);
    }
}

int main() {
    int a[SIZE] = {8,4,6,3,1,7,5,2};
    MergeSort(a, 0, SIZE - 1);
    for (int i = 0; i < SIZE; i++)
        printf("%d ", a[i]);
    printf("
");
    return 0;
}

Illustrations

The article includes diagrams (not shown here) that illustrate each algorithm’s process step by step.