esercizio mediano dei mediani

'''
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 tempoO(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

'''
import random
import time

def main():

    '''
    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 = main()
    tempoTrascorso=time.clock() - inizio
    print(A,'\t\ttempo =\t',tempoTrascorso)

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