(a) Explain why insertion sort (as coded in the slides from lecture) is also fas

Question

(a) Explain why insertion sort (as coded in the slides from lecture) is also faster than its worst-case
asymptotic running time would suggest. What is it running time in this case?
(b) Selection sort as coded in class will take O(n2) time even when the array is already sorted. Modify
the code so that it completes in only O(n) time on an already-sorted array. (Hint: You’ll need to
keep some extra information as you seek the smallest value.)
(c) Repeat the previous part with mergesort. (Again, you’ll need to do extra work before making the
recursive calls to test if the array is already sorted.)

Explanation / Answer

a) Insertion sort worst case time complextiy is O(n2), but in case of sorted list its time complexity is O(n).. so it is better in this case.

every time it has to take an element from unsorted part.. and compare with the elements in the sorted part and place it in the sorted correct position.. complexity here is... for checking and moving is O(n2)..

in case of sorted array it no need to compare with all elements... because every element taking from unsorted part.. is already biggest element among all the elements in sorted part..

we came to know it by checking this element with the last element of the sorted part... so we no need to move or compare all the elements so.. the complexity is O(n) only.

b) before seeking the smallest element in selection sort we have to check whether the list is sorted or not, we can do it in O(n) time..

c=0;

for(i=0;i<n;i++)if(a[i]<a[i+1])c++;   /*a is sorted array*/

if c==n-1 then array is sorted... we have to stop here..

else     array is not sorted we can continue selection sort code..

Time complexty of this modified selection sort is O(n) in case sorted list..

c)In case merge sort also we can do the same thing what we have done in selection sort...

before calling recursive functions we have to check whether the list is sorted or not....

we can do it in O(n) time..

c=0;

for(i=0;i<n;i++)if(a[i]<a[i+1])c++;   /*a is sorted array*/

if c==n-1 then array is sorted... we have to stop here..

else     array is not sorted we can continue merge sort code..

Time complexty of this modified mergesort code is O(n) in case of sorted list..

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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