QuickSelectDeterm.py

import random
import time




'''
File name : divide_n_quintuple
Created on : 18/11/2016
@author: --> Stefano Pica N° 0203868
Python Version  3.5.2

'''


def dividi_n_quintuple(lista):

    '''funzione che divide la lista data in quintuple e restituisce
    una lista contenete le quituple divise in sottoliste
    usando solo una lista di appoggio'''

    listaQuintuple=[]
    indice=0
    while indice < len(lista):
        listaQuintuple += [lista[indice : indice + 5]] # seleziono gli elementi tramite SLICE e anche se
        indice += 5                                    # l'indice supera la lunghezza della lista python nn restituisce
                                                       # errore ma inserisce i rimanenti elementi
    return listaQuintuple


#if __name__ == '__main__':
    #dividi_n_quintuple(lista=[1,2,3,4,5,6,7,8,9,0,10,11,12,13,14,15])


###########################################################################################

def selectionSort(l):
    """ It sorts the given Python list in ascending order.
        The key idea is that at the k-th step, you put the the right element in position k.
        O(n^2)
    """
    for k in range(len(l) - 1):
        minPos = k
        for j in range(k + 1, len(l)):
            if l[j] < l[minPos]:
                minPos = j
        l[minPos], l[k] = l[k], l[minPos]   #Assegnamento multiplo che permette di non usare variabili temporanee
    print(l,'\tselectionSort')
    return l



###########################################################################################
'''
File name :listaMediani
Created on : 19/11/2016
@author: --> Stefano Pica N° 0203868
Python Version  3.5.2

'''

def listaMediani(lista):
    '''
        funzione che prende la lista di quintuple richiama la funzione mediano_Quintuple
        e restituisce la lista dei mediani


    '''
    listaMediani=[]

    for i in(lista):

        if len(i) == 5:                                        #se è una quintupla richiamo mediano_Quintuple

            mediano=mediano_Qintuple(i)
            listaMediani.append(mediano)
                                                               # se non è una quintupla la riordino con selectionSort tempo O(n^2)
        else:                                                  #se è pari prendo n+1 della metà cioè [1,2,3,4] prendo
            listaOrdinata = selectionSort(i)
            listaMediani.append(listaOrdinata[int(len(i)/2)])  #il 3  se [1,2] prendo 2  ; se è dispari < 5 prendo il mediano
                                                               # cioè [1,2,3] prendo il 2
    return listaMediani                                        # se è [1] prendo 1


######################################################################################################


'''
File name :mediano_di_Qintuple.py
Created on : 19/11/2016
@author: --> Stefano Pica N° 0203868
Python Version  3.5.2

'''
def mediano_Qintuple(lista):

        '''
        funzione che restituisce il mediano di una quintupla in 6 confronti
        come nella propietà 5.1
        cioè esegue 6[n/5] confronti

        '''

        if lista[0] > lista[1]:
            lista[0],lista[1] = lista[1],lista[0]

        if lista[2] > lista[3]:
            lista[2],lista[3] = lista[3],lista[2]

        if lista[1] > lista[3]:
            lista[1],lista[4] = lista[4],lista[1]

            if lista[0] > lista[1]:
                lista[0],lista[1] = lista[1],lista[0]

        else:
            lista[3], lista[4] = lista[4], lista[3]
            if lista[2] > lista[3]:
                lista[2],lista[3] = lista[3],lista[2]

        if lista[1] > lista[3]:
            lista.append(lista.pop(1))
            if lista[0] > lista[2]:
                return lista[0]
            else:
                return lista[2]

        else:
            lista.append(lista.pop(3))
            if lista[1] > lista[2]:
                return lista[1]
            else:
                return lista[2]


#if __name__ == '__main__':
    # lista=[6,1,1,4,5]
     #a=mediano_Qintuple(lista)
    # print (a)




#################################################################################################

'''
File name :medianoDeiMediani
Created on : 19/11/2016
@author: --> Stefano Pica N° 0203868
Python Version  3.5.2

'''


def mediano_dei_mediani(lista):

    '''
    prende la lista e con chiamate ricorsive su dividi_n_quintuple e listaMediani
    restituisce il mediano dei mediani

    '''

    #lista = lista_di_prova

    while len(lista) > 1 :                        #finchè la lista dei mediani non diveta di un solo elemento
                                                    # richiamo le funzioni ricorsivamente -> dividi e listaMediani-> che
        quintuple=dividi_n_quintuple(lista)
        print(quintuple,'\tquituple')               # dentro richiama-> (medianoQuintuple)

        lista = listaMediani(quintuple)

        print(lista,'\tmediani')


    return lista

######################################################################################

#if __name__ == '__main__':
    #inizializzazione

    #step=510

    #lista_di_prova = [None]*step

    #for i in range(0,step):

        #lista_di_prova[i] = random.randint(0,step)

    #print(lista_di_prova,'\tlista')
    #inizio=time.clock()
    #A = mediano_dei_mediani()
    #tempoTrascorso=time.clock() - inizio
    #print(A,'\t\ttempo =\t',tempoTrascorso)

 ##########################################################################################################






##################################################################################

def partition(lista, left, right, det=False):
    inf = left
    sup = right + 1

    #if not det:
        #mid = random.randint(left, right)
        #l[left], l[mid] = l[mid], l[left]  # scambio il perno con il primo elemento dell'intervallo considerato

    mid = mediano_dei_mediani(lista)  # If deterministic, it is set to the first element. Otherwise, since we swapped the randomically chosen median with the left element, we set mid to left.

    #if printSwitch.dumpOperations:
    print("Selected median:", mid)

    while True:
        inf += 1
        while inf <= right and lista[inf] <= lista[left]:
            inf += 1

        sup -= 1
        while lista[sup] > lista[left]:
            sup -= 1

        if inf < sup:
            lista[inf], lista[sup] = lista[sup], lista[inf]
        else:
            break

    lista[left], lista[sup] = lista[sup], lista[left]

    #if printSwitch.dumpOperations:
    print("- " * left + str(lista[left:right + 1]) + " -" * (len(lista) - right - 1))

    return sup











###################################################################################


'''
File name :
Created on :
@author: --> Stefano Pica N° 0203868
Python Version  3.5.2

'''



def quickSelectDet(lista, position):  # position 1...n

    '''

    QuickSelect  deterministico cioè gli passo come mid il mediano dei mediani

    '''

    if position <= 0 or position > len(lista):
        return None
    return recursiveQuickSelectDet(lista, 0, len(lista) - 1, position)


def recursiveQuickSelectDet(lista, left, right, position):
    #if printSwitch.dumpOperations:
    print("recursiveQuickSelectRand({},{},{})".format(left, right, position))

    if left > right:  # controllo superfluo
        return

    if left == right and position - 1 == left:
        return lista[position - 1]

    mid = partition(lista, left, right, det=False)
    #if printSwitch.dumpOperations:
    print("mid: {}".format(mid))

    if position - 1 == mid:
        return lista[mid]
    if position - 1 < mid:
        return recursiveQuickSelectDet(lista, left, mid - 1, position)
    else:
        return recursiveQuickSelectDet(lista, mid + 1, right, position)




# End of quickSelect
if __name__ == '__main__':
    basel = [5, 34, 26, 1, 4, 2, 17, 50, 41, 11]
    k = 5
    lista = list(basel)
    print(lista)
    print(quickSelectDet(lista,k))