algorithm

Question

array has n elements and we need to sort them in non decreasing order as follows. first find minimum, remove this element from the array and find minimum of remaining elements, remove this element  and so on until array becomes emplty . In best case how many comparisons needed

Comments

it is selection sort technique, it will require n(n-1)/2= O(n²) comparisons

---

its O(n log n) using heap..how?

---

it is not following heap...

for heap first we have to build heap, according to qsn, array is initially random, and then we are one by one selecting minimum from the remaining elements...it is a process of selection sort..

---

MY SOLUTION

construct a min heap = O(n)

remove min = O(1)

call min heapify = O( log n)

O(n) + O(log n) = > O(n)

then for n elements O(n^2)

SOLUTION GIVEN

​​​​​​​construct a min heap 

remove min = O(1)

call min heapify = O( log n)

for n elements => O ( n log n)

please help in which one is right

Answer 1

This will be done by heap sort.

1.First we create a min heap using build heap method ......................O(n)

2.Then (remove min) +(min heapify)

.......................O(1) +O(log n)=O(logn)

After this we get first minimum as well as the remaining elements already forms a min heap... So no need to apply build heap again.

Instead second step will be repeated for all n elements until finally we get a sorted array.......n*O(logn)=O(nlogn)

Overall: O(n) + O(nlogn)=O(nlogn)