Selection sort order

Admin 1
Viewed 108

My book says:

Suppose you have a group of N numbers and would like to determine the kth largest. This is known as the selection problem. Most students who have had a programming course or two would have no difficulty writing a program to solve this problem. There are quite a few “obvious” solutions. One way to solve this problem would be to read the N numbers into an array, sort the array in decreasing order.

It says that it would make sense to sort the array in decreasing order. How does that make sense? If I have an array of {1,9,3,7,4,6} and I want the greatest element, I would sort it in an increasing order so {1,3,4,6,7,9} and then return the last element. Why would the book say in decreasing order?

selection-sort sorting algorithm
2 Answers

Because you may not want the largest element, the book says

would like to determine the kth largest

If you sort it in ascending order, how do you know what the, say, 3rd largest number is without first finding out how big the array is?

This would be easier if the array was descending, as the 3rd largest will simply be the 3rd element.

user_104605380

The order itself is not that important, but if you want to k-th largest element, then if you sort in descending order, it is located at the k-th element (or k-1 if we start with index 0), whereas if we sort in ascending order, it is located at index n-k+1 (or n-k if the index starts at 0).

For lazy sorting algorithms (like the ones in Haskell and C# Linq's .OrderBy), this can in fact have implications with respect to time complexity. If we implement a lazy selection sort algorithm (so a generator), then this will run in O(k×n) instead of O(n2). If we use for example a lazy variant of QuickSort, it will take O(n + k log n) to obtain the first k elements.

In a language like Haskell, where laziness is really a key feature, one typically does not only aim to minimize the time complexity of the algorithm producing the entire result, but also producing subsets of the result.

user_675790
Related