CODEWITHSUNDEEP
arraysalgorithmsorting
Kevin doesmath
Kevin doesmath

Reputation: 113

K largest elements of an array, sorting algorithm

I have been stuck on this problem and was hoping someone would give the answers and explain please.

You are given an unsorted array A of ints with no repeated elements, and asked to find the Kth largest elements in descending sorted order. For example if A is the array [11,6,1,2,15,7,4,8,20] and K = 3, then the answer should be [20,15,11]. Describe how you would modify selection sort and heapsort to solve this problem (two separate answers). What is the worst case running time of your algorithms, as a function of N = A.length and K?

Upvotes: 0

Views: 377

Answers (1)

Amadan
Amadan

Reputation: 198496

What selection sort normally does:

  • Find highest element, swap to first place
  • Find next highest element, swap to second place
  • ...
  • Find second-to-last element, swap to second-to-last place
  • Done.

The normal running time is O(N * N), because each of the N steps is a search problem, which is O(N).

You can just stop when you found the first K elements. If you abort it early, it's not N steps any more; but each step is unchanged.

and so the big-O

of the aborted selection sort is thus O(K * N).

Heap sort is done in two steps: heapify and siftdown. Heapify (creating the heap structure) has to be done properly, and it will remain unchanged. Since it's performed in less operations than siftdown, it is omitted from heap sort's big-O.

Siftdown (swapping elements from the heap into a sorted array) is very, very similar to selection sort, but the operation performed in each of N steps to find the next highest element is faster: O(log N).

Since siftdown does pretty much the same thing, conceptually, as the selection sort, you can abort that as well as soon as it has found the top K results.

This means the big-O

of the aborted heap sort is thus O(K * log N).

Upvotes: 3

Related Questions