In [6]:
plot()
import random
import matplotlib.pyplot as plt
import sys
sys.setrecursionlimit(3000)
def bubblesort(a):
for i in range(0, len(a)-1):
aux, j = a[i], i
if a[i] > a[i+1]:
a[i], j = a[i+1], j+1
a[j] = aux
return a
def bubblesort_improvement(sequence):
n = len(sequence)
is_sorted = False
while not is_sorted:
is_sorted = True
for i in range(n-1):
if sequence[i] > sequence[i+1]:
sequence[i], sequence[i+1] = sequence[i+1], sequence[i]
is_sorted = False
return sequence
# Melhor dos casos é quando nenhum número é trocado (ou seja já está ordenada)
# Pior dos casos é quando todos os números são trocados (lista completamente desordenada)
# passos elementares importantes: for (n-1) soma de n-1 vezes que se repete o ciclo
# calculo pela expressao 1/n^2 + 1/2n -n O(n^2)
class Ordena:
def __init__(self, lista):
self.lista = lista
def bubblesort(self):
for i in range(0, len(self.lista) - 1):
aux, j = self.lista[i], i
if self.lista[i] > self.lista[i + 1]:
self.lista[i], j = self.lista[i + 1], j + 1
self.lista[j] = aux
return self.lista
def selectionsort(self):
for j in range(0, len(self.lista) - 1): # de 0 a 2
minimo = j
for i in range(j + 1, len(self.lista)): # de 1 a 3
if self.lista[i] < self.lista[minimo]:
minimo = i
if minimo != j:
self.lista[j], self.lista[minimo] = self.lista[minimo], self.lista[j]
return self.lista
def insertionsort(self):
for j in range(1, len(self.lista)):
aux, i = self.lista[j], j
while self.lista[i - 1] > aux and i > 0:
self.lista[i], i = self.lista[i - 1], i - 1
self.lista[i] = aux
return self.lista
def mergesort(self, a):
if len(a) > 1:
meio = len(a) // 2
esquerda = a[:meio]
direita = a[meio:]
self.mergesort(esquerda)
self.mergesort(direita)
# definem se limites i e j
i = 0
j = 0
k = 0
# vamos comparar as listas que se pretendem juntar (ja de len=1) e se o
while i < len(esquerda) and j < len(direita):
if esquerda[i] < direita[j]:
a[k] = esquerda[i]
i = i + 1
else:
a[k] = direita[j]
j = j + 1
k = k + 1
while i < len(esquerda):
a[k] = esquerda[i]
i += 1
k += 1
while j < len(direita):
a[k] = direita[j]
j += 1
k += 1
return a
def mergesorthelper(self):
return self.mergesort(self.lista)
def qsort(self, a):
acima = []
abaixo = []
pivot2 = []
if len(a) > 1:
pivot = a[0]
for i in range(0, len(a)):
if a[i] < pivot:
abaixo.append(a[i])
elif a[i] > pivot:
acima.append(a[i])
else:
pivot2.append(a[i])
return self.qsort(abaixo) + pivot2 + self.qsort(acima)
return a
def qsort2(self, arr):
if len(arr) <= 1:
return arr
else:
return self.qsort([x for x in arr[1:] if x < arr[0]]) + [arr[0]] + self.qsort([x for x in arr[1:] if x >= arr[0]])
def quicksort1(self):
return self.qsort2(self.lista)
def tempomed_timeit(funcao, repeticoes=10):
# Calcula o tempo medio de execucao de uma funcao em python
import timeit
total_time = 0
for n in range(0, repeticoes):
tempo_inicio = timeit.default_timer()
funcao()
total_time += timeit.default_timer()-tempo_inicio
return total_time/repeticoes
def gera_inteiros(n):
a = []
for i in range(0,n):
a.append(random.randrange(10001))
return a
print(f"{'Numero de execucoes':<20}{'TM bubblesort ':<20}{' TM selectionsort':<20}{' TM insertionsort':<20}{' TMquicksort':<20}{' TM Mergesort':<20}{' TM SORT':<20}")
n = [100, 300, 500, 800, 1100, 1400, 1700, 2000]
lista1 = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []
lista6 = []
for ordem in n:
a = []
for i in range(0, ordem):
a.append(random.randrange(10001))
b = Ordena(a)
tmbb = tempomed_timeit(b.bubblesort)
tmss = tempomed_timeit(b.selectionsort)
tmis = tempomed_timeit(b.insertionsort)
tmqs = tempomed_timeit(b.quicksort1)
tmms = tempomed_timeit(b.mergesorthelper)
tmsort = tempomed_timeit(a.sort)
print(f"{ordem :<20}{ tmbb :<20}{ tmss :<20}{ tmis :<20}{ tmqs:<20}{ tmms:<20}{ tmsort:<20}")
lista1.append(tmbb)
lista2.append(tmss)
lista3.append(tmis)
lista4.append(tmsort)
lista5.append(tmqs)
lista6.append(tmss)
def plot():
plt.plot(n, lista1, label='Bubblesort')
plt.plot(n, lista2, label='Selectionsort')
plt.plot(n, lista3, label='Insertionsort')
plt.plot(n, lista5, label = 'Quicksort')
plt.plot(n, lista6, label= 'Mergesort')
plt.plot(n, lista4, label='Sort')
plt.legend()
plt.show()
Numero de execucoes TM bubblesort TM selectionsort TM insertionsort TMquicksort TM Mergesort TM SORT 100 3.1279999996058903e-050.00072065999999892942.5430000007986564e-050.00145639999999787050.00028355000000317438.100000002286833e-07 300 0.000148730000000796290.0040208900000038743.949000000034175e-050.00510842999999567850.000485420000003955471.1199999988775745e-06 500 0.000126169999998637640.0095056200000044560.000138050000003886450.0138788899999980240.00085582000000101741.7399999961753564e-06 800 0.000215740000001574120.0225662499999998549.905999999944015e-050.03673888999999235 0.00148362999999562822.9600000004847972e-06 1100 0.00026965000000132020.0445568200000025160.000136509999998679640.06653812000000414 0.00215986999999699934.130000007762646e-06 1400 0.00032412999999564820.07632339999999829 0.000203440000001364760.11790731000000107 0.00292999000000691 5.079999993995443e-06 1700 0.000395589999990875160.11360079000000098 0.00029896999999721170.16451934999999765 0.0029478299999965434.589999997506311e-06 2000 0.00037991000000090480.11750905000000386 0.000218379999998319360.18392259000000594 0.00388600000000565145.239999995865219e-06
plot()