Lab 5 Sorting - Sort Descriptions PDF

Preview

Summary

Sort Descriptions...

Description

Lab 5 – Investigating Sorting Algorithms 1. Bogo Sort (O(∞)): This algorithm views a list, if it is sorted, the algorithm is complete. If the list is not sorted, the elements in the list are then randomized and the process is repeated. 2. Selection Sort (O(n^2)): This algorithm scans repeatedly from left to right and exchanges the smallest value towards the left until all values are accounted for. 3. Insertion Sort (O(n^2)): This algorithm scans the values from left to right and sets the least value on the left by inserting the values on the right one by one. 4. Bubble Sort (O(n^2)): This algorithm repeatedly passes through the values scanning and switching one value with the next (if required) from left to right in order to place the smallest values in order from the left. 5. Quick Sort (O(n^2)): This algorithm selects an element called the partition element and places values less than the partition element to the left of the element, and the values larger than the partition element to the right. This process is then repeated for both subsets created by the process before it, until the list is completely sorted. 6. Shell Sort (O(n^2)): This algorithm calculates the floor value of the number given when dividing the list amount (N) by 2. This value is then evaluated with the element to its left. If it is greater, the values switch places, if not they stay the same. The gap between the two values is then increased by one, and the process is repeated with a new value. This entire algorithm continues and repeats until the list is finally sorted. 7. Merge Sort (O(n*log(n))): This algorithm continues to divide the list by half until each element is in a list of its own, and then puts the sublists back together in order of least to greatest from left to right. 8. Gnome Sort (O(n^2)): This algorithm compares the current element with the previous element. If the previous element is less than the current element, the next element is searched. If the previous element is greater than the current element, then they are swapped and the next element is searched. This process is repeated until the list is in order. If the end of the list is reached, the list is complete. 9. Cocktail Sort (O(n^2)): This algorithm repeatedly passes through the values scanning and switching the value to the left with the one on the right if the left value is greater than the right value. This algorithm goes backwards after reaching the end completing the same process forwards and backwards throughout the list until no swaps are necessary.

10. Tree Sort (O(n^2)): This algorithm performs an inorder traversal search for what would be a binary search tree. This means that starting from position N = 0 to the next position, and so on, any element less than the current element goes to the left and any element greater than or equal to the current element goes to the right of the current element in the binary search tree. Once the tree is created, the elements are ordered in a list using inorder traversal: traverse left, place current node in list, traverse right, and continuously repeat inorder traversal until all nodes have been placed into the list, at which point the list would be sorted properly, least to greatest.

Works Cited “BogoSort or Permutation Sort.” GeeksforGeeks, 4 Jan. 2019, www.geeksforgeeks.org/bogosort-permutation-sort/. Accessed November 3th, 2020. “Selection Sort.” GeeksforGeeks, 2 May 2019, www.geeksforgeeks.org/selection-sort/?ref=lbp. Accessed November 4th, 2020. “Insertion Sort.” GeeksforGeeks, 25 July 2020, www.geeksforgeeks.org/insertion-sort/?ref=leftbar-rightbar. Accessed November 4th, 2020. “Bubble Sort.” GeeksforGeeks, 30 Sept. 2020, www.geeksforgeeks.org/bubble-sort/?ref=lbp. Accessed November 4th, 2020. “QuickSort.” GeeksforGeeks, 4 Sept. 2020, www.geeksforgeeks.org/quick-sort/?ref=lbp. Accessed November 4th, 2020. “ShellSort.” GeeksforGeeks, 20 Nov. 2018, w  ww.geeksforgeeks.org/shellsort/. Accessed November 4th, 2020. “Merge Sort.” GeeksforGeeks, 4 Nov. 2020, www.geeksforgeeks.org/merge-sort/?ref=leftbar-rightbar. Accessed November 4th, 2020. “Gnome Sort.” GeeksforGeeks, 19 July 2018, www.geeksforgeeks.org/gnome-sort-a-stupid-one/?ref=lbp. Accessed November 5th, 2020. “Cocktail Sort.” GeeksforGeeks, 5 Apr. 2018, www.geeksforgeeks.org/cocktail-sort/. Accessed November 5th, 2020. “Tree Sort.” GeeksforGeeks, 20 Apr. 2020, www.geeksforgeeks.org/tree-sort/. Accessed November 5th, 2020....