Module 4.3

Array Algorithms

Master the fundamental algorithms every programmer must know! Learn how to search through data efficiently with linear and binary search, and organize data using classic sorting algorithms like bubble sort, insertion sort, selection sort, and the powerful quick sort.

45 min read
Beginner to Intermediate
Interactive Visualizations
What You'll Learn
  • Linear search for unsorted arrays
  • Binary search for sorted arrays
  • Bubble, insertion, and selection sort
  • Quick sort with divide-and-conquer
  • Big O notation and efficiency analysis
Contents
01

Introduction to Algorithms

An algorithm is simply a step-by-step procedure to solve a problem. When working with arrays, two of the most common problems are searching (finding an element) and sorting (arranging elements in order). Mastering these algorithms is fundamental to becoming a proficient programmer.

Imagine you have a bookshelf with 1000 books and you need to find a specific one. You could check every book one by one (slow but works), or if the books are arranged alphabetically, you could open to the middle and quickly narrow down where your book is (much faster!). This is the essence of choosing the right algorithm - the difference between seconds and hours of work.

Beginner Tip: Think of algorithms like recipes. Just as a recipe gives you step-by-step instructions to make a dish, an algorithm gives step-by-step instructions for a computer to solve a problem. Some recipes are quick and simple, others are complex but produce better results!

What is Algorithm Efficiency?

Not all algorithms are created equal. Some solve problems quickly, others take forever. We measure algorithm efficiency using Big O notation, which describes how the running time grows as the input size increases.

Concept

Big O Notation

Big O notation describes the worst-case performance of an algorithm as input size grows. It answers the question: "If I double my data, how much longer will my algorithm take?"

Think of it like travel time. Walking to a nearby store is O(1) - constant time regardless of distance. But walking across town takes longer the farther you go - that's O(n), where time grows with distance.

Common complexities: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic

Understanding Time Complexity

Here's how different time complexities compare. Imagine processing an array of 1000 elements:

O(1)

Constant Time

Always takes the same time, regardless of input size.

~1 operation

Example: Accessing array[5]

O(log n)

Logarithmic

Halves the problem each step. Very efficient!

~10 operations

Example: Binary search

O(n)

Linear

Time grows proportionally with input size.

~1,000 operations

Example: Linear search

O(n²)

Quadratic

Time squares with input size. Slow for large data!

~1,000,000 operations

Example: Bubble sort

Why This Matters: For 1000 elements, O(n²) does 1 million operations while O(log n) does only 10! As data grows, choosing the right algorithm becomes critical.

Practice Questions: Linear Search

Given:

char str[] = "hello world";
char target = 'o';

Task: Write a function to find the first occurrence of target in the string. Return the index if found, -1 otherwise.

Expected output: 4

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

int findChar(char str[], char target) {
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        if (str[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    char str[] = "hello world";
    char target = 'o';
    printf("Found at index: %d\n", findChar(str, target));  // 4
    return 0;
}

Given:

int arr[] = {1, 4, 2, 4, 3, 4, 5};
int target = 4;

Task: Write a function that counts how many times target appears in the array.

Expected output: 3

Show Solution 
#include <stdio.h>

int countOccurrences(int arr[], int size, int target) {
    int count = 0;
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            count++;
        }
    }
    return count;
}

int main() {
    int arr[] = {1, 4, 2, 4, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Count: %d\n", countOccurrences(arr, size, 4));  // 3
    return 0;
}

Given:

int arr[] = {5, 3, 7, 3, 8, 3, 2};
int target = 3;

Task: Modify linear search to find the LAST occurrence of target instead of the first.

Expected output: 5 (last 3 is at index 5)

Show Solution 
#include <stdio.h>

int lastOccurrence(int arr[], int size, int target) {
    int lastIndex = -1;
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            lastIndex = i;  // Update each time we find it
        }
    }
    return lastIndex;
}

