There is no programming assignment this week. You\'ll be working with pencil and

Question

There is no programming assignment this week. You'll be working with pencil and paper to demonstrate your knowledge of searching and sorting algorithms (or you could use a word processor or even spreadsheet, of course). 40 63 64 2 87 62 45 66 99 30 31 57 Show the state of the array above after each pass through the array using the following sorting algorithms. (In other words, use the method used in lecture to show how each sorting algorithm sorts the numbers above.) Also, for each algorithm, state the average big-O running time estimate. 1.Selection Sort 2.Bubble Sort (No swap flag. In other words, no stopping early when the list is sorted.) 3.Insertion Sort 4.Merge Sort 5.Quicksort. You must use the version given in the lesson and circle the pivot at each step. 6. List each number from the unsorted list above that will be examined if a linear search is used to search for the number 62. Also state the average big-O running time estimate for a linear search. Here the numbers are sorted: 02 30 31 40 45 57 62 63 64 66 87 99 7. List each number from the list above that will be examined if a binary search is used to search for the number 99. 8. List each number from the list above that will be examined if a binary search is used to search for the number 52. Note that 52 is not in the list. That doesn't change anything. There is still a sequence of numbers that are examined until the algorithm determines that it isn't there. 9. State the average big-O running time estimate for binary search.

Explanation / Answer

1. Selection sort

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray

original array:

40 63 64 2 87 62 45 66 99 30 31 57

2.

Bubble Sort works by repeatedly swapping the adjacent elements if they are in wrong order.

3.

4.Merge sort:

40 63 64 2 87 62 45 66 99 30 31 57

in merge sort each is divided into smaller sub arrays and then combined again

5.Quick sort

6.Linear search --complexity O(n)

40 63 64 2 87 62 45 66 99 30 31 57 --- when number 62 is searched the list is searched each element wise

so first element and then second element and so on

so 40,63,64,2,87 are searched until 62 is found

7.Binary search: Binary search can be applied on sorted list only.so the sorted list is

so the mid is calculated and compared with the target element 52, here low =0 , high = 11 mid = low+high/2 = 5

if the mid is equal to the target elemnt is found,if mid is greater than then the left list is searched similary if lesser than then right list searched

so a[5] is compared with 52 that is 57>52 so 52 may be present in left list , so the list reduces to

now again similarly low=0, high=4 mid = low+high/2 = 2

a[2] is compared with 52 that is 31<52

so 52 may be present in right list so the new list becomes 40 45

now again similarly low=4, high=5 mid = low+high/2 = 4

40<52

so list is reduced to 45

now again similarly low=5, high=5 mid = low+high/2 = 5

now finally it is compared with 45 which is not equal to 52 so element is not in the list

8. As the required element gets halved everytime you want to search the recurrence relation for the time complexity will be like this

T(N) = T(N/2) + O(1)

which gives rise to complexity of O(logN)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.