[Solved] Objective Project Offers Experience Implementing Sorting Algorithms Arrays Sorting Algorit Q37186560

Objective

This project offers experience of implementing — sortingalgorithms for arrays — sorting algorithms for linked lists —measuring and comparing algorithm performance for large datastructures

ABET Program Learning Outcomes:

The ability to recognize the need for data structures and choosethe appropriate data structure (1, 2, 6)

 The ability to evaluate the performance of an algorithm (1, 2,6)  The ability to implement and use linked lists (1, 2, 6)

 The ability to implement binary trees, and heaps (1, 2, 6)

 The ability to design and implement algorithms for varioussorting and searching problems (1, 2, 6) The Problem Theprogramming problem in this project is to implement and testseveral sorting algorithms applied for arrays and linked lists ofvarious sizes. In each case the data are integer numbers, usinggeneric types is not necessary. The goal of these applications isto collect experimental data on the performance of the appliedalgorithms. The observed data are to be compared to each other andto the theoretical Big-Oh estimates.

A written report is required to summarize your results ofanalyzing the implemented algorithms. The algorithms to be testedare  insertion sort of arrays

 insertion sort of linked lists

 merge sort of arrays

 merge sort of linked lists

 heap sort of arrays

Analysis and Design Input:

 Integer values randomly selected from the range 0 – 12,000,000(same range must be used for all structures when they compared toeach other)

 The size of the structure (varies between 20 and10,240,000)

 An unsorted structure of given size such that it stores therandomly selected integer values

Output:

 The sorted structure. For large structures of size >200only fifty elements evenly distributed over the structure shall beprinted to the console

 An estimate of the running time of the applied algorithms.

For this project, you have to define three classes

1. Class Sortings

This class is a utility class that contains the implementationsof the required algorithms. Each method is static. The class has nofields. All sorting results are to be increasingly ordered datasequences.

The required method headings are as follows:

public static void insertionSort( int[]data )

public static Node insertionSort( Node head )

public static void mergeSort( int[] data, int first, int n )

public static Node mergeSort( Node head )

public static void heapSort( int[] data )

An array to be sorted is passed as parameter data to therelevant methods. The recursive mergeSort method needs additionalparameters to specify the range to be sorted: data[first] …data[first+n-1 ].

Sorting methods for linked lists receive the head reference ofthe unsorted list as parameter and return the head reference of thesorted list.

Note that array sorters are void, they do not instantiateanother array. Private helper methods can be added to the Sortingsclass as necessary. They can be particularly useful for the mergesort algorithm, but also recommendable for the linked insertionsort and the heap sort as well.

2. Class Node

You are familiar with this class used in several previousassignments to represent the nodes of a linked list. Sortingapplications do not use the tail reference, lists are representedby their head. You may re-use one of your previous implementations,but for the current applications you may conveniently re-write theclass, since beside the constructor you only need the toString( )method for displaying test results. However, you cannot printmillions of data to the console, therefore you must limit thenumber of recursive calls in toString. The suggested limit is 20.To implement such limitation you have to declare a counter variableas a field in the Node class. Update the counter in the method, andmake the recursive call conditional in an if statement controlledby the counter. The counter must be reset to zero before every newdisplay application.

3. Class Test

This class shall exercise all the methods from Sortings andorganizes the performance analysis. You may include the main methodin this class, if so, all members of the class must be static. Ifyou create another Application class for main, none of the membersin Test are static.

Fields: int[ ] data: : to store the numbers in an array

Node head: to store the reference to the head node of a linkedlist that stores the numbers

int TOP = 12000000 named constant

Methods:

 randomData( ): void; takes an int parameter for data length;instantiates the data array, and instantiates the head field for alinked list. Fills the array with integers randomly selected fromthe range 0 <= x < TOP. Using the same for loop, the methodgenerates the nodes of the list with the same random numbers asused for the array entries. Note: If you load the array starting atindex 0, your loop shall feed the linked list at tail. If you wantfeeding at head, load the array backwards.

 testSort( ): void; parameters as suitable; this method callsthe sorting methods and measures the running time for each,independent of each other. Calls display method(s) to print thetime results and to demonstrate the sorting execution.

 displayArray( ) and displayList ( ) print arrays and linkedlists to the consol. Create an attractive display format for eachcase. For arrays larger than 200, print only 50 array entriesevenly distributed over the total array. For instance, Figure 1below illustrates the display of an array of length 300000.

 main( )

The array data[0..299999] was sorted in 16.39 seconds.

The resulting array is:

data[ 0] 21

data[6000] 238904

data[12000] 481443

data[18000] 721207

data[24000] 961016

data[30000] 1200480

data[36000] 1438963

data[42000] 1677970

data[48000] 1916379

data[54000] 2155558

data[60000] 2394058

data[66000] 2629376

data[72000] 2862326

data[78000] 3103038

data[84000] 3340798

data[90000] 3584410

data[96000] 3822442

data[102000] 4067575

data[108000] 4309194

data[114000] 4552299

data[120000] 4790055

data[126000] 5029607

data[132000] 5267807

data[138000] 5510326

data[144000] 5751761

data[150000] 5989749

data[156000] 6232703

data[162000] 6469388

data[168000] 6713051

data[174000] 6948927

data[180000] 7189037

data[186000] 7430532

data[192000] 7673084

data[198000] 7920143

