ssignment 8 – Sorting
Objective
Learn how to select and implement sorting algorithms
Supports learning outcome 2, 3
2. Select the correct data structure and algorithm to solve specific problems.
3. Implement data structures and algorithms in computer code.
Introduction
Here is your practical application of data structures; sorting. There are literally hundreds of sorting algorithms and Topic – Sorting Techniques covers most of the important ones. Sorting is also tied very closely to searching, as it is much easier to search a sorted list. The Wikipedia article on sorting is actually quite interesting and you should have recognition of many of the different techniques – https://en.wikipedia.org/wiki/Sorting_algorithm
Assignment
You will need to fork your JSFiddle for Your List into a new Fiddle. In this Fiddle, we are going to add sorting functions. This is a great time to clean up your list of things you have learned. You should start with your code for your List/Stack/Queue and fork a new Fiddle to which you will add the sorting functions.
You should automatically populate Your List with 20 elements (random strings).
Once you have completed this – you will add the insertion sort as a function.
The interface should have buttons to (1) Repopulate the list with Random strings, (2) Sort list with selected algorithm 1 (3) Insert a user entered value into the sorted list. After each operation, it should display the new list.
| Original Random CharactersThis table column will fill in when the user hits Create Randomized String List |
Results of SortPut the results of the first,sort into the 2nd column |
Results of InsertionPut the results of the second sort into the 3rd column |
Option 4 here will insert the new string entered by the user (you will need a textbox to enter the string) in the correct sorted position, and you should print the new list with the new element on the screen.
For a nice clean interface, you may want to create a table with three columns and put the insert button on columns 2 and 3 and the results of sorting the list (printed in column 1) in columns 2 and 3 below the button. This is not required, but it does give you an opportunity to look at various methods of creating an interface to present results (you will do a lot of this in COP4813).
The code for this table n HTML is
<input type="button" value="Create Random String List" onclick="displayArray()"></input> <input type="button" value="Sort with Insertion Sort" onclick="insertionSort()"></input> <input type="textbox" id="string_to_insert" value="aaaaaaaa"></input> <input type="button" value="Insert String" onclick="insertString()"></input> <br/> <table> <tr> <td><div id="unsorted"></div></td> <td><div id="sorted1"></div></td> <td><div id="sorted2"></div></td> </tr> </table>
When you insert the “String” ensure that it inserts into the correct location in both of the sorted lists.
Note: Your insertion function should NOT SORT the entire List after the insert. You should insert the element into the correct location in your List without having to resort the entire List. This will give it a complexity of O(n) – it is doable in O(log n) – but I will accept a O(n) solution.
Assignment Grading –
Randomized String – 2 points
Insertion Sort and display – 5 Points
Insert User Value and display- 3 Points
