CSIS-385: Homework 3

CSIS-385: Homework 3

This project can be completed in groups of size 2 or smaller. See schedule for due date.

Overview

Implement four basic sorting algorithms and compare the number of comparisons and assignment statements to figure out which sorting algorithm is the best.

Algorithm Details

For all four algorithms, the input to the algorithm should be a simple array of integers. Optionally, you can input the size of the array if you need to. The output should be the sorted array. If you use Java, you should pass the original array as a function parameter and return the sorted array as the return value.

1. Implement Insertion Sort

Insertion Sort is an easy to implement O(N2) sorting
algorithm. Insertion Sort is actually very efficient for
partially sorted lists, such as the one pictured here.
Implement the Insertion Sort algorithm described Figure 1: Partially Sorted List
on page 241 of the text.

2. Implement Mergesort

In theory, Mergesort is one of the most efficient sorting algorithms. It does a very good job of minimizing the number of comparisons, but it does not minimize the number data elements that must be moved or swapped. Implement the Mergesort algorithm described on pages 220 and 221 of the text.

3. Implement Quicksort

In practice, Quicksort is one of the fastest sorting algorithms but it performance varies greatly depending on the characteristics of the input. Implement the Quicksort algorithm described on pages 245 and 246 of the text.

4. Implement Wickedsort

There are two very simple improvement to the basic Quicksort algorithm that dramatically improve its run-time. We will call the improved algorithm Wickedsort.

First, pick a good pivot. Picking the first number for each sub-problem isn’t always the best strategy. Computing the median isn’t practical. Try to think of a quick strategy for picking a pivot value that is likely to split the list in half. Implement this strategy.

Second, once the sub-problems become very small, the partitioning strategy is not as efficient as Insertion Sort, probably because picking a good pivot value is more work than sorting a very small list. When sub-problems become small, you can actually stop the recursion prematurely. Notice that Quicksort stops when index i equal index j, which means the sub-problem is of size 1. Try stopping the recursion when the sub-problem size reaches 7 or less items. You will be left with a partially sorted list that looks similar to the one in Figure 1. To finish sorting, all you have to do is call Insertion Sort, which should be insanely efficient. This call to Insertion Sort should be consider part of WickedSort.

Implement the two improvement described above. Your improved algorithm is actually a hybrid combination of Quicksort followed by a simple insertion sort.

Test Program

Write a test program that generates a random array of integers and calls each sorting algorithm. Each of the four algorithms should sort a separate copy of the random array, so that everything is as fair as possible. But instead of generation just one array, we should test the four algorithms on different sized arrays. Randomly generate ten arrays of size 100, 200, 400, 800, 1600, … 51,600. For each array, run the four sorting algorithms and count the total number of comparisons and the total number of assignment statements that each of the 4 algorithms execute.The output should look like this for each input size (note: these are just sample numbers):

Input Size = 100

Insertion Sort: 4700 Comparisons 8560 Assignments

Mergsort: 1342 Comparisons 3755 Assignments

Quicksort: 2303 Comparisons 2055 Assignments

Wickedsort: 1689 Comparisons 1899 Assignments

After printing the total comparisons and assignments for each of the 10 input arrays, you should print a summary of all 10 inputs. For each of the four algorithms, count the total number of comparisons needed to sort all 10 arrays and simply divide this number by the sum of all the input sizes, i.e., 100+200+400+…+51,600. Repeat this process to compute and print the average number of assignment statements relative to the input size. You’ll probably have to use long integers or double precision floats to perform the arithmetic.

Insertion Sort: 77.6 Comparisons 92.4 Assignments

Mergsort: 31.2 Comparisons 44.5 Assignments

Quicksort: 51.4 Comparisons 49.6 Assignments

Wickedsort: 30.4 Comparisons 29.3 Assignments

Counting Assignment Statements

Each of the four algorithms should include an extra parameter for storing and counting the total number of assignment statement executed by the algorithm. Before calling the algorithm set the counter to zero. Increment the counter for each instance of an assignment statement, i.e., every = symbol. Also, remember that increments (++, +=, -= and -- ) are also assignment statements, so be sure to count them. Do not count the increment statements used to count the increment statements, otherwise you will find yourself in an infinite recursive loop and your brain will explode.

Counting Comparison Statements

Each of the four algorithms should include another extra parameter for storing and counting the total number of comparison statement executed by the algorithm. Before calling the algorithm set the counter to zero. Increment the counter for each comparison statement. Remember that comparisons include <, >, <=, >=, !=, and ==.

Deliverables

Email me your source code, which should be a single working program. Print the output of your program and submit it in class on the due data. Also, answer the following questions.

1.  Does the test program conclusively show which algorithm is the best? If yes, which algorithm is the best. If no, why isn’t the test conclusive?

2.  Is there anything wrong with how we tested these 4 algorithms? If yes, suggest a better way. If no, is there any way to improve the testing.