Reading 02

The assigned reading prior to Tuesday, January 29th's class is an overview of sorting with a focus on the divide and conquer methods Merge Sort and Quick Sort. Once again, we will ask you to think about complexity analysis, with a focus on the algorithm side (vs. the data structure side from Reading 01).

Please refer to:

  1. Data Structures and Other Objects Using C++:

    • Chapter 13, we'll cover most of this esp. bubble, insertion, merge and quick sort (13.1 and 13.2)

  2. Sorting Algorithms Animations

Alternative

If you do not have the primary textbook, you can use the following free alternative texts instead:

  1. Data Structures & Algorithm Analysis

    • 7.1 Sorting Terminology and Notation
    • 7.2 Three O(n^2) Sorting Algorithms
    • 7.4 Mergesort
    • 7.5 Quicksort
    • 7.8 An Empirical Comparison of Sorting Algorithms

  2. Open Data Structures

Questions (due 1/29, 10:30am)

Once you have completed the readings, answer the following questions:

  1. Trace the execution of selection sort for an array containing {9, 6, 0, 0, 7}, i.e., show the contents of the array after each iteration of the sorting algorithm.

  2. Trace the execution of insertion sort for an array containing {9, 6, 0, 0, 7}, i.e., show the contents of the array after each iteration of the sorting algorithm.

  3. merge sort is the prototypical example of a divide and conquer algorithm. In your own words, explain what happens during the divide portion of the algorithm and what happens during the conquer phase of merge sort.

  4. quick sort is another, but more complicated example, of a divide and conquer algorithm. Explain what happens during the partitioning phase of the algorithm and why the choice of a pivot is important for efficiency.

  5. For merge sort and quick sort, identify the worst case complexity of each algorithm in terms of Big O.

Submission

To submit your reading assignment, you must upload a text/PDF file onto Canvas prior to class