How to find the top n elements without sorting the array?

Is this possible???

Well I don't want to sort the array because the order is mandatory? After I have found the top n elements I want to modify them?

Is there any certain algorithM?? Help ???

this is no homework , hints are appreciated

Ty

4
Contributors
4
Replies
5
Views
9 Years
Discussion Span
Last Post by Salem

1) You could sort a copy of the array to determine the values and then search the original array for the desired values.

2) You could place the first n values of the array in a list using and insertion sort so the head of the list is the smallest and the tail the largest. Then compare the first element of the list, to the n + 1 (current) element in the original array. If the current element of the array is bigger than the smallest element of the list then delete the smallest element of the list and insert the current element of the array into the list in the appropriate spot of the list so it remains sorted. When array has been reviewed in it's entirety, then search through the array for the values in the list and do what you will.

Here are another 2 options:

1) Make a copy of the array, and do only a partial selection sort. Use the variation of selection sort that puts the largest element at the end. Since you only want the top n elements, only run the outer loop of selection sort n times, then your top n elements should all be at the end of your copied array.

2) Instead of making a copy of the array, search for the largest number in the array, then store the index of that number in a list or vector of some sort. Search again for the largest number in the array, but ignoring any indexes that are in your list of indexes, repeat n times.

how to ignore the elements that I have found??? is there any specific algorithm for this or would i have to implement this my self?