Arrays

Array Algorithms

Master essential array algorithms - linear search, binary search, bubble sort, selection sort, insertion sort, and quicksort. Learn time complexity, implementation, and when to use each algorithm.

Searching Algorithms

Searching finds whether an element exists in an array and returns its position. The two fundamental approaches are linear search (works on any array) and binary search (requires sorted array but much faster). Understanding their trade-offs is essential for choosing the right approach.

Linear Search

Linear search checks each element sequentially until finding the target or reaching the end. It's simple, works on unsorted arrays, and has O(n) time complexity. Best for small arrays or when the array is unsorted.

C
/* Linear search - returns index or -1 if not found */
int linear_search(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i;  // Found at index i
        }
    }
    return -1;  // Not found
}

/* Usage */
int main(void) {
    int numbers[] = {5, 2, 8, 1, 9, 3, 7};
    int size = 7;
    
    int index = linear_search(numbers, size, 9);
    if (index != -1) {
        printf("Found at index %d\n", index);  // Found at index 4
    } else {
        printf("Not found\n");
    }
    
    return 0;
}

/* Time complexity: O(n) - worst case checks all elements
   Space complexity: O(1) - no extra space needed
   
   Best case: O(1) - element is first
   Average case: O(n/2) = O(n)
   Worst case: O(n) - element is last or not present
*/

Binary Search

Binary search repeatedly divides a sorted array in half, eliminating half the remaining elements each iteration. It has O(log n) time complexity - dramatically faster than linear search for large arrays. The array MUST be sorted first.

C
/* Binary search - requires sorted array */
int binary_search(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;  // Avoid overflow
        
        if (arr[mid] == target) {
            return mid;  // Found
        }
        
        if (arr[mid] < target) {
            left = mid + 1;  // Search right half
        } else {
            right = mid - 1;  // Search left half
        }
    }
    
    return -1;  // Not found
}

/* Recursive binary search */
int binary_search_recursive(int arr[], int left, int right, int target) {
    if (left &gt; right) {
        return -1;  // Base case: not found
    }
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) {
        return mid;  // Found
    }
    
    if (arr[mid] < target) {
        return binary_search_recursive(arr, mid + 1, right, target);
    } else {
        return binary_search_recursive(arr, left, mid - 1, target);
    }
}

/* Usage */
int main(void) {
    int sorted[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int size = 10;
    
    int index = binary_search(sorted, size, 13);
    printf("Found at index: %d\n", index);  // 6
    
    return 0;
}

/* Time complexity: O(log n) - halves search space each iteration
   Space complexity: O(1) iterative, O(log n) recursive (call stack)
   
   Example: Array of 1,000,000 elements
   Linear search: up to 1,000,000 comparisons
   Binary search: max 20 comparisons (logâ‚‚(1,000,000) â‰ˆ 20)
*/

Sorting Algorithms

Sorting arranges array elements in order (ascending or descending). Efficient sorting enables binary search, makes data easier to analyze, and solves many problems. Different sorting algorithms have different trade-offs between time complexity, space complexity, and stability.

Bubble Sort

Bubble sort repeatedly steps through the array, comparing adjacent elements and swapping them if they're in wrong order. Larger elements "bubble" to the end. Simple to understand but inefficient - O(nÂ²) time complexity makes it impractical for large arrays.

C
/* Bubble sort - O(nÂ²) */
void bubble_sort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        /* Last i elements are already sorted */
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] &gt; arr[j + 1]) {
                /* Swap adjacent elements */
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

/* Optimized bubble sort - stops early if no swaps */
void bubble_sort_optimized(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int swapped = 0;
        
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] &gt; arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        
        /* If no swaps, array is sorted */
        if (!swapped) {
            break;
        }
    }
}

/* Time complexity: O(nÂ²) worst and average case
   Best case: O(n) with optimization (already sorted)
   Space complexity: O(1) - sorts in place
   Stable: Yes - preserves relative order of equal elements
*/

Selection Sort

Selection sort finds the minimum element and swaps it to the beginning, then repeats for the remaining unsorted portion. Makes fewer swaps than bubble sort but still O(nÂ²). Good when swaps are expensive.

