Hashing and Hash Tables; Sorting Algorithms

Hashing and Hash Tables

What is Hashing?

Hashing is a technique that maps data to a fixed-size array (hash table) using a hash function.

Hash Function: h(key) = index where key is stored

Goal: O(1) average time for insert, delete, search.

Hash Table Structure

#define TABLE_SIZE 100

int hash(int key) {
    return key % TABLE_SIZE;
}

Collision Handling

Collision: Two keys hash to the same index.

Chaining Implementation

typedef struct entry {
    int key;
    int value;
    struct entry *next;
} entry_t;

entry_t *table[TABLE_SIZE] = {NULL};

void insert(int key, int value) {
    int idx = hash(key);
    entry_t *e =
malloc(sizeof(entry_t));
    e->key = key;
    e->value = value;
    e->next = table[idx];
table[idx] = e;
}

int search(int key) {
    int idx = hash(key);
    entry_t *curr = table[idx];
    while (curr != NULL) {
        if (curr->key == key) return curr->value;
        curr = curr->next;
    }
    return -1;  // not found
}

Hash Function Design

A good hash function:

• Distributes keys uniformly across the table
• Fast to compute

Minimizes collisions

Common techniques:

Load Factor: α = n/m (n = entries, m = table size)
Keep α < 0.7 for good performance.

Sorting Algorithms

Introduction to Sorting

Sorting is the process of arranging elements in a specific order (ascending or descending).

Stability: A sorting algorithm is stable if equal elements maintain their relative order.

In-place: Algorithm sorts using O(1) extra space.

21.1 Selection Sort

Algorithm:

• Select element (start from first) and compare with remaining elements in forward direction
• Repeat the above process N-1 times
• After completion of first pass, the lowest element will be placed in order
• Need to execute n-1 passes

Passes needed: n-1
Comparisons:

• 1st pass: n-1 comparisons
• 2nd pass: n-2 comparisons
• ...
• Total: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)

Example:

Initial: 56  4  43  33  2
Pass 1 (find min=2, swap with index 0):
         2  4  43  33  56
Pass 2 (find min=4 in [1..4], already in place):
         2  4  43  33  56
Pass 3 (find min=33 in [2..4], swap with 43):
         2  4  33  43  56
Pass 4:  2  4  33  43  56  (already sorted)
Sorted!  2  4  33  43  56

C Implementation:

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
}

Complexity: Time O(n²), Space O(1), Not stable, In-place.

21.2 Bubble Sort

Algorithm: Compare adjacent elements; swap if out of order; repeat n-1 passes.

Key insight: After each pass, the largest unsorted element "bubbles" to its correct position.

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;  // Already sorted; early exit
    }
}

Complexity: Time O(n²) worst/average; O(n) best (sorted); Space O(1); Stable; In-place.

21.3 Insertion Sort

Algorithm: Build sorted portion one element at a time; insert each element into correct position.

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];  // shift right
            j--;
        }
        arr[j + 1] = key;  // insert
    }
}

Example:

Initial: [56, 4, 43, 33, 2]

i=1: key=4;   [4, 56, 43, 33, 2]
i=2: key=43;  [4, 43, 56, 33, 2]
i=3: key=33;  [4, 33, 43, 56, 2]
i=4: key=2;   [2, 4, 33, 43, 56]

Complexity: Time O(n²) worst; O(n) best; Space O(1); Stable; In-place; Good for nearly sorted data.

21.4 Merge Sort

Divide and Conquer: Divide array into halves, recursively sort, merge.

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    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++];
}

void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

Complexity: Time O(n log n) all cases; Space O(n); Stable; Not in-place (extra array).

21.5 Quick Sort

Divide and Conquer: Choose a pivot; partition array (smaller left, larger right); recursively sort subarrays.

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++;
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
        }
    }
    int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp;
    return i + 1;
}

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

Complexity: Time O(n log n) avg; O(n²) worst (sorted input); Space O(log n) avg; Not stable; In-place.

Sorting Algorithm Comparison