Qual é o algoritmo de classificação em espaço constante mais eficiente?

Estou procurando um algoritmo de classificação para matrizes int que não aloque nenhum byte que não seja o tamanho da matriz e esteja limitado a duas instruções:

SWAP: troca o próximo índice pelo atual;
MOVER: move o cursor para o índice +1 ou -1;

Ou seja, você não pode trocar índices não vizinhos nem trocar o índice 100depois de trocar o índice 10. Qual é o algoritmo mais eficiente - ou seja, aquele que usa a menor quantidade de movimentos totais?

algorithms sorting in-place MaiaVictor
fonte

Não é tão estranho, é uma máquina física que classifica uma lista de carrinhos colados a uma fita enrolada. A máquina só pode mover a fita para frente ou para trás e apenas trocar cartões vizinhos, de corse. No mundo real, você não pode se teletransportar por aí, então, essas são as restrições ...

MaiaVictor

Então, quando você diz que deseja um algoritmo que não aloque nenhum byte além do tamanho da matriz , acho que você se refere apenas ao armazenamento de elementos, certo? Ainda posso alocar contadores e tal?

Darkhogg 28/03

Ah com certeza. Claro. Você pode alocar algumas estruturas adicionais. Você pode até alocar toda a matriz e fazer muita computação realmente pesada e isso conta como custo zero. A única coisa que você precisa minimizar é o número de SWAP / MOVEs da máquina física real, porque é lenta. O tipo de bolha é o melhor que eu pude, mas achei que deveria haver melhores opções.

MaiaVictor

Eu não acho que exista esse algoritmo. Sem qualquer memória extra, você não terá nenhuma maneira de armazenar qualquer estado do controle.

Raphael

@svrm: sim, então, com RAM ilimitada e a capacidade de copiar a fita para a RAM e fazer cálculos arbitrários gratuitamente, o algoritmo "tente de tudo e aplique o melhor" é ideal em termos de número de movimentos da fita. É improvável que seja prático, mas na prática o tempo de execução seria de bilhões de anos, não 0 ;-) Se o custo de N for copiado uma fita de comprimento N na RAM, a força bruta ingênua pode não ser a ideal, mas está dentro de N de ótimo. Mas nada disso é específico para o seu problema: muitos problemas, quando declarados dessa maneira, poderiam ser resolvidos "offline" usando um algoritmo falso.

21716 Steve Steveop

Respostas:

Considere a classificação de coqueteleira , que é uma versão bidirecional da classificação de bolhas. Você classifica de baixo para alto e depois (esta é a parte adicionada) classifica de alto para baixo, repetindo até terminar. Isso ainda é , mas gera significativamente menos passes em média, porque pequenos elementos próximos à extremidade superior da matriz serão movidos para sua posição final em uma única passagem em vez de N passes. Além disso, você pode acompanhar as posições mais alta e mais baixa em que ocorreu uma troca; passes subsequentes não precisam ser digitalizados além desses pontos. $O(n^2)$

zwol
fonte

O número de trocas de elementos adjacentes necessários para ordenar uma matriz é igual ao número de inversões na matriz. Com n elementos no total, há no máximo n * (n-1) / 2 inversões, portanto, a classificação de bolhas fornece o número assintoticamente ideal de swaps neste modelo.

Charles
fonte

Na verdade, o tipo de bolha fornecerá exatamente o número ideal de swaps. No entanto, para cada permutação, existem várias maneiras de fazer o número ideal de swaps, e não é óbvio qual reduz o número total de movimentos. (Por bubble sort Quero dizer "pegar o maior não-ordenados e movê-lo para o final de ordenado")

Peter Kravchuk

$O(n^2)$

$-\infty$ $+\infty$

O algoritmo que não usa um sinalizador booleano para saber se trocamos algum elemento ou não, é apresentado abaixo (o truque para manter as informações no estado da máquina e não na memória):

Start:
    Do until we are not at the leftmost position (Op 4)
        move left (Op 2b)

Check:
    If we are at rightmost position (Op 3)
        goto Finished:
    If current value is larger than next value (Op 5)
        goto Unfinished:
    move right (Op 2a)
    Repeat Check:

Unfinished:
    If we are at rightmost position (Op 3)
        goto Start:
    If current value is larger than next value (Op 5)
        swap the elements (Op 1) and move right (Op 2a)
    Repeat Unfinished:

Finished:
    The list is sorted now, output it.

A solução de Eric Lippert, o tipo de gnomo, também funciona, porque basicamente é um tipo de bolha bidirecional.

Shreesh
fonte

E a classificação por inserção?

Darkhogg

A classificação de bolha precisa de pelo menos dois contadores de loop que já são mais do que permitidos.

Raphael

Não, você pode ir para a esquerda e direita e, em seguida, da direita para a esquerda, até que não haja alterações (no máximo n vezes) sem usar o contador. Você nem precisa de espaço extra para um sinalizador booleano para observar se há uma alteração. Se houver uma alteração, basta pular para outra sub-rotina que faça o mesmo, exceto que é outra sub-rotina.

Shreesh

E, claro, presumo que você possa ler em branco nas duas extremidades, para que saiba que está no início ou no final da lista. Além disso, suponho que lemos o elemento atual e o próximo para saber se precisamos trocar.

Shreesh 28/03

Ou, se modificarmos o operador swap como "swap se não em ordem crescente".

Shreesh 28/03