quicksort_externo.py

from math import inf


K = 3


class Arquivo:

    registros = [3, 4, 5, 1, 2, 6, 8]

    def ler_registro(self, pos):
        return self.registros[pos - 1]

    def escrever_registro(self, pos, reg):
        self.registros[pos - 1] = reg


def quicksort_externo(arquivo, inicio, fim):
    # inicio e fim são, respectivamente, os endereços do primeiro e do último
    # registro do arquivo a ser considerado

    if fim - inicio >= 1:
        i, j = particionar(arquivo, inicio, fim)  # define os endereços de particionameto
        # i e j, que representam, respectivamente, o limite inferior e o limite
        # superior da partição

        if i - inicio < fim - j:
            # caso a primeira partição seja menor, ordenar ela primeiro
            quicksort_externo(arquivo, inicio, i) # ordena a primeira partição
            quicksort_externo(arquivo, j, fim) # ordena a segunda partição
        else:
            # caso a segunda partição seja menor, ordena ela primeiro
            quicksort_externo(arquivo, j, fim)
            quicksort_externo(arquivo, inicio, i)


def particionar(arquivo, inicio, fim):
    leitura_i = escrita_i = inicio # ponteiros de escrita e leitura inferiores
    leitura_f = escrita_f = fim # ponteiros de escrita e leitura superiores
    buff = [] # buffer inicialmente vazio, suporta K itens

    # inicialmente, os limites são no infinito
    limite_inferior = -inf
    limite_superior = inf

    lendo_esquerda = False # flag para alternar leitura entre os dois lados

    ultimo_registro = None # inicia o último registro lido como vazio

    i = inicio - 1 # inicia com o subarquivo esquerdo vazio
    j = fim + 1 # inicia com o subarquivo direito vazio


    while leitura_f >= leitura_i:
        # os ponteiros de leitura i e f são incrementados e decrementados,
        # respectivamente. O while roda até que os dois ponteiros cruzem, tendo
        # percorrido todos os registros

        if len(buff) < K -1:
            # se ainda há espaço no buffer
            if lendo_esquerda:
                lendo_esquerda = False
                # le o elemento da esqueda e move o cursor 
                ultimo_registro = arquivo.ler_registro(leitura_i)
                leitura_i += 1
            else:
                lendo_esquerda = True
                # le o elemento da direita, e move o cursor
                ultimo_registro = arquivo.ler_registro(leitura_f)
                leitura_f -= 1

            # insere o ultimo_registro no buffer
            buff.append(ultimo_registro)
        else:
            # buffer só tem mais um espaço disponível

            # para garantir que os cursores de escrita estejam a um passo atrás
            # dos cursores de escrita, a alternancia de leitura é interrompida
            # quando os ponteiros de escrita e leitura forem iguais
            if leitura_f == escrita_f:
                # caso os cursores superiores sejam iguais, andar leitura
                lendo_esquerda = True
                ultimo_registro = arquivo.ler_registro(leitura_f)
                leitura_f -= 1
            elif leitura_i == escrita_i:
                # caso os cursores inferiores sejam iguais, andar a leitura
                lendo_esquerda = False
                ultimo_registro = arquivo.ler_registro(leitura_i)
                leitura_i += 1
            else:
                # caso os cursores não estejam no mesmo lugar, ler normalmente

                if lendo_esquerda:
                    lendo_esquerda = False
                    # le o elemento da esqueda e move o cursor 
                    ultimo_registro = arquivo.ler_registro(leitura_i)
                    leitura_i += 1
                else:
                    lendo_esquerda = True
                    # le o elemento da direita, e move o cursor
                    ultimo_registro = arquivo.ler_registro(leitura_f)
                    leitura_f -= 1

            # agora, o buffer está cheio é o momento de escrever as alterações

            if ultimo_registro > limite_superior:
                # caso a chave do ultimo registro seja maior que o limite,
                # atualizar j e escrever na direita
                j = escrita_f
                arquivo.escrever_registro(escrita_f, ultimo_registro)
                escrita_f -= 1
            elif ultimo_registro < limite_inferior:
                # caso a chave do reg seja menor que o limite, escrever na
                # esquerda
                i = escrita_i
                arquivo.escrever_registro(escrita_i, ultimo_registro)
                escrita_i += 1
            else:
                # caso a chave esteja entre o limite inferior e superior, o
                # registro deve ser adicionado ao buffer. Mas como o buffer
                # está cheio, é necessário remover um elemento do buffer e
                # inserir no arquivo. Um dos registros é inserido no arquivo da
                # direita ou da esquerda. O registro é inserido no menor
                # arquivo, para manter a partição balanceada.

                # insere o registro no buffer
                buff.append(ultimo_registro)

                if escrita_i - inicio < fim - escrita_f:
                    # esquerda é o menor arquivo
                    reg = min(buff)
                    buff.remove(reg)
                    arquivo.escrever_registro(escrita_i, reg)
                    escrita_i += 1
                    limite_inferior = reg
                else:
                    reg = max(buff)
                    buff.remove(reg)
                    arquivo.escrever_registro(escrita_f, reg)
                    escrita_f -= 1
                    limite_superior = reg

    while escrita_i <= escrita_f:
        reg = min(buff)
        buff.remove(reg)
        arquivo.escrever_registro(escrita_i, reg)
        escrita_i += 1

    return i, j

arquivo = Arquivo()

print(arquivo.registros)
quicksort_externo(arquivo, 1, len(arquivo.registros))
print(arquivo.registros)