Topic 7: Searching and Sorting Important concepts: Search/Sort algorithms complexities Search/Sort algorithms similarities/differences Sorting algorithms tracing Example Questions: Q1: Given the list {2, 4, 6, 8, 3, 5, 7, 9}. Before the last pass of mystery sort, the list becomes {2, 4, 6, 8, 3, 5, 7, 9}. What is mystery sort algorithm? a) Insertion sort b) Merge Sort c) Quick Sort d) Neither, after the pass before the last pass, all the items of the list, must be in their right order except for only one item Q2: Which of the following causes the smallest element to be placed to its correct place in the array? a) Bubble Sort b) Insertion sort c) Merge Sort d) Quick Sort Q3: In Quicksort algorithm, sequence of the main steps is: a) Quicksort(Left part), Partition by pivot, Quicksort(Right part) b) Quicksort(Right part), Partition by pivot, Quicksort(Left part) c) Partition(Left part), Quicksort(Entire array), Partition(Right part) d) Partition by pivot, Quicksort(Left part), Quicksort(Right part) Q4: Given the following array, what is the total number of swaps that would be performed if the bubble sort algorithm was applied? {6, 3,4, 1, 7, 8, 9,5} Q5: Given the following array, what is the content of the array before the last pass of the mergesort algorithm? {3,4,6, 1, 7, 9, 8,5} Q6: Given the following array, what is the content of the array after the third pass of the selection sort algorithm? {8, 9, 7, 6, 5, 4, 3, 1}