Reference no: EM132290821 , Length: 2000 Words

Algorithm Engineering Project - Sort Race

Introduction - This project is to write an Html + Javascript program for a racing competition between different sorting algorithms. You program will run several algorithms in an interleaved fashion, where each algorithm will get a turn to perform a single step (one of its complexity operations) in its run, and maybe rearrange its array. This project will involve a Race Mgr that will loop, giving each algorithm a turn on each iteration by calling its pass() function. Finally, the Race Mgr will stop calling an algorithm's step() function when it returns that it has completed its sorting task. Each algorithm should be given its own copy of the array of integers to be sorted.

Algorithms - For this project, you will run three sorting algorithms: the O(N²) Insertion sort, the O(N*logN) Merge sort, and the O(N*logN) Quicksort.

Setup - Your program should select one of the sample inputs provided below at random. Each is a list of 12 hex digits. You will create an array of these integers.

Race Mgr & Step() Methods - The Race Mgr should loop until the first sort algorithm reports that it is done. (It should finish the iteration in which an algorithm reports done.) Each iteration should call the Step() function for each algorithm. The Step() function should run the algorithm through one more complexity operation, which is usually one comparison between elements and what the algorithm does based on the result of that comparison. The Step() function should also call a UI display update function to allow the display to update that algorithm's part of the display, if needed. This will allow the user to see each algorithm improve its position in the race.

Display - You should display three races each as a row array in its own vertical grid starting at the top row with the raw input elements. The row-by-row display is similar to the cellular automata display, but in 3 columns, one for each algorithm. Assume the input list to sort is only 12 elements comprised of hexadecimal digits taken from the range 0..B. Below are sample inputs that your program should be able to race. For a race, each sorting algorithm will start with the same input. You should be able to run any of the sample inputs. A new row for an algorithm should be provided as each "pass" is completed. While the steps/comparisons of an algorithm are being done, changes in element positions should be displayed. The prior row for the prior "pass" should be left as is, so that the user can see the "pass" differences.

Complexity Order - You should prepare a 1-page (at most) paper describing your analysis of the Big-O running time of whatever algorithm you use. Address the usual issues such as main operations, input size, etc.

Attachment:- Assignment & Sample File.rar