Unit 3: Searching, hashing and sorting

• Linear search: check each element one by one until the key is found or the list ends. Works on unsorted data. Best O(1), worst O(n).
• Binary search: works only on sorted data. Compare the key with the middle element; search the left or right half; repeat. Worst case O(log n).

cint binarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] == key) return mid;
        else if (key < a[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

• Records are sorted and divided into blocks; an index table holds the largest (or first) key of each block and its address. Search the index to find the block, then search sequentially within it.

• Like binary search on sorted data, but estimates the probe position from the key value — good for uniformly distributed keys.

Hashing stores and finds a record directly by computing its position from its key, giving average O(1) search. A hash function h(k) maps a key to an index in a hash table.

A collision happens when two keys hash to the same index.

• Open addressing (store in the table itself): linear probing (try next slots: h, h + 1, h + 2 …), quadratic probing (h + 1², h + 2² …) and double hashing (a second hash function decides the step).
• Chaining: each table slot points to a linked list of all keys that hash there.

cvoid bubble(int a[], int n) {
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; }
}
void insertion(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
}
void selection(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) if (a[j] < a[min]) min = j;
        int t = a[i]; a[i] = a[min]; a[min] = t;
    }
}

cint partition(int a[], int low, int high) {
    int pivot = a[high], i = low - 1;               /* Lomuto partition */
    for (int j = low; j < high; j++)
        if (a[j] <= pivot) { i++; int t = a[i]; a[i] = a[j]; a[j] = t; }
    int t = a[i + 1]; a[i + 1] = a[high]; a[high] = t;
    return i + 1;
}
void quickSort(int a[], int low, int high) {
    if (low < high) {
        int p = partition(a, low, high);
        quickSort(a, low, p - 1);
        quickSort(a, p + 1, high);
    }
}

• Average O(n log n); worst O(n²) with bad pivots; in-place; not stable. Median-of-three or random pivots avoid the worst case.

cvoid merge(int a[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m, L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = a[l + i];
    for (int j = 0; j < n2; j++) R[j] = a[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) a[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) a[k++] = L[i++];
    while (j < n2) a[k++] = R[j++];
}
void mergeSort(int a[], int l, int r) {
    if (l < r) { int m = (l + r) / 2; mergeSort(a, l, m); mergeSort(a, m + 1, r); merge(a, l, m, r); }
}

• O(n log n) in all cases, stable; the contiguous version needs O(n) extra space; the linked-list version splits the list with slow and fast pointers and merges by relinking nodes, needing no extra array — the preferred sort for linked lists.

• Insertion sort on elements a gap apart, with the gap reduced each pass (n/2, n/4, …, 1). Early passes move elements long distances, so the final insertion sort has little to do.

• Complexity depends on the gap sequence — about O(n^1.5) with Knuth's sequence; not stable.

A heap is a complete binary tree that satisfies the heap property:

• Max-heap: every parent ≥ its children; the largest value is at the root.
• Min-heap: every parent ≤ its children; the smallest value is at the root.

Heaps are stored in arrays and are used for priority queues and heap sort.

Heap sort runs in O(n log n) time in all cases.

• Tree sort: insert all elements into a binary search tree, then output an inorder traversal — O(n log n) on average, O(n²) if the tree becomes skewed (sorted input) unless a balanced tree is used.