sorting (2)

Course Overview

  • Course Title: CS170: Discrete Methods in Computer Science

  • Semester: Spring 2025

  • Instructor: Shaddin Dughmi

  • Content Source: Adapted from slides by Aaron Cote

Objective of Lecture

  • Main Topic: Sorting an array

  • Goals:

    • Exercise concepts of proofs and runtime.

    • Prepare students for upcoming course (270).

Definition of Sorting

  • Input: An array of n numbers, in arbitrary order (e.g., a = [a0, ..., an-1])

  • Output: Array with the same n numbers ordered from smallest to largest.

    • Inclusion Rule: Any number occurring multiple times in input should do so in output as well.

Computational Model

  • Basic Operations (counting runtime):

    • Comparison of two numbers.

    • Reading/Writing from the array at a given index.

Sorting Algorithms Overview

  • Outline of Algorithms:

    1. Bubble Sort

    2. Selection Sort

    3. Insertion Sort

    4. Merge Sort

Bubble Sort

Overview and Process

  • High-Level Description:

    • Compare adjacent elements (a0 with a1, a1 with a2, ..., an-2 with an-1).

    • Swap elements out of order.

  • Completion: Repeat until the array is sorted.

  • After each full pass, the largest element moves to the end of the array.

Pseudocode

  • Structure:

    For i from n - 1 to 1:
    For j from 0 to i - 1:
        If a[j] > a[j + 1] then swap(a,j, j + 1)

Runtime Analysis

  • Outer Loop: n - 1 iterations

  • Inner Loop: (n - 1) + (n - 2) + ... + 1 = O(n^2)

  • Total Complexity: O(n^2)

Correctness

  • Inductive Proof:

    • The loop invariant states that at the start of each k-th iteration, the largest k - 1 elements are in the last k - 1 positions, sorted.

    • Prove by base case and induction the correctness of the sort.

Selection Sort

Overview and Process

  • High-Level Description:

    • Scan to find the smallest element, swap it to the first position.

    • Continue to find the next smallest for each subsequent position until sorted.

Pseudocode

  • Structure:

    For i from 0 to n - 1:
    small = i;
    For j from i + 1 to n - 1:
        If a[j] < a[small] then small = j;
    swap(a,i, small)

Runtime Analysis

  • Outer Loop: n iterations

  • Inner Loop: (n - 1) + (n - 2) + ... + 1 = O(n^2)

  • Total Complexity: O(n^2)

Correctness

  • Inductive Proof:

    • Loop invariant states that at the start of the iteration with i = k, the smallest k elements are sorted in the first k positions.

Insertion Sort

Overview and Process

  • High-Level Description:

    • Sort the first element, then insert the second element to maintain order, then the third, and so on until sorted.

Pseudocode

  • Structure:

    For i from 1 to n - 1:
    j = i;
    While (j > 0 and a[j] < a[j - 1]):
        swap(a,j,j - 1);
        j = j - 1;

Runtime Analysis

  • Outer Loop: n - 1 iterations

  • Inner Loop: 1 + 2 + ... + (n - 1) = O(n^2)

  • Total Complexity: O(n^2)

Correctness

  • Inductive Proof:

    • Loop invariant states that before each outer iteration begins, the first k elements are in sorted order.

Merge Sort

Overview and Process

  • High-Level Description:

    • If the array has 1 element, it is sorted.

    • Recursively sort the left and right halves, then merge them.

Pseudocode

  • Recursive Structure:

    Mergesort(a, L, R):
    If L = R return.
    let m be the middle between L and R;
    Mergesort(a, L, m);
    Mergesort(a, m + 1, R);
    Merge(a, L, m, R);

Merge Function Pseudocode

  • Merge Process:

    • Create temporary array, compare elements, merge back into the original array.

Correctness and Runtime Analysis

  • Inductive Proof for Merge:

    • Correctly sorts when both halves are sorted.

  • Runtime: O(n log n)

    • By structure and recursive nature of the algorithm.