CSC 1061 Week 05 Lists and Sorts PDF

CSC 1061 DATA STRUCTURE: LIST SORTS OBJECTIVES AGENDA: WEEK 05 Design and implement 1. Static Array Data Structures: collection classes that use Bag and List partially filled arrays to store 2. RemoveByIndex Example a collection of...

CSC 1061 DATA STRUCTURE: LIST SORTS OBJECTIVES AGENDA: WEEK 05 Design and implement 1. Static Array Data Structures: collection classes that use Bag and List partially filled arrays to store 2. RemoveByIndex Example a collection of elements 3. Bag Compared to List Simulate selection sort, 4. ADT Do's and Don'ts bubble sort insertion 5. Data Structures Do's and Don'ts sort, merge sort, quick sort 6. Bubble Sort & Selection Sort and heap sort 7. Other Sorts Explain the runtime advantage of using one sort over another. ARRAY DATA STRUCTURES: BAG | LIST Bag is an unordered List is an ordered collection of collection of values that values that may have duplicates. may have duplicates. List are described like a TODO list and order should be kept in- tack. This Photo by Unknown author is licensed under CC BY-NC-ND. REMOVEBYINDEX EXAMPLE: BAG | LIST bool Bag::removeByIndex(int index) bool List::removeByIndex(int index) { { if(index >= 0 && index = 0 && index < size) int i; { for(i = index; i < size-1; i++) data[index] = data[--size]; { return true; data[i] = data[i+1]; } } return false; size--; } return true; } return false; What is the general BigO analysis of each function? Bag and } List  COMPARE AND CONTRAST A. Items are unordered B. C. Items are unordered GetItem Bag List D. IsEmpty E. Add to end F. Add in order by shifting or sorting G. FindItem H. Remove by replacing end item over itemToRemove I. Remove by shifting or sorting J. ClearAll K. WriteFile L. ReadFile  DO'S ADT CLASS OOP DON'TS Constructors: create and Have the data initialize objects of the class structure read from class has a data member keyboard input in a Setters (modifiers) getter function setDataMember Have the data Getters (accessors) structure output to getDataMember console output in a setter function toString: format data for console as string Have redundant code toFileString: format data for file as string Overload operators Leave any function without a return path Relational Operators ==, !=, , = Use inline function for Insertion Operators > instruction (;)  DO'S DATA STRUCTURE CLASS DON'TS Default constructor – empty collection Have the data Follow data member rules – invariant structure read from keyboard input Getters (accessors): Have the data contains structure output to size, MAX console output isEmpty Have redundant code at, operator[] Leave any function writeFile without a return path Setters (modifiers): Use inline function append, readFile for more than 1 code instruction (;) removeItem, removeByIndex, clearAll BUBBLE SORT BUBBLE SORT ALGORITHM (PROGRAMIZ) 1. First Iteration (Compare and Swap) 1. Starting from the first index, compare the first and the second elements. 2. If the first element is greater than the second element, they are swapped. 3. Now, compare the second and the third elements. Swap them if they are not in order. 4. The above process goes on until the last element 2. Remaining Iteration 1. The same process goes on for the remaining iterations. 2. After each iteration, the largest element among the unsorted elements is placed at the end. SELECTION SORT SELECTION SORT ALGORITHM (PROGRAMIZ) 1. Set the first element as minimum if sorting ascending or the algorithm can also be done starting with a maximum sorting descending order. 2. Compare minimum with the second element. If the second element is smaller than minimum, assign the second element as minimum. Compare minimum with the third element. Again, if the third element is smaller, then assign minimum to the third element otherwise do nothing. The process goes on until the last element. 3. After each iteration, minimum is placed in the front of the unsorted list. 4. For each iteration, indexing starts from the first unsorted element. Step 1 to 3 are repeated until all the elements are placed at their correct positions. SORTS Using XSortLab (external link) to visualize the sorts, ZyBooks weekly module and the Runestone Tutorials research each of the below sorting algorithms and answer the following questions for each. 1. What is the general algorithm of the sort? 2. What is the general BigO analysis? Merge Sort Quick Sort Insertion Sort Shell Sort