Insertion Sort in C #

What is Insertion Sort? #

• A simple sorting algorithm
• Works like sorting playing cards in your hand
• Builds the final sorted array one item at a time

Algorithm Idea #

1. Start from the second element
2. Compare with elements before it
3. Shift larger elements to the right
4. Insert the element into the correct position
5. Repeat until array is sorted

C Implementation #

void insertionSort(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];
            j--;
        }
        arr[j + 1] = key;
    }
}

Pythontutor

Inserstion Sort vs Selection Sort #

Suppose the input was sorted, Selection Sort will still do n(n+1)/2 iterations but insertion sort only does n. (Prove this)

For a reverse sorted array, both will do n(n+1)/2 iterations.

What is Binary Search? #

• Efficient algorithm for finding an element in a sorted array
• Works by repeatedly dividing the search interval in half
• Compare target with the middle element:
  • If equal → found
  • If smaller → search left half
  • If larger → search right half

Algorithm Idea #

1. Start with low = 0, high = n-1
2. Compute mid = (low + high) / 2
3. Compare arr[mid] with key
   • If arr[mid] == key → return mid
   • If arr[mid] > key → search left half
   • Else → search right half
4. Repeat until low > high

Recursive Implementation (C) #

int binarySearchRec(int arr[], int low, int high, int key) {
    if (low > high) return -1;

    int mid = (low + high) / 2;

    if (arr[mid] == key)
        return mid;
    else if (arr[mid] > key)
        return binarySearchRec(arr, low, mid - 1, key);
    else
        return binarySearchRec(arr, mid + 1, high, key);
}

Pythontutor #

Runtime of Binary Search #

Suppose the array is already sorted and we need to check for a single key, runtime of BinarySearch is only $C \log n$ (were C is some constant). (Prove this).

Runtime of linear search is $C n$.

When to use #

If you include the runtime for sorting also, the total runtime for checking if $m$ elements are part of the array is: $n(n+1)/2 + m C \log n$.

For linear search it will be $m n$.

So when $m » n$ (much larger), sorting + binary search wins.

Example Dry Run #

Array: {1, 3, 5, 7, 9, 11, 13} Search for 7

low=0, high=6 → mid=3 → arr[3]=7 → found at index 3

Search for 6

low=0, high=6 → mid=3 → arr[3]=7 (too big)

low=0, high=2 → mid=1 → arr[1]=3 (too small)

low=2, high=2 → mid=2 → arr[2]=5 (too small)

low=3, high=2 → stop → not found

What is the Fibonacci Sequence? #

• Each number is the sum of the two preceding numbers
• Defined as:
  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2), for n ≥ 2

Example sequence: 0, 1, 1, 2, 3, 5, 8, 13, …

Recursive Definition in C #

int fibonacci(int n) {
    if (n == 0) return 0;  // base case
    if (n == 1) return 1;  // base case
    return fibonacci(n-1) + fibonacci(n-2); // recursion
}

You can call the same funtion mutliple times in the same line!

Example Trace: F(5) #

fibonacci(5)
= fibonacci(4) + fibonacci(3)
= (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
= ...
= 5

Tree of calls (partial): #

            F(5)
          /     \
       F(4)     F(3)
      /   \     /   \
   F(3)  F(2) F(2)  F(1)
   ...

Note that same F(3) value that was computed initially was forgotten and we had to recompute it again.