def select(L, k):
    quickSelect(0, len(L) - 1, L, k)
    return L[:k]

"""
Explanation: An Array-Based Implementation of QuickSelect
The function quickSelect takes two arguments:
* L is a list of numbers,
* k is a natural number such that k &lt;= len(L). 
The function call quickSelect(L, k) returns a list of length k that contains the k smallest
elements of L, i.e. it satisfies the following specification:
- len(quickSelect(L, k)) = k,
- set(quickSelect(L, k)) = set(sorted(L)[:k]).
End of explanation
"""


def quickSelect(start, end, L, k):
    n = end + 1 - start
    assert k <= n, f'quickSelect({start}, {end}, {L}, {k})'
    if n == k:
        return
    m = partition(start, end, L)  # m is the split index
    if k <= m - start:
        quickSelect(start, m-1, L, k)
        return
    if k == m + 1 - start:
        return
    quickSelect(m+1, end, L, k - (m+1 - start))
    return

"""
Explanation: The function quickSelect(start, end, L, k) takes four arguments:
* start is an index into the list L,
* end   is an index into the list L,
* L     is a list of objects that can be compared using the operators &lt; or &lt;=,
* k     is a natural number such that k ≤ len(L).
The function call quickSelect(start, end, L, k) returns a list of length k that contains 
the k smallest elements of L[start:end+1].
The implementation of quickSelect(start, end, L, k) can be specified recursively via the following equations.
To simplify these equations we first define
$$ n := \texttt{len}(\texttt{L[start:end+1]}) = \texttt{end}+1 - \texttt{start}. $$
1. $n < k \rightarrow \texttt{quickSelect}(\texttt{start}, \texttt{end}, \texttt{L}, \texttt{k}) = \Omega$,
because when the length of L[start:end+1] is less than k there is no way to select the k smallest
   elements from L[start:end+1].
2. $n = k \rightarrow \texttt{quickSelect}(\texttt{start}, \texttt{end}, \texttt{L}, \texttt{k}) = \texttt{L[start:end+1]}$,
because when the list L[start:end+1] has exactly k elements, then the k smallest elements of 
   L[start:end+1] are all elements of L[start:end+1].
3. Otherwise we partition L[start:end+1] as in QuickSort, i.e. we define
   $$ m := \texttt{partition}(\texttt{start}, \texttt{end}, \texttt{L}). $$
   After the partitioning all elements in L[start:m] are less or equal than the pivot element L[m] 
   and all elements in L[m+1:end+1] are bigger than L[m].
   Then there are three cases:
   - $k \leq \texttt{len(L[start:m])} \rightarrow \texttt{quickSelect}(\texttt{start}, \texttt{end}, \texttt{L}, \texttt{k}) = 
                                                  \texttt{quickSelect}(\texttt{start}, \texttt{m}-1, \texttt{L}, \texttt{k})$,
   - $k = \texttt{len(L[start:m+1])} \rightarrow \texttt{quickSelect}(\texttt{start}, \texttt{end}, \texttt{L}, \texttt{k}) = \texttt{L[start:m+1]}$,
   - $k > \texttt{len(L[start:m+1])} \rightarrow 
      \texttt{quickSelect}(\texttt{L}, \texttt{k}) = \texttt{L[start:m+1]} + 
                                   \texttt{quickSelect}(m+1, \texttt{end}, \texttt{L}, \texttt{k} - \texttt{len(L[start:m+1])})$
To implement these equations we observe that $\texttt{len(L[start:m+1])} = m + 1 - \texttt{start}$.
End of explanation
"""


def partition(start, end, L):
    pivot = L[end]
    left  = start - 1
    for idx in range(start, end):
        if L[idx] <= pivot:
            left += 1
            swap(left, idx, L)
    swap(left + 1, end, L)
    return left + 1

"""
Explanation: The function $\texttt{partition}(\texttt{start}, \texttt{end}, L)$ returns an index $m$ into the list $L$ and 
regroups the elements of $L$ such that after the function returns the following holds:

$\forall i \in {\texttt{start}, \cdots, m-1} : L[i] \leq L[m]$,
$\forall i \in { m+1, \cdots, \texttt{end} }  : L[m] <    L[i]$,
$L[m] = \texttt{pivot}$.

Here, $\texttt{pivot}$ is the element that is at the index $\texttt{end}$ at the time of the invocation 
of the function, i.e. we have

$L[\texttt{end}] = \texttt{pivot}$

at invocation time.
The for-loop of partition maintains the following invariants:

$\forall i \in {\texttt{start}, \cdots, \texttt{left} } : L[i] \leq \texttt{pivot}$,
$\forall i \in {\texttt{left}+1, \cdots, \texttt{idx}-1} : \texttt{pivot} < L[i]$,
$L[\texttt{end}] = \texttt{pivot}$.

This algorithm has been suggested by Nico Lomuto.  It is not the most efficient implementation of partition, but
it is easier to understand than the algorithm given by Tony Hoare that uses two separate loops.
End of explanation
"""


def swap(x, y, L):
    L[x], L[y] = L[y], L[x]

"""
Explanation: The function $\texttt{swap}(x, y, L)$ swaps the elements at index $x$ and $y$ in $L$.
End of explanation
"""


L = [7, 8, 11, 4]
select(L, 2)

import random as rnd
rnd.seed(42)

"""
Explanation: Testing
End of explanation
"""


def testSelect(n, m):
    for i in range(n):
        L = [ rnd.randrange(2*m) for x in range(m) ]
        k = rnd.randrange(m)
        C = L[:]
        S = select(C, k)
        assert len(S) == k, f'{S} = select({L}, {k})'
        assert set(sorted(L)[:k]) == set(S)
        print('.', end='')
    print()
    print("All tests successful!")

%%time
testSelect(100, 100_000)

"""
Explanation: The function test_list(n, m) generates n random lists L of length m and checks whether 
quickSelect(L, k) satisfies its specification.  Here, the number k is a random number less 
than or equal to the length of the list.
End of explanation
"""


k = 1_000_000
L = [ rnd.randrange(1000 * k) for x in range(k) ]

%%time
S = select(L, 1500)

"""
Explanation: Performance Testing
End of explanation
"""


k = 1_000_000
L = [ rnd.randrange(1000 * k) for x in range(k) ]

%%time
S = sorted(L)[:1500]

"""
Explanation: This is quite a lot faster than to sort the list and extract the first $k$ elements from the sorted list.
End of explanation
"""


