Reading 02

The assigned reading prior to Thursday, September 5th's class is an review 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 either of 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

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

  1. 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.

  2. 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. Finally, in your own words why is this an O(n log n) algorithm?

  3. 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. If it helps, think of the best and worse case pivots and how they affect the big-Oh of this sorting method.

  4. Define stability of a sort and give at least one example of when it would be useful/needed. Which of the above sorts, if any, are stable?

Submission

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