0
$\begingroup$

Given an array with $2n$ elements, we want to select the greatest $n$ elements, i.e. obtain new array with these elements, no matter of the ordering (it's not necessary to be sorted). Can we do this in $O(n)$ time?

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! What are your thoughts? Where did you encounter the problem? What was the broader context? If this was in a textbook or course, what topics have you studied most recently? Can you tell us more about your thought process so far when you tried to solve this yourself? We're happy to help you understand the concepts but just solving an exercise-style problem for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Jun 24 '17 at 1:33
  • $\begingroup$ You can do it in linear time by using a randomized selection algorithm. $\endgroup$ – Aristu Jun 24 '17 at 1:45
2
$\begingroup$

Proceed in two phases.

  1. Determine the median of the input.
  2. Partition the input with the median as the pivot (cf. Quicksort).

Both steps take worst-case linear time. Note, though, that in practice you'd not use a linear-time selection algorithm but rather Quickselect, which is faster in expectation.

$\endgroup$
0
$\begingroup$

Let $L$ be a list of $n$ elements and $k \in \mathbb{N}, k < n$.

First Problem: Given $e \in L$, how to find the index of $e$ as if $L$ were sorted?

Solution: Just walk $L$ and count how many elements are smaller than $e$

Using this idea define a partition function, that takes the list $L$ and an element $e$ and returns all elements smaller than $e$ and greater than $e$.

def partition(L, e):
    # Partitions L into 3 lists
    # [_ < e], [e], [e < _]
    smaller = []
    bigger = []
    for elm in L:
        if elm < e:
            smaller.append(elm)
        if elm > e:
            bigger.append(elm)
    return smaller, [e], bigger

The selection algorithm described here outputs the $k$ smallest elements of $L$, you can easily modify the Python code to do what want. It works like this:

Pick $e \in L$ at random.

+--------------------+---+----------------------------+
|                    | e |                            |
+--------------------+---+----------------------------+

Now make a partition in $L$.

+--------------------+---+----------------------------+
|      LEFT          | e |        RIGHT               |
+--------------------+---+----------------------------+

Now check one of the following cases:

If $length(LEFT) < k$, then you already have some $length(LEFT) + 1$ smaller elements, that is $LEFT + \{e\}$, and need to find the other $k - length(LEFT) - 1$ in a smaller subset of $L$.

+--------------------+---+----------------------------+
|       LEFT         | e |        RIGHT               |
+--------------------+---+----------------------------+

                         +----------------------------+
                         |         New L              |
                         +----------------------------+

If $length(LEFT) = k$. Then it's over, you're really lucky.

If $length(LEFT) > k$. Then it's the same problem, in a smaller array.

+--------------------------------+---+----------------+
|       LEFT                     | e |    RIGHT       |
+--------------------------------+---+----------------+

+--------------------------------+
|         New L                  |
+--------------------------------+

The python code:

def selectK(L, k):
    from random import choice
    e = choice(L)
    left, mid, right = partition(L, e)

    if len(left) < k:
        return left + [e] + selectK(right, k - (len(left) + 1))
    if len(left) == k:
        return left
    if len(left) + 1 == k:
        return left + [e]
    if len(left) > k:
        return selectK(left, k)

Test case:

L = [56, 24, 68, 36, 16, 4, 44, 40, 32, 8, 28, 20, 72, 64, 60, 52, 76, 0, 48, 12]
Output for k=6: [0, 4, 16, 8, 12, 20]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.