Find the k largest elements in order

by

One option would be the following:

  1. Using a linear-time selection algorithm like median-of-medians or introsort, find the kth largest element and rearrange the elements so that all elements from the kth element forward are greater than the kth element.

  2. Sort all elements from the kth forward using a fast sorting algorithm like heapsort or quicksort.

Step (1) takes time O(n), and step (2) takes time O(k log k). Overall, the algorithm runs in time O(n + k log k), which is very, very fast.

Hope this helps!

More Related Contents:

  1. C++ Sorting Algorithms [closed]
  2. Priority scoring algorithm [closed]
  3. What should be the algorithm of the below statement?
  4. Efficient way to add element to sorted datastructure [closed]
  5. What is stability in sorting algorithms and why is it important?
  6. Fastest sort of fixed length 6 int array
  7. Is there an O(n) integer sorting algorithm?
  8. Why is quicksort better than mergesort?
  9. Which sort algorithm works best on mostly sorted data? [closed]
  10. Merge Sort a Linked List
  11. Quicksort: Choosing the pivot
  12. What’s the fastest algorithm for sorting a linked list?
  13. Natural Sorting algorithm
  14. Compute the minimal number of swaps to order a sequence
  15. Which parallel sorting algorithm has the best average case performance?
  16. Fast algorithm implementation to sort very small list
  17. Sorting in linear time? [closed]
  18. median of three values strategy
  19. Sorting an array with minimal number of comparisons
  20. Quicksort vs heapsort
  21. What is a bubble sort good for? [closed]
  22. Sorting in place
  23. Write a program to find 100 largest numbers out of an array of 1 billion numbers
  24. Faster version of find for sorted vectors (MATLAB)
  25. Quicksort superiority over Heap Sort
  26. Can an array be grouped more efficiently than sorted?
  27. Search a sorted 2D matrix [duplicate]
  28. Comparison-based ranking algorithm
  29. Why is bubble sort O(n^2)?
  30. Stable separation for two classes of elements in an array

Leave a Comment