1. Give an example for when would be a worst case for selection sort algorithm?
ID: 3703824 • Letter: 1
Question
1. Give an example for when would be a worst case for selection sort algorithm? Also give the worst and best time complexity for selection sort algorithm?
2. What is the least number comparisons of bubble sort will execute in sorting an array of million numbers. Briefly explain your reason for choosing it?
a) one b) million
c) million*million
d) million * log(million) e) million-1
3. Here is an array of ten integers: 5 3 8 9 1 7 0 2 6 4 Draw this array after the TWO recursive calls of merge sort are completed, and before the final merge step has occurred
4. Which sorting algorithm will take least time when all elements of input array are identical? Consider typical implementations of sorting algorithms. Explain your understanding.
5. Suppose we are sorting an array using one of the specified sorting algorithms. After 4 iterations, the array elements are ordered as: 2 4 5 7 8 1 3 6. Briefly explain your reason for choosing it?
a) Insertion sort b) Selection sort c) Bubble Sort d) none of a, b and c
6. Consider the following list. List1 = {20, 10, 30, 40}
Show how Bubble Sort algorithm works for the above list
7. Consider the following list of integers: [1,2,3,4,5,6]. Show how this list is sorted by the following algorithms:
Explain how steps each sorting algorithm would take?
bubble sort
selection sort
insertion sort
merge sort
quick sort (you decide on the pivot value)
Explanation / Answer
If you have any problems with the answer or want me to edit the answer, just let me know in the comments and I will try to get on to it as soon as possible. Do give a positive rating if you think this answer helped.
We are required to do only 4 parts of a question.
1. The best case and worst case of selection sort is same, which is : O(n^2)
Example of worst case : 6 5 4 3 2 1
2. Bubble sort compares each element even if the element is sorted(best case). Hence the number of comparisons will be n^2 i.e million*million.
3. In first recursive call, merge sort will sort the left half: 1 3 5 8 9 7 0 2 6 4
Second recursive call, merge sort will sort the right half: 1 3 5 8 9 0 2 4 6 7
The array before final will be :
1 3 5 8 9 0 2 4 6 7
4. The least time will be observed in a already sorted array and insertion sort will take theta(n) time when input array is already sorted and identical as insertion sort is stable and will not compare each element.
6. Bubble sort compares two elements and, interchange them if left element is larger than the right element.
List1 = {20, 10, 30, 40}
First, 20 and 10 will compared and as 10 is larger than 10, it will be interchanged.
10, 20, 30, 40
Then 20 will be compared to 30, no change as 30 is larger than 20.
10, 20, 30, 40
Then 30 will be compared to 40 and similarly no change.
Hence the final list will be :
10, 20, 30, 40
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.