cont.py

import matplotlib.pyplot as plt
import random
from random import randrange
import timeit


tempos_bubble = []
tempos_selection = []
tempos_insertion = []
tempos_quick = []
tempos_marge = []
tempos_shell = []
tempos_counting = []
quanNum = []

def insertion_sort(lista):
    for i in range(1,len(lista)):
        x = lista[i]
        j = i-1
        while j>=0 and x<lista[j]:
            lista[j+1] = lista[j]
            j=j-1
        lista[j+1] = x

def selection_sort(lista):
    for i in range(0, len(lista) - 1):
        imin = i
        for j in range(i + 1, len(lista)):
            if (lista[j] < lista[imin]):
                imin = j
        if i != imin:
            aux = lista[imin]
            lista[imin] = lista[i]
            lista[i] = aux


def bubble_sort(lista):
    for j in range(0, len(lista)):
        for i in range(0, len(lista) - 1):
            if (lista[i] > lista[i + 1]):
                aux = lista[i + 1]
                lista[i + 1] = lista[i]
                lista[i] = aux

def partition(lista, start, end, pivot):
    lista[pivot], lista[end] = lista[end], lista[pivot]
    store_index = start
    for i in range(start, end):
        if lista[i] < lista[end]:
            lista[i], lista[store_index] = lista[store_index], lista[i]
            store_index += 1
    lista[store_index], lista[end] = lista[end], lista[store_index]
    return store_index
                     
def quick_sort(lista, start, end):
    if start >= end:
        return lista
    pivo = randrange(start, end + 1)
    new_pivo =partition(lista, start, end, pivo)
    quick_sort(lista, start, new_pivo - 1)
    quick_sort(lista, new_pivo + 1, end)



def merge_sort(lista):
    if len(lista) < 1:
		
        meio = len(lista)/2
        esquerda = merge_sort(lista[:meio])
        direita = merge_sort(lista[meio:])
    
        i, j, k = 0, 0, 0
        while i < len(esquerda) and j < len(direita):
     
                if esquerda[i] < direita[j]:
                    lista[k]=esquerda[i]
                    i += 1
                else:
                    lista[k]=direita[j]
                    j += 1
                k += 1
     
        while i < len(esquerda):
     
                lista[k]=esquerda[i]
                i += 1
                k += 1
     
        while j < len(direita):
                lista[k]=direita[j]
                j += 1
                k += 1
	 

  
def shell_Sort(lista):

    count_sublist = len(lista)//2
    while count_sublist > 0:
     
       for pos_start in range(count_sublist):
           sort_gap_insertion(lista,pos_start,count_sublist)


       count_sublist = count_sublist // 2


def sort_gap_insertion(lista, start, gap):

    for i in range(start + gap, len(lista), gap):

        val_current = lista[i]
        pos = i

        while pos>=gap and lista[pos-gap] > val_current:

            lista[pos] = lista[pos-gap]
            pos = pos-gap

        lista[pos] = val_current

def counting_sort(lista):
    """in-place counting sort"""
    unicos = [i for i in lista if lista.count(i) < 2]
    maximo = max(unicos)

    m = maximo + 1
    count = [0] * m               
    for a in lista:
        count[a] += 1            
    i = 0
    for a in range(m):       
        for c in range(count[a]):
            lista[i] = a
            i += 1

def crialistarand(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

i = 1000
 
tam = 12000
  
while (i <= tam):
    quanNum.append(i)  
    lista = crialistarand(i)
    tmp = lista
    tempos_bubble.append(timeit.timeit("bubble_sort({})".format(lista), setup="from __main__ import bubble_sort", number=1))    
    tempos_selection.append( timeit.timeit("selection_sort({})".format(lista), setup="from __main__ import selection_sort", number=1))
    tempos_insertion.append( timeit.timeit("insertion_sort({})".format(lista), setup="from __main__ import insertion_sort", number=1))
    tempos_quick.append( timeit.timeit("quick_sort({}, {}, {})".format(lista, 0, len(lista) - 1), setup="from __main__ import quick_sort", number=1))
    tempos_marge.append( timeit.timeit("merge_sort({})".format(lista), setup="from __main__ import merge_sort", number=1))
    tempos_shell.append( timeit.timeit("shell_Sort({})".format(lista), setup="from __main__ import shell_Sort", number=1))  
    tempos_counting.append( timeit.timeit("counting_sort({})".format(lista), setup="from __main__ import counting_sort", number=1))
    if (i == 1000):
        i += 2000
    else:
        i += 3000
    print(i)

fig, ax = plt.subplots()
plt.title('Bubble/Selection/Insertion/Quick/Marge/Shell/Counting')
ax.plot(quanNum,tempos_bubble, label="buble")
ax.plot(quanNum,tempos_selection, label="selection")
ax.plot(quanNum,tempos_insertion,label="insertion")
ax.plot(quanNum,tempos_quick,label="quick sort")
ax.plot(quanNum,tempos_marge,label="marge sort")
ax.plot(quanNum,tempos_shell,label="shell sort")
ax.plot(quanNum,tempos_shell,label="counting sort")

plt.xlabel('Quant.Elemen')
plt.ylabel('Tempo')
legend = plt.legend(loc='upper center', shadow=True)
frame = legend.get_frame()
frame.set_facecolor('0.90')
plt.xlim([250,12000])
plt.show()