Pesquisa e Ordenação

Radix Sort

import random
import timeit
import matplotlib.pyplot as plt
    
b=[]; s=[]; c=[]; q=[]; m=[]; l=[]; t=[]; r=[]
listaAuxB=[]; listaAuxS=[]; listaAuxI=[]; listaAuxQ=[]; listaAuxM=[]; listaAuxL=[]; listaAuxT=[]; listaAuxR=[]
listaaux=[]
tam=[100, 300, 600, 900, 1200, 2400, 4800, 7000]
tipo=[1, 2, 3, 4, 5, 6, 7, 8]
    
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 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==7: #Radix
        listaAuxR=listaOriginal[:]
        tempo8 = timeit.timeit("radixSort({})".format(listaAuxR),setup="from __main__ import radixSort", number=1)
        r.append(tempo8)
        listaAuxR={}
                
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.legend()
    plt.xlabel('Quantindade')
    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)
   
print(b); print(s); print(c); print(q); print(m); print(l); print(t); print(r)
print(tam)
   
grafico()