data[204000] 8159646

data[210000] 8396322

data[216000] 8636451

data[222000] 8877219

data[228000] 9122181

data[234000] 9358565

data[240000] 9604353

data[246000] 9844392

data[252000] 10085564

data[258000] 10325063

data[264000] 10563061

data[270000] 10799306

data[276000] 11042243

data[282000] 11281520

data[288000] 11517798

data[294000] 11757536

figure 1.

Testing requirements

Testing must be carried out in two phases

Phase 1. This phase is supposed to eliminate bugs, and mustdemonstrate that all sorting methods in the program work correct.In this phase do not use random selections and do not use largestructures. Keep the size under 10 and you may create input arraysusing initializer lists and linked lists with direct instantiation.Test the boundary cases (empty structure, single element structure,two element structure). Empty and singleton structure do not needsorting. Document your test results by attaching short consoleprintouts to your code.

Phase 2. In this phase the program is applied to test andcompare the performance of working algorithms. Apply therandomData() method to fills the structures and let the structuresgrow by taking for size input values the numbers 20, 5000, 10000,20000, 40000, 80000, 160000, 320000, 640000, 1280000, 2560000,5120000, and 10240000. You may get an OutOfMemoryError on yourcomputer when using the largest data set(s) and alsoStackOverflowError in case of recursive methods. In these casesrestrict the input and/or comment out the method calls that causetrouble. Comment all your experience and use the results you areable to execute. Include a statement in your report specifying thevalue which could not be handled.

Report:

interpretation of the results Using Word or your favoriteeditor, create a table that lists the run time results as afunction of input size for all five sorting algorithms. The tableshould show the growing factor, that is the ratio of the currentrun time to the previous (shorter) run time.

Write a brief report containing your conclusions based a on thetable and possible break-down events. Your report should correlatethe theoretical “big-O” performance of each algorithm with theactual run times observed. In order to do this, state how the runtime is expected to change with the array size as the array sizegets doubled, match this against the change you actually observe,and finally state whether or not these changes agree.

In your report demonstrate the best case versus the worst caseperformance of the insertion sort algorithms. For this purpose donot use random data. Simply load the array indices to the array asvalues, first sorted in increasing order and for second, inreversed order.

Note that exact correspondence of observed results totheoretical performance is not expected, particularly for short runtimes. Because there is a certain small amount of error inherent ineach of the time measurements (“noise”), the results from thesmallest data sets may get buried in the noise. In fact, all runtimes will vary somewhat from one run to the next. The largest 3 or4 data sets are the most significant for each method. Your reportshould be clearly and professionally written with correct grammarand punctuation.

Hints

1. You must complete some designing details on your own. Forinstance the local variables will be needed in the testSort( )method, and you may or may not apply here loops. Also, the displaymethods may print a cluster of output at one call, or just oneresult.

2. The linked list implementations require local variables forNode references. A pseudo code is provided below for insertionsort, and a description of the method design for merge sort.

3. The implementation of the mergeSort method follows the arrayideas:

 divide

 mergeSort each of two halves

 merge

It is suggested that the divide (split) operation as well as themerge operation be implemented in private helper methods.

Splitting a linked list cannot be analogous to splitting anarray since the number of nodes in the list is not known, we cannotuse it for the halving procedure.

Instead, the split algorithm declares two Node references, saymiddle and fast initialized to head and head.link respectively,then it runs a while loop such that middle is forwarded one step,fast is forwarded two steps at each turn as long as fast reachesthe end of the list. Now head is the head of the first half of thelist and the link of middle is the head if the second half. Createa second head reference, then set middle.link to null (middle isnow the tail of the first half). To test your split method,temporarily declare it public. If the length of a list is an evennumber, the split must produce two lists of equal length. For themerge operation the head reference of each list is given, say head1and head2. Declare the Nodes head and tail to be used in the mergedlist. Variable head is assigned head1 or head 2, depending whichone stores smaller data and tail is initialized to head. Use head1and head2 as cursors on the corresponding lists, that is, everytime a cursor is merged, it moves up one step in the list. Themerge iteration stops when one of the cursor falls off the list.The remaining other list must be joined to tail.

4. Pseudo-code for insertion sort The method takes the headreference of a linked list as parameter, and returns the headreference of the sorted list. Note that this pseudo-code does notspecify any helper method, though using one is recommendable. TheinOrder reference below is a cursor up to which the list issupposed to be sorted. Its link named checkOrder is the next nodeto be investigated for insertion.

– if head or head.link null, send message and return null

– declare Node references inOrder and checkOrder //these workfor the outer while loop;

precursor, cursor // these work for the inner while loop– –

– initialize inOrder to head

– while inOrder link not null

checkOrder assigned inOrder.link

store checkorder data in a temp variable

if temp < head.data

rearrange links to insert checkOrder before head

update head

else

declare Node references

precursor, initialize it as head

cursor, initialize to head.link

while cursor.data < temp

update precursor and cursor (moving one step forward)

if cursor is not checkOrder

rearrange links to insert checkOrder between precursor andcursor

else

update inOrder (moving one step forward)

– return head

Documentation and style requirements

As usual, conform to the document “Java documentation and stylerequirements.” Document the methods you create (including any“helper” methods).

Expert Answer

---

Answer to Objective This project offers experience of implementing — sorting algorithms for arrays — sorting algorithms for li… . . .