Comparação de Desempenho de Algoritmos de Ordenação

 #----------------------------   ordenador.py

class Ordenador:
    def selecao_direta(self, lst): # selection sort
        for i in range(len(lst)-1):
            p = i
            for j in range(i+1, len(lst)):
                if lst[j] < lst[p]:
                    p = j
            lst[i], lst[p] = lst[p], lst[i]
        return lst
        
    def bolha(self, lst):
        for n in range(len(lst)-1,0,-1):
            for i in range(n):
                if lst[i] > lst[i+1]:
                    lst[i], lst[i+1] = lst[i+1], lst[i]
        return lst
        
    def bolha_curta(self, lst):
        for n in range(len(lst)-1,0,-1):
            trocou = False
            for i in range(n):
                if lst[i] > lst[i+1]:
                    lst[i], lst[i+1] = lst[i+1], lst[i]
                    trocou = True
                if not trocou:
                    return
        return lst
                    
def test():
    l = [5,4,3,8,6,7,2,1]
    o = Ordenador()
    s = o.selecao_direta(l)
    b = o.bolha(l)
    return s, b, s == b
#test()

#-------------------------------------   conta_tempos.py

import ordenador
import random as r
import time # 01/01/1970 UNIX
class ContaTempos:
    def lista_aleatoria(self, n):
        lista = [r.randrange(n) for i in range(n)]# gera de 1 a 3 digitos
        return lista
    def lista_quase_ordenada(self, n):
        lista = [x for x in range(n)]
        lista[n//10] = -500
        return lista
    def compara(self, n):
        lista1 = self.lista_aleatoria(n)
        #lista1 = lista_grande(n)
        lista2 = lista1[:] #clone
        o = ordenador.Ordenador()
       
        antes = time.time()
        o.bolha_curta(lista1)
        depois = time.time()
        print("Bolha c: ", depois - antes, " Listas aleatorias.")
        antes = time.time()
        o.selecao_direta(lista2)
        depois = time.time()
        print("Selecao: ", depois - antes)
       
        lista1 = self.lista_quase_ordenada(n)
        lista2 = lista1[:]
        antes = time.time()
        o.bolha_curta(lista1)
        depois = time.time()
        print("Bolha c: ", depois - antes, " Listas quase ordenadas.")
        antes = time.time()
        o.selecao_direta(lista2)
        depois = time.time()
        print("Selecao: ", depois - antes)           
def lista_grande(n):
    l = []
    for i in range(n):
        l.append(int(r.random()*100))
    return l
def main():
    pass
    c = ContaTempos()
    c.compara(1000)
main()

#--------------------------------   test_ordenador.py

import ordenador
import pytest
import conta_tempos
class TestaOrdenador:
    @pytest.fixture
    def o(self):
        return ordenador.Ordenador()
    @pytest.fixture
    def l_quase(self):
        c = conta_tempos.ContaTempos()
        return c.lista_quase_ordenada(100)
    @pytest.fixture
    def l_aleat(self):
        c = conta_tempos.ContaTempos()
        return c.lista_aleatoria(100)
    def esta_ordenada(self, l):
        for i in range(len(l)-1):
            if l[i] > l[i+1]:
                return False
        return True
    def test_bolha_curta_aleat(self, o, l_aleat):
        o.bolha_curta(l_aleat)
        assert self.esta_ordenada(l_aleat)
    def test_selecao_direta_aleat(self, o, l_aleat):
        o.selecao_direta(l_aleat)
        assert self.esta_ordenada(l_aleat)
    def test_bolha_curta_quase(self, o, l_quase):
        o.bolha_curta(l_quase)
        assert self.esta_ordenada(l_quase)
    def test_selecao_direta_quase(self, o, l_quase):
        o.selecao_direta(l_quase)
        assert self.esta_ordenada(l_quase)