C
/* Selection sort - O(nÂ²) */
void selection_sort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        /* Find minimum in unsorted portion */
        int min_idx = i;
        
        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        
        /* Swap minimum to position i */
        if (min_idx != i) {
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

/* Time complexity: O(nÂ²) all cases - always does same comparisons
   Space complexity: O(1)
   Stable: No - can change relative order of equal elements
   
   Advantages:
   - Simple implementation
   - Minimum number of swaps: O(n)
   - Works well when swaps are expensive
*/

Insertion Sort

Insertion sort builds the sorted array one element at a time by inserting each element into its correct position. Efficient for small arrays and nearly sorted data. O(nÂ²) worst case but O(n) for sorted data.

C
/* Insertion sort - O(nÂ²) worst case, O(n) best case */
void insertion_sort(int arr[], int size) {
    for (int i = 1; i < size; i++) {
        int key = arr[i];
        int j = i - 1;
        
        /* Shift elements greater than key to the right */
        while (j >= 0 && arr[j] &gt; key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        /* Insert key at correct position */
        arr[j + 1] = key;
    }
}

/* Time complexity:
   Best case: O(n) - already sorted
   Average case: O(nÂ²)
   Worst case: O(nÂ²) - reverse sorted
   
   Space complexity: O(1)
   Stable: Yes
   
   When to use:
   - Small arrays (< 50 elements)
   - Nearly sorted data
   - Online algorithm (can sort as data arrives)
   - Part of more complex algorithms (e.g., Shell sort, Timsort)
*/

Quicksort

Quicksort uses divide-and-conquer: pick a pivot, partition array so elements less than pivot are left and greater are right, then recursively sort partitions. Average O(n log n) makes it one of the fastest general-purpose sorts, though worst case is O(nÂ²).

C
/* Quicksort - O(n log n) average, O(nÂ²) worst */

/* Partition function */
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
    
    for (int j = low; j < high; j++) {
        /* If current element <= pivot */
        if (arr[j] <= pivot) {
            i++;
            /* Swap arr[i] and arr[j] */
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    /* Swap pivot to correct position */
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    
    return i + 1;  // Return pivot index
}

/* Quicksort recursive function */
void quicksort(int arr[], int low, int high) {
    if (low < high) {
        /* Partition array */
        int pivot_idx = partition(arr, low, high);
        
        /* Recursively sort sub-arrays */
        quicksort(arr, low, pivot_idx - 1);   // Before pivot
        quicksort(arr, pivot_idx + 1, high);  // After pivot
    }
}

/* Wrapper function */
void quick_sort(int arr[], int size) {
    quicksort(arr, 0, size - 1);
}

/* Time complexity:
   Best case: O(n log n) - balanced partitions
   Average case: O(n log n)
   Worst case: O(nÂ²) - already sorted with bad pivot choice
   
   Space complexity: O(log n) - call stack
   Stable: No (standard implementation)
   
   Advantages:
   - Very fast in practice
   - In-place (no extra array needed)
   - Cache-friendly
   
   Improvements:
   - Random pivot selection avoids worst case
   - Median-of-three pivot selection
   - Switch to insertion sort for small sub-arrays
*/

Algorithm Comparison

Choosing the right algorithm depends on your data characteristics, size, and requirements. Here's a practical guide to help you decide which algorithm to use in different situations.

C
/* Performance comparison on different data */

#include <time.h>

void benchmark_sorts(void) {
    int sizes[] = {100, 1000, 10000};
    
    for (int s = 0; s < 3; s++) {
        int size = sizes[s];
        int *arr = malloc(size * sizeof(int));
        
        /* Fill with random data */
        for (int i = 0; i < size; i++) {
            arr[i] = rand() % 10000;
        }
        
        clock_t start, end;
        
        /* Bubble sort */
        start = clock();
        bubble_sort(arr, size);
        end = clock();
        printf("Bubble sort (%d): %.3f ms\n", 
               size, (double)(end - start) / CLOCKS_PER_SEC * 1000);
        
        /* Reset and try quicksort */
        for (int i = 0; i < size; i++) {
            arr[i] = rand() % 10000;
        }
        
        start = clock();
        quick_sort(arr, size);
        end = clock();
        printf("Quick sort (%d): %.3f ms\n\n", 
               size, (double)(end - start) / CLOCKS_PER_SEC * 1000);
        
        free(arr);
    }
}

/* When to use each algorithm:

   LINEAR SEARCH:
   - Unsorted array
   - Small array (< 100 elements)
   - Search once or rarely
   
   BINARY SEARCH:
   - Sorted array
   - Large array
   - Multiple searches (amortize sort cost)
   
   BUBBLE SORT:
   - Educational purposes only
   - Already mostly sorted
   - Very small arrays (< 10)
   
   SELECTION SORT:
   - Swapping is expensive
   - Small arrays
   - Memory writes are costly
   
   INSERTION SORT:
   - Small arrays (< 50 elements)
   - Nearly sorted data
   - Online sorting (data arrives over time)
   - Part of hybrid algorithms
   
   QUICKSORT:
   - General-purpose sorting
   - Large arrays
   - Average case performance critical
   - In-place sorting needed
   
   MERGE SORT: (not shown, but worth mentioning)
   - Guaranteed O(n log n)
   - Stable sort needed
   - External sorting (data doesn't fit in memory)
   - Linked lists
*/

Practical Array Utilities

Beyond searching and sorting, many practical array operations are useful in real programs. These utilities demonstrate common patterns you'll use frequently.

C
/* Remove duplicates from sorted array */
int remove_duplicates(int arr[], int size) {
    if (size == 0) return 0;
    
    int write_idx = 1;
    for (int read_idx = 1; read_idx < size; read_idx++) {
        if (arr[read_idx] != arr[read_idx - 1]) {
            arr[write_idx++] = arr[read_idx];
        }
    }
    return write_idx;  // New size
}

/* Rotate array left by k positions */
void rotate_left(int arr[], int size, int k) {
    k = k % size;  // Handle k &gt; size
    
    /* Reverse first k elements */
    for (int i = 0; i < k / 2; i++) {
        int temp = arr[i];
        arr[i] = arr[k - 1 - i];
        arr[k - 1 - i] = temp;
    }
    
    /* Reverse remaining elements */
    for (int i = k; i < (k + size) / 2; i++) {
        int temp = arr[i];
        arr[i] = arr[size - 1 - (i - k)];
        arr[size - 1 - (i - k)] = temp;
    }
    
    /* Reverse entire array */
    for (int i = 0; i < size / 2; i++) {
        int temp = arr[i];
        arr[i] = arr[size - 1 - i];
        arr[size - 1 - i] = temp;
    }
}

/* Find two numbers that sum to target */
int find_pair_sum(int arr[], int size, int target, int *idx1, int *idx2) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (arr[i] + arr[j] == target) {
                *idx1 = i;
                *idx2 = j;
                return 1;  // Found
            }
        }
    }
    return 0;  // Not found
}

/* Merge two sorted arrays */
void merge_sorted(int arr1[], int size1, int arr2[], int size2, int result[]) {
    int i = 0, j = 0, k = 0;
    
    while (i < size1 && j < size2) {
        if (arr1[i] <= arr2[j]) {
            result[k++] = arr1[i++];
        } else {
            result[k++] = arr2[j++];
        }
    }
    
    /* Copy remaining elements */
    while (i < size1) {
        result[k++] = arr1[i++];
    }
    
    while (j < size2) {
        result[k++] = arr2[j++];
    }
}

Summary & What's Next

Key Takeaways:

âœ… Linear search: O(n), works on unsorted arrays
âœ… Binary search: O(log n), requires sorted array
âœ… Bubble sort: O(nÂ²), simple but slow
âœ… Selection sort: O(nÂ²), minimum swaps
âœ… Insertion sort: O(nÂ²) worst, O(n) best, good for small/nearly sorted
âœ… Quicksort: O(n log n) average, fastest general-purpose
âœ… Choose algorithm based on data size and characteristics
âœ… Understanding complexity helps predict performance

What's Next?

Let's learn about array and pointer relationship!

Next: Arrays & Pointers â†’