Sorting & Searching

Quick check before you start: Can you trace through a loop that finds the minimum element in an array? If so, skip to Selection Sort. If not, review arrays in the previous lesson first.

Practice this topic: Sorting skill drill

After this lesson, you will be able to:

• Implement selection sort on an integer array using nested loops and the swap pattern
• Trace through selection sort pass-by-pass on a small array
• Implement binary search on a sorted array
• Use qsort from <stdlib.h> with a comparator function
• Explain the difference between O(n^2) and O(n log n) sorting

Why Build Your Own Sort?

Java has Arrays.sort(). Python has sorted(). Why implement sorting from scratch?

Because sorting is the algorithm that teaches you how algorithms work. When you implement selection sort, you practice array traversal, comparison, swapping, and loop design — all at once. In this course, we use selection sort — not because it is the fastest, but because it is the clearest to understand and trace.

Selection Sort

The idea: find the smallest element and put it first. Then find the next smallest and put it second. Repeat until sorted.

The Swap Pattern

Swapping two elements requires a temporary variable:

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

Common Pitfall: a = b; b = a; does not work — after the first assignment, the original value of a is lost. You need a temporary variable.

The Algorithm

void selection_sort(int arr[], int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        int min_index = i;

        for (int j = i + 1; j < size; j++)
        {
            if (arr[j] < arr[min_index])
            {
                min_index = j;
            }
        }

        if (min_index != i)
        {
            int temp = arr[i];
            arr[i] = arr[min_index];
            arr[min_index] = temp;
        }
    }
}

Tracing Through an Example

Starting array: {64, 25, 12, 22, 11}

Pass 1 (i=0): Find minimum in entire array — 11 at index 4. Swap with index 0.

{11, 25, 12, 22, 64}

Pass 2 (i=1): Find minimum in indices 1-4 — 12 at index 2. Swap with index 1.

{11, 12, 25, 22, 64}

Pass 3 (i=2): Find minimum in indices 2-4 — 22 at index 3. Swap with index 2.

{11, 12, 22, 25, 64}

Pass 4 (i=3): Find minimum in indices 3-4 — 25 at index 3. Already in place.

{11, 12, 22, 25, 64}    <- Sorted!

The outer loop runs n-1 times. For each pass, the inner loop scans the remaining unsorted elements to find the minimum. This gives O(n^2) time complexity.

Bubble Sort

Bubble sort repeatedly walks through the array, swapping adjacent elements that are out of order:

void bubble_sort(int arr[], int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = 0; j < size - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Bubble sort is also O(n^2). It is simpler to code but generally slower than selection sort in practice because it performs more swaps. Selection sort is the preferred algorithm in this course.

Binary Search

Linear search checks every element — O(n). On a sorted array, binary search cuts the search space in half each step — O(log n):

int binary_search(const int arr[], int size, int target)
{
    int low = 0;
    int high = size - 1;

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

        if (arr[mid] == target)
        {
            return mid;
        }
        else if (arr[mid] < target)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return -1;    // Not found
}

Key Insight: Binary search requires a sorted array. If the array is not sorted, the algorithm does not work. Always sort first, then search. The tradeoff: sorting costs O(n^2) with selection sort, but if you search many times, the O(log n) per search pays off.

From Java: This is the same algorithm behind Arrays.binarySearch(). The logic is identical — the difference is that C has no built-in version, so you write it yourself.

qsort: The Standard Library Sort

C’s standard library provides qsort in <stdlib.h>. It sorts any data type using a comparator function you provide:

#include <stdlib.h>

int compare_ints(const void *a, const void *b)
{
    int int_a = *(const int *)a;
    int int_b = *(const int *)b;
    return int_a - int_b;
}

int main(void)
{
    int arr[] = {64, 25, 12, 22, 11};
    int size = sizeof(arr) / sizeof(arr[0]);

    qsort(arr, size, sizeof(int), compare_ints);

    // arr is now {11, 12, 22, 25, 64}
    return 0;
}

The comparator function takes two const void * pointers (generic pointers to any type), casts them to the correct type, and returns:

• Negative if a should come before b
• Zero if a and b are equal
• Positive if a should come after b

qsort uses an O(n log n) algorithm internally, making it much faster than selection sort on large arrays. For small arrays in labs, selection sort is fine. For larger datasets, use qsort.

From Java: qsort with a comparator is the C equivalent of Arrays.sort(arr, comparator) in Java. The comparator contract (negative/zero/positive) is the same as Java’s Comparator.compare() method.

O(n^2) vs. O(n log n)

For an array of 1,000 elements, O(n^2) means roughly 1,000,000 comparisons. O(n log n) means roughly 10,000. The gap grows fast with larger inputs.

What Comes Next

You have now built sorting and searching algorithms by hand — the same algorithms that Java hides behind Arrays.sort() and Arrays.binarySearch(). You understand how data gets organized in memory and how comparator functions let a single sort work on any type.

Next week begins pointers and memory. Pointers are C’s most distinctive feature. Everything from here — dynamic allocation with calloc, linked lists, string manipulation — builds on understanding that variables have addresses and you can work with those addresses directly.