Analysis of Algorithms & Searching and Sorting
profile
modiishan21

TheShellsortisavariationofthebubblesort.docx
Home>Computer Science homework help>Analysis of Algorithms & Searching and Sorting
1. The Shell sort is a variation of the bubble sort. Instead of comparing adjacent values, the Shell sort adapts a concept from the binary search to determine a “gap” across which values are compared before any swap takes place. In the first pass, the gap is half the size of the array. For each subsequent pass, the gap size is cut in half. For the final pass(es), the gap size is 1, so it would be the same as a bubble sort. The passes continue until no swaps occur.

Below is the same set of values as per the bubble sort example in Chapter 18 (p. 681), showing the first pass of the Shell sort:

The pseudo-code for the Shell sort is as follows:

Create a class called ShellArray. It should create and populate an array of random integers based on a size supplied to the constructor. Implement the Shell sort as a method of this class. Create a driver class to instantiate and sort several different arrays of different sizes.

Hint: Implement a toString method for the ShellArray class, so it is easy to output the results of each swap to demonstrate that your algorithm is working correctly.

2. Modify the sorts listed in Chapter 18 (selection sort, insertion sort, bubble sort, quick sort, and merge sort) by adding code to each to tally the total number of comparisons and total execution time of each algorithm. Execute the sort algorithms against the same list, recording information for the total number of comparisons and total execution time for each algorithm. Try several different lists, including at least one that is already in sorted order.

Note that the original code for all the sorts is contained in the Chapter 18 source code folder. It is recommend that you use a spreadsheet to present the test cases you have prepared, along with the comparisons and execution time.

Hint: Remember that arrays are passed by reference in Java. Use Arrays.copyOf() or a similar method to test each sort method on the exact same data content in separate arrays.