Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

how would I sort a list and get the top K elements? (STL)

Tags:

c++

stl

I have a vector of doubles. I want to sort it from highest to lowest, and get the indices of the top K elements. std::sort just sorts in place, and does not return the indices I believe. What would be a quick way to get the top K indices of largest elements?

like image 508
kop Avatar asked Oct 19 '10 19:10

kop


People also ask

Which sorting is used in STL?

In more details it is implemented using hybrid of QuickSort, HeapSort and InsertionSort.By default, it uses QuickSort but if QuickSort is doing unfair partitioning and taking more than N*logN time, it switches to HeapSort and when the array size becomes really small, it switches to InsertionSort.

How do I sort a set in STL?

Sorting an Unordered Set: An Unordered Set can be sorted by copying its elements to a Vector and then using the sort() method of the STL. For a better understanding of its implementation, refer to the well-commented C++ code given below.

How do you sort the elements of a vector?

Sorting a Vector in C++ in Ascending order A vector in C++ can be easily sorted in ascending order using the sort() function defined in the algorithm header file. The sort() function sorts a given data structure and does not return anything. The sorting takes place between the two passed iterators or positions.

How do you sort a function in C++?

Here, first – is the index (pointer) of the first element in the range to be sorted. last – is the index (pointer) of the last element in the range to be sorted. For example, we want to sort elements of an array 'arr' from 1 to 10 position, we will use sort(arr, arr+10) and it will sort 10 elements in Ascending order.


1 Answers

you could use the nth_element STL algorithm - this will return you the N greatest elements ( this is the fastest way,using stl ) and then use .sort on them,or you could use the partial_sort algorithm,if you want the first K elements to be sorted (:

Using just .sort is awful - it is very slow for the purpose you want.. .sort is great STL algorithm,but for sorting the whole container,not just the first K elements (; it's not an accident the existung of nth_element and partial_sort ;)

like image 69
Kiril Kirov Avatar answered Oct 02 '22 17:10

Kiril Kirov