Unit 1: Introduction, searching and sorting

A data structure is a logical or mathematical model for organising data so it can be stored and processed efficiently.

Common operations: traversing (visiting each element), searching, inserting, deleting, sorting and merging.

• Problem analysis: understand inputs, outputs and constraints, choose a suitable data structure and algorithm, then estimate time and space requirements.

The complexity of an algorithm is the amount of time (time complexity) and memory (space complexity) it needs as a function of the input size n.

Common growth rates from fastest to slowest: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).

Time-space trade-off: we can often make a program faster by using more memory (for example a lookup table), or save memory at the cost of speed.

• Using more memory can reduce running time, and vice versa — e.g., a lookup table (hash table) answers queries in O(1) time using extra space; recomputing values saves space but takes more time; storing sorted copies speeds searching.

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

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