Welcome to Lesson 20!

Learning Objectives
By the end of this class, you should know...
  • Sorting Algorithm Classification
  • Bubble sort
  • Merge sort
  • Divide and Conquer



1. Sorting Algorithms
  • Used to put list of values in order
    • numerical, lexographic or other (how to compare two objects from the same class?)
  • Typical run-times of sorting algorithms:
    • Worst class of sorting algorithms: average O(n2) or above
    • Best class of sorting algorithms: average O(n log n)
    • Average of O(n) is not possible for comparison-based algorithms
      • Why?
    • Non-comparison based sorting algorithms can achieve better average results:
      • Radix sort: O(nk)
      • Bucket sort: O(n + k)
  • Recursive and non-recursive
  • Comparison-based vs parallel
    • Divide and conquer
  • In-place algorithms (sorted without needing extra memory)
    • Example: heap sort
  • My experience with interviews and what I have heard:
    •  #1 to know is merge sort
    •  Should have merge sort and quick sort memorized when you interview
    • Will ask you to have merge sort (wrapper not helper) memorized for the final


 Algorithm Big-O Comparison-Based Parallel Divide and Conquer
 In-Place
Bubble Sort
n2
Yes
No
No
Yes
 Heap Sort
nlog(n)
Yes
No
No
Yes
 Merge Sort
nlog(n)
Yes
No
Yes
No
 Bucket Sort
n+k
 No YesYes
No




2. BubbleSort Algorithm

  • Compare all pairs of values
  • Swap any pair where the first value is larger than the second value


Bubble Sort Animation


Bubble Sort

Bubble Sort Pseudocode:

BubbleSort(A[], size)
    for i = 0 to size - 1
        for j = 0 to size - 1
            if A[j] > A[j+1]
               A[j] <---> A[j+1] //swap

Advantage:
  • Easy to write and remember
Disadvantage:
  • Very sloooowww
  • Run-times:
    • Best-case: O(n)
    • Average-case: O(n2)
    • Worst-case: O(n2)
  • Never used in real life applications

3. Merge Sort
  • Recursive "Divide and Conquer" Algorithm
  • Divide and Conquer is a common approach to problems in Computer Science
    • Divide (the problem into a small number of pieces)
    • Conquer (solve each piece, by applying divide-and-conquer recursively to it)
    • Combine (the pieces together into a global solution)
  • Merge Sort is one of the best known Divide and Conquer Algorithms
    • Divide: Split A down the middle into two subsequences, each of size roughly n/2. 
    • Conquer: Sort each subsequence (by calling MergeSort recursively on each). 
    • Combine: Merge the two sorted subsequences into a single sorted list.
  • The dividing process ends when we have split the subsequences down to a single item. 
    • A sequence of length one is trivially sorted.
  • We can visualize Merge Sort's Divide and Conquer approach through the image below:

Merge Sort Performed on an Array 



Merge Sort Animation

Merge-sort-example-300px.gif

Merge Sort Pseudocode

MergeSort(A[], low, high)
    if (low < high)
        middle = (low + high) / 2 //midpoint formula
        MergeSort(A[], low, middle)
        MergeSort(A[], middle+1, high)
        Merge(A[], low, middle, high)

Merge(A[], low, mid, high)
    l = low
    m = mid + 1
    index = low //current index of result array
    result[low...high] //will store sorted values
    while (l <= mid AND m <= high) //while both subarrays are non empty
        if(A[l] < A[m]) //A[l] is smaller value so copy into result
            result[index] = A[l]
            index++
            l++
        else
            result[index] = A[m]
            index++
            m++
    while (l <= mid) //right subarray is empty so copy over all of left side values
        result[index] = A[l]
        index++
        l++
    while (m <= high) //left subarray is empty so copy over all right side values
        result[index] = A[m]
        index++
        m++
    Copy(A, result) //copy contents of result into original Array A

  • Note: The use of the temporary array result here is a necessary evil, as merge sort requires the use of a temporary array at some point in the algorithm. 
    • It is one of the shortcomings of MergeSort, compared to some of the other efficient sorting algorithms.
    • In other words, it is not an "In Place Algorithm"
      • In contrast to Heap Sort, where the array is sorted without requiring extra memory
  • This version of mergeSort minimizes the creation of temporary arrays.
Order Of Steps
Order in which steps occur in merge sort


Time Complexity of Merge Sort
  • O(n logn) - in Best, Worst, and Average Cases

Merge Sort with Cards



Wrap Up
  • Answer the review questions for this lesson on Canvas

~ Have a Great Day! ~