Pesquisa e Ordenação

Contribuição - Merge Sort

#Bubble Sort x Selection Sort x Insertion Sort x Quick Sort x Merge Sort
 
import random
import timeit
import matplotlib.pyplot as plt
  
b=[]; s=[]; c=[]; q=[]; m=[]
listaAuxB=[]; listaAuxS=[]; listaAuxI=[]; listaAuxQ=[]; listaAuxM=[]
tam=[100, 300, 600, 900, 1200, 2400, 4800, 10000]
tipo=[1, 2, 3, 4, 5]
  
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 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={}
              
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.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)
 
print(b); print(s); print(c); print(q); print(m)
print(tam)
 
grafico()