int main() {
    int arr[] = {5, 3, 7, 3, 8, 3, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Last occurrence at: %d\n", lastOccurrence(arr, size, 3));  // 5
    return 0;
}

Given:

int arr[] = {2, 7, 11, 15};
int targetSum = 9;

Task: Find two numbers in the array that add up to targetSum. Print their indices.

Expected output: Indices: 0 and 1 (because 2 + 7 = 9)

Hint: Use two nested loops (brute force approach).

Show Solution 
#include <stdio.h>

void findTwoSum(int arr[], int size, int targetSum) {
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            if (arr[i] + arr[j] == targetSum) {
                printf("Indices: %d and %d\n", i, j);
                return;
            }
        }
    }
    printf("No pair found\n");
}

int main() {
    int arr[] = {2, 7, 11, 15};
    int size = sizeof(arr) / sizeof(arr[0]);
    findTwoSum(arr, size, 9);  // Indices: 0 and 1
    return 0;
}

Practice Questions: Binary Search

Given:

int n = 16;

Task: Find the integer square root of n using binary search. For 16, the answer is 4.

Hint: Search between 1 and n. Check if mid * mid equals n.

Show Solution 
#include <stdio.h>

int sqrtBinarySearch(int n) {
    if (n == 0 || n == 1) return n;
    
    int left = 1, right = n, result = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (mid == n / mid) {
            return mid;  // Exact square root
        }
        else if (mid < n / mid) {
            result = mid;  // Store potential answer
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return result;
}

int main() {
    printf("sqrt(16) = %d\n", sqrtBinarySearch(16));  // 4
    printf("sqrt(8) = %d\n", sqrtBinarySearch(8));    // 2
    return 0;
}

Given:

int arr[] = {1, 2, 2, 2, 3, 4, 5};
int target = 2;

Task: Find the FIRST occurrence of target in a sorted array that may contain duplicates.

Expected output: 1 (first 2 is at index 1)

Show Solution 
#include <stdio.h>

int firstOccurrence(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            result = mid;      // Found, but keep searching left
            right = mid - 1;   // Look for earlier occurrence
        }
        else if (arr[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return result;
}

int main() {
    int arr[] = {1, 2, 2, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("First occurrence: %d\n", firstOccurrence(arr, size, 2));  // 1
    return 0;
}

Given:

int arr[] = {1, 1, 2, 2, 2, 2, 3};
int target = 2;

Task: Count how many times target appears using binary search (not linear search).

Expected output: 4

Hint: Find first and last occurrence, then calculate count.

Show Solution 
#include <stdio.h>

int firstOccurrence(int arr[], int size, int target) {
    int left = 0, right = size - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) { result = mid; right = mid - 1; }
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return result;
}

int lastOccurrence(int arr[], int size, int target) {
    int left = 0, right = size - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) { result = mid; left = mid + 1; }
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return result;
}

int countOccurrences(int arr[], int size, int target) {
    int first = firstOccurrence(arr, size, target);
    if (first == -1) return 0;
    int last = lastOccurrence(arr, size, target);
    return last - first + 1;
}

int main() {
    int arr[] = {1, 1, 2, 2, 2, 2, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Count: %d\n", countOccurrences(arr, size, 2));  // 4
    return 0;
}

Given:

int arr[] = {4, 5, 6, 7, 0, 1, 2};  // Sorted array rotated at pivot
int target = 0;

Task: Find target in a rotated sorted array. The array was originally sorted, then rotated at some pivot.

Expected output: 4

Show Solution 
#include <stdio.h>

int searchRotated(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) return mid;
        
        // Check which half is sorted
        if (arr[left] <= arr[mid]) {
            // Left half is sorted
            if (target >= arr[left] && target < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half is sorted
            if (target > arr[mid] && target <= arr[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

int main() {
    int arr[] = {4, 5, 6, 7, 0, 1, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Found at: %d\n", searchRotated(arr, size, 0));  // 4
    return 0;
}
04

Basic Sorting Algorithms

Sorting rearranges elements in a specific order (ascending or descending). While there are many sorting algorithms, we'll focus on three fundamental ones that every programmer should understand: Bubble Sort, Selection Sort, and Insertion Sort.

These algorithms are called "simple" or "elementary" sorting algorithms. They have O(n²) time complexity, making them inefficient for large datasets. However, they're excellent for learning because they're intuitive to understand and implement.

Bubble Sort

Algorithm

Bubble Sort

Bubble Sort repeatedly steps through the array, compares adjacent elements, and swaps them if they're in the wrong order. The largest unsorted element "bubbles up" to its correct position at the end of each pass.

Imagine bubbles rising in water - bigger bubbles rise faster. Similarly, larger numbers "bubble" to the right end of the array with each pass through the data.

Time Complexity: O(n²) average and worst case, O(n) best case (already sorted). Space: O(1)

// Bubble Sort
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // Flag to detect if any swaps occurred
        int swapped = 0;
        
        // Last i elements are already sorted
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap adjacent elements
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        
        // If no swaps occurred, array is sorted
        if (swapped == 0) break;
    }
}

Imagine bubbles rising in a glass of soda - bigger bubbles rise faster! The outer loop runs n-1 times (we need n-1 passes to fully sort). The inner loop compares neighbors: if left is greater than right, we swap them. After each pass, the largest unsorted number "bubbles up" to its correct position.

The swapped flag is clever: if nothing swapped, the array is already sorted, so we stop early! This optimization makes bubble sort O(n) for already-sorted arrays instead of O(n²).

Selection Sort

Algorithm

Selection Sort

Selection Sort divides the array into sorted and unsorted portions. It repeatedly finds the minimum element from the unsorted portion and moves it to the end of the sorted portion.

Think of selecting the smallest card from your hand and placing it at the front. Then select the next smallest from the remaining cards. Repeat until all cards are in order.

Time Complexity: O(n²) for all cases. Space: O(1). Note: Performs fewer swaps than bubble sort.

// Selection Sort
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // Find the minimum element in unsorted portion
        int minIndex = i;
        
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // Swap minimum with first unsorted element
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

Think of picking the smallest apple from a basket and placing it in a new row. Start at position 0 and scan the entire array to find the smallest element. Swap that smallest element with position 0, and now position 0 is sorted! Move to position 1, find the smallest in the remaining elements, and swap it to position 1. Repeat until the whole array is sorted.

Selection sort always does exactly n-1 swaps, making it good when swapping is expensive. However, it always takes O(n²) time even if the array is already sorted.

Insertion Sort

Algorithm

Insertion Sort

Insertion Sort builds the final sorted array one element at a time. It takes each element and inserts it into its correct position within the already-sorted portion of the array.

This is exactly how you'd sort playing cards in your hand! You pick up cards one by one and insert each new card into its correct position among the cards you're already holding.

Time Complexity: O(n²) average/worst, O(n) best case. Space: O(1). Best for: Small or nearly-sorted data.

// Insertion Sort
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // Element to insert
        int j = i - 1;
        
        // Shift elements greater than key to the right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        // Insert key at correct position
        arr[j + 1] = key;
    }
}

This is exactly how you sort playing cards in your hand! Start with the second card (index 1) since a single card is already "sorted". Take the current card (key) out and hold it. Compare with cards to the left and shift any larger cards one position right. Then insert the held card into the gap you created.

For arrays that are almost sorted, insertion sort is incredibly fast - almost O(n)! Many fast algorithms use insertion sort for small sub-arrays because of its low overhead.

Comparing Basic Sorting Algorithms

Algorithm Best Case Average Case Worst Case Space Stable? Best For
Bubble Sort O(n) O(n²) O(n²) O(1) Yes Educational purposes
Selection Sort O(n²) O(n²) O(n²) O(1) No Few swaps needed
Insertion Sort O(n) O(n²) O(n²) O(1) Yes Small/nearly sorted
What does "Stable" mean? A stable sort maintains the relative order of equal elements. If you have two items with the same value, a stable sort keeps them in their original order. This matters when sorting by multiple keys (e.g., sort by name, then by age).

Practice Questions: Basic Sorting

Given:

int arr[] = {5, 2, 8, 1, 9};

Task: Modify bubble sort to sort in DESCENDING order (largest to smallest).

Expected output: [9, 8, 5, 2, 1]

Show Solution 
#include <stdio.h>

void bubbleSortDesc(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            // Change > to < for descending
            if (arr[j] < arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {5, 2, 8, 1, 9};
    int n = 5;
    bubbleSortDesc(arr, n);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    // Output: 9 8 5 2 1
    return 0;
}

Given:

int arr[] = {7, 10, 4, 3, 20, 15};
int k = 3;

Task: Find the 3rd smallest element using selection sort logic (but stop after k iterations).

Expected output: 7 (sorted: 3, 4, 7, 10, 15, 20)

Show Solution 
#include <stdio.h>

int kthSmallest(int arr[], int n, int k) {
    // Run selection sort for only k iterations
    for (int i = 0; i < k; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        // Swap
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
    }
    return arr[k - 1];  // kth smallest is at index k-1
}

int main() {
    int arr[] = {7, 10, 4, 3, 20, 15};
    printf("3rd smallest: %d\n", kthSmallest(arr, 6, 3));  // 7
    return 0;
}

Given:

int arr[] = {2, 0, 1, 2, 1, 0};

Task: Sort the array so all 0s come first, then 1s, then 2s. Try to do it in a single pass!

Expected output: [0, 0, 1, 1, 2, 2]

Show Solution 
#include <stdio.h>

void sortColors(int arr[], int n) {
    int low = 0, mid = 0, high = n - 1;
    
    while (mid <= high) {
        if (arr[mid] == 0) {
            // Swap with low, move both pointers
            int temp = arr[low];
            arr[low] = arr[mid];
            arr[mid] = temp;
            low++;
            mid++;
        }
        else if (arr[mid] == 1) {
            mid++;  // 1 is in correct position
        }
        else {  // arr[mid] == 2
            // Swap with high, only decrement high
            int temp = arr[high];
            arr[high] = arr[mid];
            arr[mid] = temp;
            high--;
        }
    }
}

int main() {
    int arr[] = {2, 0, 1, 2, 1, 0};
    sortColors(arr, 6);
    for (int i = 0; i < 6; i++) printf("%d ", arr[i]);
    // Output: 0 0 1 1 2 2
    return 0;
}

Given:

int arr[] = {2, 4, 1, 3, 5};

Task: Count the number of "inversions" (pairs where i < j but arr[i] > arr[j]). Use bubble sort and count each swap.

Expected output: 3 (inversions: (2,1), (4,1), (4,3))

Show Solution 
#include <stdio.h>

int countInversions(int arr[], int n) {
    int count = 0;
    
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // This is an inversion, count it
                count++;
                // Swap
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return count;
}

int main() {
    int arr[] = {2, 4, 1, 3, 5};
    printf("Inversions: %d\n", countInversions(arr, 5));  // 3
    return 0;
}
05

Quick Sort

Quick Sort is one of the fastest and most widely used sorting algorithms. It uses a divide-and-conquer strategy: pick a "pivot" element, partition the array around it, then recursively sort the sub-arrays. Despite O(n²) worst case, its average O(n log n) performance makes it the go-to choice for most applications.

Algorithm

Quick Sort

Quick Sort selects a "pivot" element and partitions the array so that all elements smaller than the pivot come before it, and all larger elements come after. It then recursively applies the same logic to the sub-arrays.

Imagine organizing students by height. Pick one student (pivot) to stand in place. Everyone shorter moves to the left, everyone taller moves to the right. Now repeat this process for the left and right groups until everyone is in height order!

Time Complexity: O(n log n) average, O(n²) worst case (rare with good pivot). Space: O(log n) for recursion stack.

How Quick Sort Works

Step by Step

Quick Sort Process

1

Choose Pivot

Select an element as pivot (commonly last, first, or random)

2

Partition

Move smaller elements left of pivot, larger elements right

3

Recursion

Recursively apply quick sort to left and right sub-arrays

4

Combine

No explicit combining - elements are sorted in place!

Implementation in C

Swap Utility Function
// Swap utility function
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

Swapping two values is trickier than it looks. We need a temporary variable to hold the first value so we don't lose it, then copy the second value into the first position, and finally copy the temp (original first value) into the second position.

We use pointers (int* a) so the swap actually changes the original variables. Without pointers, we'd only swap copies and the originals would stay the same!

Partition Function
Setup
// Partition function - returns the pivot's final position
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // Choose last element as pivot
    int i = low - 1;        // Index of smaller element

The partition is the heart of quick sort. We set pivot = arr[high] to choose the last element as our "dividing line". The variable i = low - 1 tracks where small elements end (starts before the range).

Our goal is to rearrange so all elements smaller than pivot are on the left, and larger ones on the right. This is called the "Lomuto partition scheme" - simple and beginner-friendly!

Partitioning Loop
    for (int j = low; j < high; j++) {
        // If current element is smaller than pivot
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }

We scan through each element and decide: is it smaller than the pivot? Variable j scans from left to right, checking each element. If arr[j] < pivot, this element belongs in the "small" section, so we increment i and swap arr[i] with arr[j]. This moves the small element to the left side.

After this loop, all elements from low to i are smaller than pivot, and all elements from i+1 to high-1 are greater than or equal to pivot.

Place Pivot
    // Place pivot in its correct position
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

After the loop, we know exactly where the pivot belongs. Position i+1 is the first position of the "larger" section. We swap the pivot (at high) with the element at i+1. Now pivot is in its FINAL sorted position - it won't move again!

We return i+1 so quick sort knows where to split the array for recursion. Everything left of this position is smaller, everything right is larger.

Quick Sort Function
// Quick Sort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // Partition and get pivot position
        int pi = partition(arr, low, high);
        
        // Recursively sort elements before and after pivot
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

This is the main sorting function that uses divide-and-conquer. The condition if (low < high) means we only sort if there are at least 2 elements. We partition the array and get the pivot's final position (pi), then recursively sort the left part (elements from low to pi-1) and the right part (elements from pi+1 to high).

The pivot is already sorted (it's in its final position), so we skip it! Each recursive call works on smaller and smaller pieces until everything is sorted.

Wrapper Function
// Wrapper for easy calling
void quickSortWrapper(int arr[], int n) {
    quickSort(arr, 0, n - 1);
}

The actual quick sort needs low and high parameters, but users shouldn't have to think about that. This wrapper function takes just the array and its size, then automatically calls quickSort with low = 0 and high = n-1.

Now anyone can sort an array with: quickSortWrapper(myArray, size); - clean, simple, and hides the complexity of recursion from the user!

Visual Example: Sorting [8, 3, 1, 7, 0, 10, 2]

Step-by-Step

Quick Sort in Action

1

Initial Array

[8, 3, 1, 7, 0, 10, 2]

Pivot = 2 (last element). We'll rearrange so all elements smaller than 2 go left, larger go right.

2

After Partition

[1, 0, 2, 7, 8, 10, 3]

Pivot 2 is now at index 2 - its FINAL position! Elements left of 2 are smaller, right are larger.

3a

Left Sub-array

[1, 0] [0, 1]

Only 2 elements - one swap and done!

3b

Right Sub-array

[7, 8, 10, 3] [3, 7, 8, 10]

Recursively applies quick sort

Final Sorted Array

[0, 1, 2, 3, 7, 8, 10]

Complete Working Example

Include and Helper Functions
#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

Starting our program:

Every C program needs to include the libraries it uses:

  • #include <stdio.h> - Gives us printf() to display output
  • The swap function is defined first because partition() will need to use it
  • In C, you must define functions before you use them (or use prototypes)

This swap function takes pointers so it can actually change the original values.

Partition Function
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

The partition function in action:

This is the compact version of partition that does all the heavy lifting:

  • Pick the last element as pivot
  • Scan through and move smaller elements to the left side
  • Place pivot in its correct final position
  • Return where the pivot ended up

After partition runs, the pivot is perfectly placed - smaller values left, larger values right!

Quick Sort Function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

The quick sort recursion:

This compact version shows the elegant simplicity of quick sort:

  • If there's more than one element to sort (low < high)...
  • Partition the array and get the pivot's position
  • Sort the left portion (before pivot)
  • Sort the right portion (after pivot)

The recursion naturally stops when sub-arrays have 0 or 1 elements.

Print Utility
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

Helper function to see our results:

This simple function prints all elements of an array:

  • Loop through each element from 0 to size-1
  • Print each number followed by a space
  • After all numbers, print a newline to move to the next line

We'll use this to see the array before and after sorting.

Main Function
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Original array: ");
    printArray(arr, n);
    
    quickSort(arr, 0, n - 1);
    
    printf("Sorted array:   ");
    printArray(arr, n);
    
    return 0;
}

Putting it all together:

The main function demonstrates quick sort working on real data:

  • Create an unsorted array: {64, 34, 25, 12, 22, 11, 90}
  • Calculate the size (7 elements)
  • Print the original array so we can see the "before"
  • Call quickSort to sort the entire array
  • Print the sorted array to see the "after"

Output: "Original array: 64 34 25 12 22 11 90" then "Sorted array: 11 12 22 25 34 64 90"

Why Quick Sort is Popular

  • Fast in practice - O(n log n) average, often faster than merge sort
  • In-place sorting - Only O(log n) extra space for recursion
  • Cache efficient - Works on contiguous memory, good cache performance
  • Widely used - Many standard library sort functions use quick sort

Things to Watch Out For

  • Worst case O(n²) - When pivot is always smallest/largest
  • Not stable - Equal elements may be reordered
  • Recursive - Deep recursion can cause stack overflow
  • Pivot matters - Bad pivot selection hurts performance
Pro Tip: To avoid worst-case O(n²), use "median-of-three" pivot selection: pick the median of the first, middle, and last elements. This makes worst case very unlikely!

Practice Questions: Quick Sort

Given:

int arr[] = {10, 80, 30, 90, 40, 50, 70};
// pivot = 70 (last element)

Task: Manually trace the partition function. What does the array look like after partitioning? What index is returned?

Show Solution

Trace:

  • i = -1, pivot = 70
  • j=0: 10 < 70, swap arr[0] with arr[0], i=0 → [10, 80, 30, 90, 40, 50, 70]
  • j=1: 80 > 70, no swap
  • j=2: 30 < 70, swap arr[1] with arr[2], i=1 → [10, 30, 80, 90, 40, 50, 70]
  • j=3: 90 > 70, no swap
  • j=4: 40 < 70, swap arr[2] with arr[4], i=2 → [10, 30, 40, 90, 80, 50, 70]
  • j=5: 50 < 70, swap arr[3] with arr[5], i=3 → [10, 30, 40, 50, 80, 90, 70]
  • Finally: swap arr[4] with arr[6] → [10, 30, 40, 50, 70, 90, 80]

Result: Array = [10, 30, 40, 50, 70, 90, 80], returns index 4

Task: Modify the partition function to use the FIRST element as pivot instead of the last element.

int arr[] = {8, 3, 1, 7, 0, 10, 2};
// Use 8 as pivot instead of 2
Show Solution 
#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partitionFirst(int arr[], int low, int high) {
    int pivot = arr[low];  // First element as pivot
    int i = high + 1;
    
    for (int j = high; j > low; j--) {
        if (arr[j] > pivot) {
            i--;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i - 1], &arr[low]);
    return i - 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partitionFirst(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {8, 3, 1, 7, 0, 10, 2};
    quickSort(arr, 0, 6);
    for (int i = 0; i < 7; i++) printf("%d ", arr[i]);
    return 0;
}

Given:

int arr[] = {3, 2, 1, 5, 6, 4};
int k = 2;

Task: Find the 2nd largest element without fully sorting. Use partition logic from quick sort!

Expected output: 5

Show Solution 
#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a; *a = *b; *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high], i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

int quickSelect(int arr[], int low, int high, int k) {
    if (low == high) return arr[low];
    
    int pi = partition(arr, low, high);
    
    if (pi == k) return arr[pi];
    else if (pi < k) return quickSelect(arr, pi + 1, high, k);
    else return quickSelect(arr, low, pi - 1, k);
}

int findKthLargest(int arr[], int n, int k) {
    // kth largest = (n-k)th smallest (0-indexed)
    return quickSelect(arr, 0, n - 1, n - k);
}

int main() {
    int arr[] = {3, 2, 1, 5, 6, 4};
    printf("2nd largest: %d\n", findKthLargest(arr, 6, 2));  // 5
    return 0;
}

Given:

int arr[] = {4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4};

Task: Implement 3-way quick sort that handles duplicates efficiently. Partition into: elements < pivot, elements = pivot, elements > pivot.

Show Solution 
#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a; *a = *b; *b = temp;
}

void threeWayPartition(int arr[], int low, int high, int* lt, int* gt) {
    int pivot = arr[low];
    int i = low;
    *lt = low;
    *gt = high;
    
    while (i <= *gt) {
        if (arr[i] < pivot) {
            swap(&arr[i], &arr[*lt]);
            (*lt)++;
            i++;
        }
        else if (arr[i] > pivot) {
            swap(&arr[i], &arr[*gt]);
            (*gt)--;
        }
        else {
            i++;
        }
    }
}

void quickSort3Way(int arr[], int low, int high) {
    if (low >= high) return;
    
    int lt, gt;
    threeWayPartition(arr, low, high, <, >);
    
    quickSort3Way(arr, low, lt - 1);
    quickSort3Way(arr, gt + 1, high);
}

int main() {
    int arr[] = {4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4};
    int n = 11;
    quickSort3Way(arr, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    // Output: 1 4 4 4 4 4 4 4 9 9 9
    return 0;
}
06

Algorithm Comparison

Choosing the right algorithm depends on your specific situation. Here's a comprehensive comparison to help you make the right choice for your use case.

Searching Algorithms

Algorithm Time Complexity Space Requires Sorted? Best Use Case
Linear Search O(n) O(1) No Small arrays, unsorted data, single search
Binary Search O(log n) O(1) Yes Large sorted arrays, multiple searches

Sorting Algorithms

Algorithm Best Average Worst Space Stable
Bubble Sort O(n) O(n²) O(n²) O(1)
Selection Sort O(n²) O(n²) O(n²) O(1)
Insertion Sort O(n) O(n²) O(n²) O(1)
Quick Sort O(n log n) O(n log n) O(n²) O(log n)

Which Algorithm Should You Use?

For Searching

Use Linear Search when:

  • Array is small (< 100 elements)
  • Array is unsorted
  • You only search once

Use Binary Search when:

  • Array is large
  • Array is sorted (or can be sorted)
  • You search multiple times

For Sorting

Use Insertion Sort when:

  • Array is small (< 50 elements)
  • Array is nearly sorted
  • Stability is needed

Use Quick Sort when:

  • Array is large
  • Average case performance matters
  • Memory is limited

Interactive Algorithm Visualizer

Algorithm Visualizer

Watch searching and sorting algorithms in action!

Comparisons
0
Swaps
0
Status
Ready

Key Takeaways

Searching Essentials

  • Linear Search: O(n), works on any array, simple but slow for large data
  • Binary Search: O(log n), requires sorted array, incredibly efficient
  • For 1 million elements: Linear = 1M comparisons, Binary = ~20 comparisons
  • Sort first + binary search is worth it if you search multiple times

Sorting Essentials

  • Bubble Sort: Simple, O(n²), good for learning
  • Selection Sort: O(n²), minimizes swaps
  • Insertion Sort: O(n²) but O(n) for nearly sorted, great for small data
  • Quick Sort: O(n log n) average, best general-purpose sort

Big O Quick Reference

  • O(1): Constant - array access
  • O(log n): Logarithmic - binary search
  • O(n): Linear - linear search, one loop
  • O(n log n): Linearithmic - quick sort, merge sort
  • O(n²): Quadratic - nested loops, bubble sort

Pro Tips

  • Use insertion sort for arrays < 50 elements (even inside quick sort!)
  • Binary search has a common bug: use mid = low + (high-low)/2 to prevent overflow
  • Quick sort's worst case is rare with good pivot selection
  • In C, qsort() from stdlib.h is production-ready

Knowledge Check

Test your understanding of searching and sorting algorithms with these questions!

1 What is the time complexity of binary search?
2 Which sorting algorithm is generally the fastest for large datasets?
3 What is required for binary search to work correctly?
4 In bubble sort, after the first complete pass through the array, where is the largest element?
5 What is the worst-case time complexity of quick sort?
6 Which sorting algorithm is best for a nearly-sorted array?
Answer all questions to check your score