PROBLEM SOLVING - SEARCH & SORT IN C

Search & Sort Basics in C

Fundamentals

Searching and sorting are fundamental operations in computer science:

Searching - Finding an element in a data structure
Sorting - Arranging elements in a particular order
Time Complexity - Measures how runtime grows with input size
Space Complexity - Measures memory usage relative to input size

Applications

Search and sort algorithms are used in:

Database operations (indexing, querying)
Data analysis and visualization
Operating system processes
Artificial intelligence and machine learning
Game development
Networking and routing

SEARCH & SORT TECHNIQUES

#	Algorithm	Type	Description	Complexity	Use Cases
1	Linear Search	Search	Check each element sequentially until found	O(n)	Unsorted arrays Small datasets Simple implementations
2	Binary Search	Search	Divide and conquer approach on sorted data	O(log n)	Sorted arrays Large datasets Database indexing
3	Bubble Sort	Sort	Repeatedly swaps adjacent elements if in wrong order	O(n²)	Educational purposes Small datasets Nearly sorted data
4	Selection Sort	Sort	Finds minimum element and swaps with first position	O(n²)	Small datasets Memory constrained Simple implementation
5	Insertion Sort	Sort	Builds final sorted array one item at a time	O(n²)	Small datasets Nearly sorted data Online sorting
6	Quick Sort	Sort	Divide and conquer with pivot element	O(n log n) O(n²) worst	Large datasets General purpose In-memory sorting
7	Merge Sort	Sort	Divide and conquer with stable sorting	O(n log n)	Large datasets External sorting Stable sort needed
8	Heap Sort	Sort	Uses binary heap data structure	O(n log n)	Large datasets In-place sorting Priority queues

Common Implementations

Binary Search

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (arr[m] == x) return m;
        if (arr[m] < x) l = m + 1;
        else r = m - 1;
    }
    return -1;
}

Time Complexity: O(log n)

Quick Sort

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);
    }
}

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

Time Complexity: O(n log n)

Merge Sort

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int L[n1], R[n2];
    
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

Time Complexity: O(n log n)

Advanced Search & Sort Techniques

#	Technique	Description	Use Case
1	Interpolation Search	Improved binary search for uniformly distributed data	Phone directories, large datasets
2	Exponential Search	Combines linear and binary search for unbounded lists	Infinite/unknown size arrays
3	Tim Sort	Hybrid of merge sort and insertion sort	Python's built-in sort, real-world data
4	Counting Sort	Non-comparison based sort using key counts	Small integer ranges
5	Radix Sort	Digit by digit sort using counting sort	Large numbers, strings
6	Bucket Sort	Distributes elements into buckets then sorts individually	Uniformly distributed data

Related Resources

Basic Programs

Interview Questions

MCQs

Optimization Tricks