import random 
import timeMyPrograms
import sys
from englishVocabulary import *
from timeMyPrograms import *
from englishTwoLetterWords import *
sys.setrecursionlimit(1000000)


def randomizedQuicksort(array):
    new_array = array[0: ] # eine Kopie anlegen 
    random.shuffle(new_array)
    result = quicksort(new_array)    
    return result


def quicksort(array):

    if (len(array) < 2):
        return array

    pivot = array[0] # das ist das rote Element auf den Folien

    


    left = [x for x in array if x < pivot]
    middle = [x for x in array if x == pivot]
    right = [x for x in array if x > pivot]

    left = quicksort(left)
    right = quicksort(right)

    return left + middle + right 



# Problem: waehle aus einem Array 
# das k-kleinste Element aus
# select(array, 0) soll das Minimum gegen,
# select(array, 1) das zweitkleinste

# Methode 1: k-mal das kleinste suchen und immer wieder ausschließen
#
# Minimum finden: n-1 
# zweitkleinste: n-2 
# drittkleinste: n-3
# k-t kleinste: n-k
#
# Insgesamt haben Sie dann n-1 + n-2 + ... + n-k Vergleiche.
# Also irgendwie doch wieder Omega(n*k)
#
# lazySelect (array,n/2) braucht also Omega(n^2) Vergleiche. 


# naiveSelect sortiert erstmal, und dann 
# gibt es das k-te Element zurück.
#
# Braucht also Theta(n log n) Schritte.


def naiveSelect(array, k):
    sortedArray = randomizedQuicksort(array)
    return sortedArray[k]

    
# Wir sind faul und nehmen an,
# dass 0 <= k <= n-1 gilt. 

def quickSelect(array, k):

    if (len(array) <= 1):
        return array[k]

    index = random.randint(0, len(array)-1)

    pivot = array[index] # das ist das rote Element auf den Folien


    left = [x for x in array if x < pivot]
    middle = [x for x in array if x == pivot]
    right = [x for x in array if x > pivot]

    if (k < len(left)):
        return quickSelect(left, k)

    k = k - len(left)

    if (k < len(middle)):
        return middle[k]

    k = k - len(middle)

    return quickSelect(right, k)




# Der Median einer Menge S aus n Elementen ist ein Wert x, 
# so dass höchstens n/2 Elemente kleiner und höchstens n/2 
# Elemente größer sind. 

# Salopper ausgedrückt, der Wert auf Position floor(n/2),
# wenn wir S sortieren.