Objective: To get a feel for big-oh notation while experimenting with searching. To start the lab: Download and extract the file lab2.zip from http://www.cs.uni.edu/~fienup/cs052s11/labs/index.htmThe lab2.zip file you downloaded and extracted contains several the following sorting algorithms which sort inascending order (i.e., from smallest to largest): bubbleSort.py - bubble sort code which does NOT stop early bubbleSortB.py - bubble sort code which stops early if no swapping is needed during a scan of the unsortedpart insertionSort.py - the insertion sort code discussed in homework #1 selectionSort.py - the selection sort code we developed in classEach program runs the sorting algorithm several time with different initial orderings of list items. The followinginitial orderings of 10,000 items are timed by each program:1. list in descending order generated by: range(10000,0,-1)2. list in ascending order generated by the previous sort3. list split in half by two descending sequences generated by: range(5000,0,-1) + range(10000,5000,-1)4. list in random order5. list in random order again to check for consistenceComplete the following timings by running the each program. selectionSortinsertionSortbubbleSortBbubbleSortRandom order2Random order 1Two descendinghalvesAscendingDescendingInitial Orderingof ItemsTimings of Sorting Algorithm on 10,000 items (seconds) Study the code and answer the following questions about the sorting algorithms:a) Why does the bubbleSort algorithm take less time on the ascending ordered list than the descending orderedlist?b) Why does the bubbleSortB algorithm take A LOT less time on the ascending ordered list than the descendingordered list?Data Structures (810:052) Lab 2 Name:___________________________Lab 2 - 1c) Why does the insertionSort algorithm take A LOT less time on the ascending ordered list than the descendingordered list?d) Why does the insertionSort algorithm take less time on the descending ordered list than the bubbleSortalgorithm on the descending ordered list?e) Why does the selectionSort algorithm take less time on the descending ordered list than the insertionSortalgorithm on the descending ordered list?After you have answered the above questions, raise your hand and explain your answers. If you complete all parts of the lab, nothing needs to be turned in for this lab. If you do not get done today,then show me the completed lab in next week’s lab period. When done, remember to log off and take your USB drive.Data Structures (810:052) Lab 2 Name:___________________________Lab 2 -
View Full Document
Unlocking...