Array Searching and Sorting in C

In C programming, searching and sorting arrays are essential operations used to manage and process data efficiently. Whether you’re looking for a specific value in an array or sorting elements in ascending or descending order, understanding how to implement these operations is fundamental to working with arrays.

1. Array Searching

Searching refers to the process of finding a specific element in an array. In C, there are various algorithms for searching elements, with the two most common being Linear Search and Binary Search.

1.1. Linear Search

Linear search is the simplest searching algorithm. It checks each element of the array sequentially until the target element is found or all elements are checked. The time complexity of linear search is O(n), where n is the number of elements in the array.

Example: Linear Search

#include <stdio.h>
 
// Function to perform linear search
int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i;  // Return index if element is found
        }
    }
    return -1;  // Return -1 if element is not found
}
 
int main() {
    int numbers[] = {10, 20, 30, 40, 50};
    int target = 30;
    int size = sizeof(numbers) / sizeof(numbers[0]);
 
    int result = linearSearch(numbers, size, target);
    
    if (result != -1) {
        printf("Element %d found at index %d\n", target, result);
    } else {
        printf("Element %d not found\n", target);
    }
 
    return 0;
}

Explanation:

The function linearSearch() takes an array, its size, and a target value to search for.
It iterates through the array and compares each element with the target. If a match is found, the function returns the index of the element.
If the element is not found, it returns -1.

Example Output:

Element 30 found at index 2

1.2. Binary Search

Binary search is a more efficient searching algorithm, but it can only be used on sorted arrays. It works by repeatedly dividing the search interval in half. If the target value is less than the value in the middle, the search continues in the lower half; otherwise, it continues in the upper half. The time complexity of binary search is O(log n).

Example: Binary Search

#include <stdio.h>
 
// Function to perform binary search
int binarySearch(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;
 
    while (low <= high) {
        int mid = (low + high) / 2;
        
        if (arr[mid] == target) {
            return mid;  // Return index if element is found
        } else if (arr[mid] < target) {
            low = mid + 1;  // Search in the right half
        } else {
            high = mid - 1;  // Search in the left half
        }
    }
    return -1;  // Return -1 if element is not found
}
 
int main() {
    int numbers[] = {10, 20, 30, 40, 50};
    int target = 40;
    int size = sizeof(numbers) / sizeof(numbers[0]);
 
    int result = binarySearch(numbers, size, target);
    
    if (result != -1) {
        printf("Element %d found at index %d\n", target, result);
    } else {
        printf("Element %d not found\n", target);
    }
 
    return 0;
}

Explanation:

The function binarySearch() takes an array, its size, and a target value to search for.
The array must be sorted for binary search to work properly.
The function performs a binary search by repeatedly dividing the search interval and adjusting the bounds (low and high) based on comparisons with the middle element.

Example Output:

Element 40 found at index 3

2. Array Sorting

Sorting is the process of arranging the elements of an array in a particular order (either ascending or descending). The most common sorting algorithms are Bubble Sort, Selection Sort, and Insertion Sort.

2.1. Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the array, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the array is sorted. The time complexity of bubble sort is O(n^2) in the worst case.

Example: Bubble Sort

#include <stdio.h>
 
// Function to perform bubble sort
void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap if the element is greater than the next one
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
 
int main() {
    int numbers[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(numbers) / sizeof(numbers[0]);
 
    bubbleSort(numbers, size);  // Sort the array
 
    printf("Sorted array: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", numbers[i]);
    }
    
    return 0;
}

Explanation:

The function bubbleSort() sorts the array using the bubble sort algorithm.
The algorithm repeatedly compares adjacent elements and swaps them if they are in the wrong order. The process continues until the entire array is sorted.

Example Output:

Sorted array: 11 12 22 25 34 64 90

2.2. Selection Sort

Selection sort is another simple sorting algorithm. It works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the array and swapping it with the first unsorted element. The time complexity of selection sort is O(n^2).

Example: Selection Sort

#include <stdio.h>
 
// Function to perform selection sort
void selectionSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;  // Find the index of the minimum element
            }
        }
        // Swap the found minimum element with the first unsorted element
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}
 
int main() {
    int numbers[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(numbers) / sizeof(numbers[0]);
 
    selectionSort(numbers, size);  // Sort the array
 
    printf("Sorted array: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", numbers[i]);
    }
    
    return 0;
}

Explanation:

The function selectionSort() sorts the array using the selection sort algorithm.
It selects the minimum element from the unsorted portion of the array and swaps it with the first unsorted element, then moves the boundary of the sorted portion.

Example Output:

Sorted array: 11 12 22 25 34 64 90

3. Conclusion

Searching and sorting are fundamental operations for processing arrays. Here’s a summary of what we covered:

Array Searching: We discussed Linear Search (simple, but slower for large arrays) and Binary Search (efficient, but requires a sorted array).
Array Sorting: We explored Bubble Sort (simple but inefficient for large arrays) and Selection Sort (another simple but inefficient sorting method). Both are good for small arrays but are generally not used for large datasets due to their O(n^2) complexity.

Efficient searching and sorting algorithms play a crucial role in many applications, and understanding them will help you manage and process data more effectively in your C programs.

Passing Arrays to Functions Multi-Dimensional Arrays