# select.py
# Copyright (C) 2006, 2007 Martin Jansche
#
# Permission is hereby granted, free of charge, to any person obtaining
# a copy of this software and associated documentation files (the
# "Software"), to deal in the Software without restriction, including
# without limitation the rights to use, copy, modify, merge, publish,
# distribute, distribute with modifications, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
# DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
# OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
# THE USE OR OTHER DEALINGS IN THE SOFTWARE.
#
# Except as contained in this notice, the name(s) of the above copyright
# holders shall not be used in advertising or otherwise to promote the
# sale, use or other dealings in this Software without prior written
# authorization.
"""
Fast (expected linear time) selection, based on Section 3.7 of "The
Design and Analysis of Computer Algorithms" by Aho, Hopcroft and
Ullman. Also contains a simple implementation of quicksort, which is
based on the same idea.
"""
import random as _random
_rng = _random.Random()
def select(k, S, comparator=cmp):
"""Select the k-th smallest element from S. Let x be the k-th
smallest element of S. Then this function returns x and
furthermore rearranges the elements of S in such a way that
S[k] == x; for all y in S[:k], y <= x; and for all z in S[k+1:],
x <= z."""
assert 0 <= k and k < len(S)
return _randSelect(S, comparator, 0, len(S)-1, k)
def _randSelect(A, comparator, p, r, i):
assert 0 <= p and p < len(A)
assert p <= r and r < len(A)
assert 0 <= i and i < len(A)
if p == r:
return A[p]
q = _randPartition(A, comparator, p, r)
k = q - p
if i == k:
return A[q]
elif i < k:
return _randSelect(A, comparator, p, q-1, i)
else:
assert i > k
return _randSelect(A, comparator, q+1, r, i-k-1)
def _swap(A, i, j):
if i == j:
return
assert 0 <= i and i < len(A)
assert 0 <= j and j < len(A)
tmp = A[i]
A[i] = A[j]
A[j] = tmp
return
def _randPartition(A, comparator, p, r):
assert 0 <= p and p < len(A)
assert p <= r and r < len(A)
i = p + _rng.randint(0, r - p)
assert p <= i and i <= r
_swap(A, r, i)
return _partition(A, comparator, p, r)
def _partition(A, comparator, p, r):
assert 0 <= p and p < len(A)
assert p <= r and r < len(A)
x = A[r]
i = p - 1
for j in xrange(p, r):
if comparator(A[j], x) <= 0:
i += 1
_swap(A, i, j)
i += 1
assert p <= i and i <= r
_swap(A, i, r)
return i
def quicksort(A, comparator=cmp):
"""Sort the array (or array-like object) A in place."""
_quicksort(A, comparator, 0, len(A)-1)
return
def _quicksort(A, comparator, p, r):
if p >= r:
return
assert 0 <= p and p < len(A)
assert 0 <= r and r < len(A)
q = _randPartition(A, comparator, p, r)
_quicksort(A, comparator, p, q-1)
_quicksort(A, comparator, q+1, r)
return
# eof