Pesquisa e Ordenação

Contribuição - Heap Sort

import random
import timeit
import matplotlib.pyplot as plt
     
b=[]; s=[]; c=[]; q=[]; m=[]; l=[]; t=[]; r=[]; k=[]; h=[]
listaAuxB=[]; listaAuxS=[]; listaAuxI=[]; listaAuxQ=[]; listaAuxM=[]; listaAuxL=[]; listaAuxT=[]; listaAuxR=[]; listaAuxBt=[]; listaAuxH=[]
listaaux=[]
tam=[100, 300, 600, 900, 1200, 2400, 4800, 7000]
tipo=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
     
def bubbleSort(lista):
    for i in range (0,len(lista)):
        for j in range(0, len(lista)-1):
            if lista[j]>lista[j+1]:
                aux=lista[j+1]
                lista[j+1]=lista[j]
                lista[j]=aux
         
     
def selectionSort(lista):
    for i in range (len(lista)-1,0,-1):
        valorminimo=0
        for j in range(1, i+1):
            if lista[j]>lista[valorminimo]:
                valorminimo=j
        temp=lista[i]
        lista[i]=lista[valorminimo]
        lista[valorminimo]=temp
         
     
def insertionSort(lista):
    for i in range(1, len(lista)):
        chave=lista[i]
        j=i-1
        while j>=0 and chave<lista[j]:
            lista[j+1]=lista[j]
            j-=1
        lista[j+1]=chave
         
     
