CMPE 180A Sorting Algorithms

Sorting algorithms

This assignment will give you practice coding several important sorting algorithms, and you will be able to compare their performances while sorting data of various sizes.

You will sort data elements in vectors with the selection sort, insertion short, Shellsort, and quicksort algorithms, and sort data elements in a linked list with the mergesort algorithm. There will be two versions of Shellsort, a "suboptimal" version that uses the halving technique for the diminishing increment, and an optimal version that uses a formula suggested by famous computer scientist Don Knuth. There will also be two versions of quicksort, a suboptimal version that uses a bad pivoting strategy, and an optimal version that uses a good pivoting strategy.

Class hierarchy

The UML (Unified Modeling Language) class diagram on the following page shows the class hierarchy. You are provided the complete code for class SelectionSort as an example, and you will code all versions of the other algorithms. You are also provided much of the support code.

The code you will write are in these classes:

• InsertionSort
• ShellSortSuboptimal
• ShellSortOptimal
• QuickSorter
• QuickSortSuboptimal
• QuickSortOptimal
• LinkedList
• MergeSort

These sorting algorithms are all described in Chapter 10 of the Malik textbook. You can also find many sorting tutorials on the Web. see image.

Abstract class Sorter

Class Sorter is the base class of all the sorting algorithms. Its member function sort() calls abstract member function run_sort_algorithm() which is defined in the sorting subclasses that you will write. It contains the sort timers.

Class Element

Your program will sort Element data, both in vectors and in linked lists. Each element has a long value. Your program must also keep track of how many times each copy constructor and destructor is called.

Abstract class VectorSorter

This is a subclass of Sorter and the base class for the vector sorting subclasses.

The vector sorting classes

The sorting classes SelectionSort, InsertionSort, ShellSortSuboptimal, and ShellSortOptimal are subclasses of VectorSorter. Each defines the member function run_sort_algorithm(). This member function is where you code each sorting algorithm.

For class ShellSortSuboptimal, use the halving technique for the diminishing increment. The value of the interval h for the first pass should be half the data size. For each subsequent pass, half the increment, until the increment is just 1.

For class ShellSortOptimal, use Knuth's formula 3i +1 for i = 0, 1, 2, 3, ... in reverse for the diminishing increment. For example: ..., 121, 40, 13, 4, 1.

Abstract class QuickSorter

This a subclass of VectorSorter and the base class for the quicksort subclasses. It does most of the work of the recursive quicksort algorithm. Its member function choose_pivot() calls abstract member function choose_pivot_strategy()which is defined by the two subclasses, QuickSortSuboptimal and QuickSortOptimal.

Class QuickSortSuboptimal

In subclass QuickSortSuboptimal, member function choose_pivot_strategy() should always return the leftmost value of the subrange as the "bad" pivot value to use to partition the subrange.

Class QuickSortOptimal

In subclass QuickSortOptimal, member function choose_pivot_strategy() should always return the "median of three" value of the subrange as the good pivot value. Look at the values at the left and right ends of the subrange and the value in the middle and then choose the value that is between the other two.

Class ListSorter

This is a subclass of Sorter and the base class for the MergeSort subclass. It has a pointer to a LinkedList of Node objects.

Class LinkedList

Class LinkedList manages a singly linked list of Node objects. Member function split() splits the list into two sublists of the same size, plus or minus one. Member function concatenate() appends another list to the end of the list.

Class MergeSort

Unlike the other sorting subclasses, subclass MergeSort sorts a singly linked list. Given a list to sort, it splits the list into two sublists. It recursively sorts the two sublists, and then it merges the two sublists back together. Merging involves repeatedly adding the head node of either sublist back to the main list. Which sublist donates its head depends on which head node has the smaller value. When one sublist is exhausted, concatenate the remaining nodes of the other sublist to the end of the main list.

When done properly, mergesort does not require any copying of data values. It does all of its work by relinking the nodes to move them from one list to another.

The data generation classes

Abstract class DataGenerator is the base class of subclasses DataRandom, DataSorted, DataReverseSorted, and DataAllZeros. Each subclass's member function generate_data() generates a vector of data that is random, already sorted, sorted in reverse, and all zeros, respectively.

The main() in class SortTests

The main program tests each sorting algorithm for data sizes 10, 100, 1000, and 10,000. It tests each algorithm against data that is random, already sorted, sorted in reverse, and all zeros. It outputs a table similar to the one below.

Comparing the algorithms

To compare the performances of the sorting algorithms, keep track of these statistics for each algorithm at each data size:

• The total number of copy constructor calls for the data elements being sorted.
• The total number of destructor calls of the data elements.
• The total number of times a data element is moved. Count one move whenever an element moves from one part of the vector or linked list to another. Whenever two elements are swapped, that counts as two moves.
• The total number of compares of two data elements. Count one compare whenever a data element is compared against another element.
• The amount of elapsed time (in milliseconds) required to do the sort.

Collect these statistics only during sorting.