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


def quicksort(array):
    n = len(array)
    if n < 2 :
        return array
    pivot = array[0] # wir werden das später randomisieren
    smaller = [x for x in array if x < pivot]
    equal = [x for x in array if x == pivot] # in der Praxis kann dies mehr als ein Element sein! 
    larger = [x for x in array if x > pivot]
    return quicksort(smaller) + equal + quicksort(larger)  


def quicksortRand1(array):
    n = len(array)
    if n < 2 :
        return array
    pivot = array[random.randint(0, n-1)] # wir werden das später randomisieren
    smaller = [x for x in array if x < pivot]
    equal = [x for x in array if x == pivot] # in der Praxis kann dies mehr als ein Element sein! 
    larger = [x for x in array if x > pivot]
    return quicksort(smaller) + equal + quicksort(larger)  


def quickSelect(array, index):
    n = len(array)
    if n < 2 :
        return array[index]
    pivot = array[random.randint(0, n-1)] # wir werden das später randomisieren
    smaller = [x for x in array if x < pivot]

    if index < len(smaller):
        return quickSelect(smaller, index)
    else:
        index = index - len(smaller)

    equal = [x for x in array if x == pivot] # in der Praxis kann dies mehr als ein Element sein! 

    if index < len(equal):
        return equal[0]
    else:
        index = index - len(equal)


    larger = [x for x in array if x > pivot]
    return quickSelect(larger, index)



def quicksortRand2(array):
    random.shuffle(array)
    return quicksort(array)