operation 4. Suppose we sort an array of numbers, but it turns out every element

Question

operation 4. Suppose we sort an array of numbers, but it turns out every element of the array is the same, e.g., {17,17,17, ..., 173. (So, in hindsight, the sorting is useless.) a) What is the asymptotic running time of insertion sort in this case? b) What is the asymptotic running time of selection sort in this case? c) What is the asymptotic running time of merge sort in this case? d) What is the asymptotic running time of quick sort in this case? e) Give an example input list for which merge-sort and heap-sort take O(n log n) time, but for which insertion sort takes O(n) time. What if the list is reversed?

Explanation / Answer

Let's suppose the Array A = {17, 17, 17, ....} whose all elements are same is of size N then,

(a) For insertion sort we take every element of array and compare it with already sorted array elements to find it's suitable position and then place it there. It is like we will compare i+1th element of array with ith element of array till i>=0, so if key = A[i+1], the comparision we does is if A[i]>key then we shift i to i+1 position and decrement i and continue comparision. If A[i]<=key then we does nothing and go to next element in array.

So, now for array with same element, no element is greater than other element hence we will do nothing and move to next element simply in this way time complexity is O(N).

(b) For selection sort we find minimum element from array element every time and replaces it with the lowest position available in already sorted list. Like in first iteration we find the minimum element and replaces it with 1st element in array and then in second iteration we replace minimum number of remaining element with 2nd element in array and on. In this we iterate over array twice no matter all the elements are same or not. Hence time complexity is O(N2).

(c) For merge sort array is divided into sub arrays untill we get two elements and in an array and then after sorting these smaller array we merge them one by one. So elements value in array does not matter, hence time complexity is O(NlogN).

(d) For Quick sort we take a pivot element (best recommended is middle element) and then compare elements of array once from left of that element and then from right of that element and then divide array in two parts. Now, again same operation performed on these partitioned array one by one. This will make to iterate array twice as all elements are same, hence we need to compare pivot with all elements of array to divide in subarrays. Hence, time complexity is O(N2).

(e) Example Array = {1, 2, 3, 4, 5, 6, 7, 8, 9} i.e. already sorted array. If array is reversed then time complexity of merge-sort and heap-sort will still remain same as O(nlogn), while time complexity of insertion sort will become O(n2).

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

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