def quickSort(lista):
    L=[]
    R=[]
    if len(lista)<=1:
        return lista
     
    chave =lista[len(lista)//2]
    for i in lista:
        if i<chave:
            L.append(i)
        if i>chave:
            R.append(i)
    return quickSort(L)+[chave]+quickSort(R)
    
def mergeSort(lista):
    if len(lista) > 1:
        meio = len(lista)//2
        listaDaEsquerda = lista[:meio]
        listaDaDireita = lista[meio:]
        mergeSort(listaDaEsquerda)
        mergeSort(listaDaDireita)
        i = 0
        j = 0
        k = 0
        while i < len(listaDaEsquerda) and j < len(listaDaDireita):
            if listaDaEsquerda[i] < listaDaDireita[j]:
                lista[k]=listaDaEsquerda[i]
                i += 1
            else:
                lista[k]=listaDaDireita[j]
                j += 1
            k += 1
        while i < len(listaDaEsquerda):
            lista[k]=listaDaEsquerda[i]
            i += 1
            k += 1
        while j < len(listaDaDireita):
            lista[k]=listaDaDireita[j]
            j += 1
            k += 1
    
def shellSort(lista):
    aux = len(lista) // 2
    while aux > 0:
         for i in range(aux, len(lista)):
             temp = lista[i]
             j = i
             while j >= aux and lista[j - aux] > temp:
                 lista[j] = lista[j - aux]
                 j -= aux
             lista[j] = temp
         aux //= 2
   
def countSort(lista):
    maximo = max(lista)
    minimo = min(lista)
    count_array = [0]*(maximo-minimo+1)
   
    for val in lista:
        count_array[val-minimo] += 1
    for i in range(minimo, maximo+1):
        if count_array[i-minimo] > 0:
            for j in range(0, count_array[i-minimo]):
                listaaux.append(i)
                  
def radixSort(lista):
  RADIX = 10
  tamMax = False
  temp , aux = -1, 1
    
  while not tamMax:
    tamMax = True
    pilha = [list() for _ in range( RADIX )]
    
    for  i in lista:
      temp = i // aux
      pilha[temp % RADIX].append( i )
      if tamMax and temp > 0:
        tamMax = False
    
    a = 0
    for b in range( RADIX ):
      buck = pilha[b]
      for i in buck:
        lista[a] = i
        a += 1
    
    aux *= RADIX
     
def bucketSort(lista):
    partMax = max(lista)
    part1 = [list() for _ in range(partMax)]
    for i in lista:
        part1[(i//10)].append(i)
    list_aux = []
    for part2 in part1:
        if len(part2) > 0:
            list_aux.append(quickSort(part2))
    return list_aux

def heapSort(a):  
    def selet(inicio, contador):  
        raiz = inicio  
  
        while raiz * 2 + 1 < contador:  
            filho = raiz * 2 + 1  
            if filho < contador - 1 and a[filho] < a[filho + 1]:  
                filho += 1  
            if a[raiz] < a[filho]:  
                a[raiz], a[filho] = a[filho], a[raiz]  
                raiz = filho  
            else:  
                return  
  
    contador = len(a)  
    inicio = contador // 2 - 1  
    fim = contador - 1  
  
    while inicio >= 0:  
        selet(inicio, contador)  
        inicio -= 1  
  
    while fim > 0:  
        a[fim], a[0] = a[0], a[fim]  
        selet(0, fim)  
        fim -= 1 
                
def listaRan(tam, lista):
    random.seed()
    i=0;
    while i<tam:
        num=random.randint(1,10*tam)
        if num not in lista:
            lista.append(num)
            i+=1
    return lista
     
def time(i,  listaOriginal):
    if i==1: #Bubble
        listaAuxB=listaOriginal[:]
        tempo = timeit.timeit("bubbleSort({})".format(listaAuxB),setup="from __main__ import bubbleSort", number=1)
        b.append(tempo)
        listaAuxB={}
            
    if i==2: #Selection
        listaAuxS=listaOriginal[:]
        tempo2 = timeit.timeit("selectionSort({})".format(listaAuxS),setup="from __main__ import selectionSort", number=1)
        s.append(tempo2)
        listaAuxS={}
    
    if i==3: #Insertion
        listaAuxI=listaOriginal[:]
        tempo3 = timeit.timeit("insertionSort({})".format(listaAuxI),setup="from __main__ import insertionSort", number=1)
        c.append(tempo3)
        listaAuxI={}
           
    if i==4: #Quick
        listaAuxQ=listaOriginal[:]
        tempo4 = timeit.timeit("quickSort({})".format(listaAuxQ),setup="from __main__ import quickSort", number=1)
        q.append(tempo4)
        listaAuxQ={}
    
    if i==5: #Merge
        listaAuxM=listaOriginal[:]
        tempo5 = timeit.timeit("mergeSort({})".format(listaAuxM),setup="from __main__ import mergeSort", number=1)
        m.append(tempo5)
        listaAuxM={}
            
    if i==6: #Shell
        listaAuxL=listaOriginal[:]
        tempo6 = timeit.timeit("shellSort({})".format(listaAuxL),setup="from __main__ import shellSort", number=1)
        l.append(tempo6)
        listaAuxL={}
           
    if i==7: #Counting
        listaAuxT=listaOriginal[:]
        tempo7 = timeit.timeit("countSort({})".format(listaAuxT),setup="from __main__ import countSort", number=1)
        t.append(tempo7)
        listaAuxT={}
          
    if i==8: #Radix
        listaAuxR=listaOriginal[:]
        tempo8 = timeit.timeit("radixSort({})".format(listaAuxR),setup="from __main__ import radixSort", number=1)
        r.append(tempo8)
        listaAuxR={}
         
    if i==9: #Bucket
        listaAuxBt=listaOriginal[:]
        tempo9 = timeit.timeit("bucketSort({})".format(listaAuxBt),setup="from __main__ import bucketSort", number=1)
        k.append(tempo9)
        listaAuxBt={}
        
    if i==10: #Heap
        listaAuxH=listaOriginal[:]
        tempo10 = timeit.timeit("heapSort({})".format(listaAuxH),setup="from __main__ import heapSort", number=1)
        h.append(tempo10)
        listaAuxH={}
                 
def grafico():
    plt.plot(tam,b,label = "Bubble Sort")
    plt.plot(tam,s,label = "Selection Sort")
    plt.plot(tam,c,label = "Insertion Sort")
    plt.plot(tam,q,label = "Quick Sort")
    plt.plot(tam,m,label = "Merge Sort")
    plt.plot(tam,l,label = "Shell Sort")
    plt.plot(tam,t,label = "Counting Sort")
    plt.plot(tam,r,label = "Radix Sort")
    plt.plot(tam,k,label = "Bucket Sort")
    plt.plot(tam,h,label = "Heap Sort")
    plt.legend()
    plt.xlabel('Quantidade')
    plt.ylabel('Tempo')
    plt.show()
     
listaOriginal=[]
for i in tam:
    print("Gerando dados para o tamanho: ")
    print(i)
    listaRan(i, listaOriginal)
    time(1, listaOriginal)
    time(2, listaOriginal)
    time(3, listaOriginal)
    time(4, listaOriginal)
    time(5, listaOriginal)
    time(6, listaOriginal)
    time(7, listaOriginal)
    time(8, listaOriginal)
    time(9, listaOriginal)
    time(10,listaOriginal)
    
print(b); print(s); print(c); print(q); print(m); print(l); print(t); print(r); print(k); print(h)
print(tam)
    
grafico()