Introduction to Algorithms - Lecture 3: Sorting

This post is a derivative from Introduction to Algorithms of MIT OpenCourseWare, used under CC BY-NC-SA 4.0.

You can watch this lecture on Youtube and see PDF.

Review

• Interface

  Collection of operations (e.g., sequence & set)

• Data structure Way to store data that supports a set of operations

Set Interface

A set interface is an object that you can keep adding things to it.

Sorting Vocabulary

• Input: Array of n numbers(keys)
• Output: Sorted array
• Destructive: Overwrite the input array. Rather than reserving some new memory for sorted array B and then putting a sorted version of A into B, a destructive algorithm is one that just overwrites A with a sorted version of A.
• In place: Uses O(1) extra space. It doesn’t use extra memory in the process of sorting. in place ⊆ destructive.

Permutaion Sort

If I have an input that’s a list of numbers, there exists a permutation of that list of numbers that is sorted because a sort is a permutation of your original list. List every possible permutation and then just double check which one is the right order.

• Example: [2, 3, 1] -> {[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], … }

def permitation_sort (A):
    '''Sort A'''
    for B in permutations (A):      # O(n!)
        if is_sorted (B):           # O(n)
            return B                # O(1)

• Correct by case analysis: try all possibilities (Brute Force)
• Running time: Ω(n! · n) which is exponential

Selection Sort

1. Find the biggest with index <= i
2. Swap
3. Sort 1, … , i - 1

def selection_sort (A, i = None):         # T(i)
    '''Sort A[:i + 1]'''
    if i is None: i = len (A) - 1         # O(1)
    if i > 0:                             # O(1)
        j = prefix_max (A, i)             # S(i)
        A[i], A[j] = A[j], A[i]           # O(1)
        selection_sort (A, i - 1)         # T(i-1)

def prefix_max (A, i):                    # S(i)
    '''Return index of maximum in A[:i+ 1 ]'''
    if i > 0:                             # O(1)
        j = prefix_max (A, i - 1)         # S(i - 1)
        if A[i] < A[j]:                   # O(1)
            return j                      # O(1)
    return i                              # O(1)

Biggest element in 0, … , i

1. It is at index i
2. It has index < i

prefix_max analysis

S(1) = Θ(1), S(n)= S(n − 1) + Θ(1)

S(n) = Θ(n)

selection_sort analysis

T(1) = Θ(1), T(n)= T(n − 1) + Θ(n)

S(n) = Θ(n^2)

Insertion Sort

Merge Sort

• Recursively sort first half and second half (may assume power of two)
• Merge sorted halves into one sorted list (two finger algorithm)

def merge_sort (A, a = 0, b = None):                    # T(b - a = n)
    '''Sort A[a:b]'''
    if b is None: b = len (A)                           # O(1)
    if 1 < b - a:                                       # O(1)
        c = (a + b + a) // 2                            # O(1)
        merge_sort(A, a, c)                             # T(n / 2)
        merge_sort(A, c, b)                             # T(n / 2)
        L, R = A[a:c], A[c:b]                           # O(n)
        merge(L, R, A, len (L), len (R), a, b)          # S(n)

def merge(L, R, A, i, j, a, b):                         # S(b - a = n)
    '''Merge sorted L[:i] and R[:j] into A[a:b]'''
    if a < b:                                           # O(1)
        if (j <= 0) or (i > 0 and L[i - 1] > R[j - 1]): # O(1)
            A[b - 1] = L[i - 1]                         # O(1)
            i = i - 1                                   # O(1)
        else:
            A[b - 1] = R[j - 1]                         # O(1)
            j = j - 1                                   # O(1)
        merge(L, R, A, i, j, a, b - 1)                  # S(n-1)

merge analysis

S(0) = Θ(1), S(n)= S(n − 1) + Θ(1) -> S(n) = Θ(n)

merge_sort analysis

T(1) = Θ(1), T(n) = 2T(n/2) + Θ(n)

T(n) = Θ(n log n)