COSC 2336 Data Structures

Objectives

• Practice writing functions

• Practice writing recursive functions.

• Learn about Analysis of algorithms and O(n log n) sorts

Description

In this assignment we will be implementing one of the most popular sorting algorithms used in libraries (like the C++ STL library, and the UNIX qsort function) to provide basic sorting abilities, the Quicksort algorithm. I would recommend that you at least read section 7.5 from our supplemental Shaffer textbook on Quicksort, if not sections 7.1-7.5 talking about three well known O(n log n) sorting algorithms, and the 3 O(n2) algorithms we discussed last week.

Quicksort, when properly implemented, is very attractive because it pro- vides a way to do a fast sort completely in-place (without having to allocate additional memory to do the sort, beyond a single value needed when swap- ping two values in the list being sorted). In the worst case, Quicksort is actually O(n2), no better than bubble sort. But this worse case only occurs when every pivot selected is the wort possible, and does not divide the list at all. This is very unlikely to happen, unless you know how the pivot is selected, and specifically design the input list to always choose the worst possible pivot. On average the cost of Quicksort is O(n log n), and it is usually very likely that average case performance will result when lists to be sorted are relatively random.Please find the source files along with the pdf question for this assignment