Na pior das hipóteses,

$O(n \ln n)$

Apenas um lembrete, no local significa que ele usa a matriz transmitida e o algoritmo de classificação só pode usar espaço extra constante. Estável significa que os elementos com a mesma chave aparecem na mesma ordem na matriz classificada como no original.

$O(n \ln n)$ $O(n)$ $O(n^2)$ $O(n \ln n)$ $O(n \ln n)$

$O(n \ln n)$ $\frac{1}{4}$ $\frac{1}{2}$ $\frac{1}{4}$

Eu também estaria muito interessado no pior caso no lugar quicksort estável. Pelo que entendi, modificar quicksort para o pior caso requer a seleção de um pivô adequado que destruiria a estabilidade que normalmente seria desfrutada. $O(n \ln n)$ $O(n \ln n)$

Isso é puramente de interesse teórico e não tenho aplicação prática. Gostaria apenas de conhecer o algoritmo que possui todos esses três recursos.

algorithms reference-request sorting in-place user834
fonte

Há uma pergunta semelhante no SO aqui, com uma resposta que fornece a referência que forneci na pergunta. Acredito que essa não seja uma pergunta duplicada, pois estou pedindo esclarecimentos adicionais, mais literatura e, com alguma sorte, uma descrição do algoritmo.

User834

Veja esta pergunta em math.stackexchange.com.

Tsuyoshi Ito

Por que a maneira diferente de selecionar um pivô no QuickSort destrói sua estabilidade?

svick

O (n \ln n)

$O(n \ln n)$

@TsuyoshiIto, considere fazer disso uma resposta. Além disso, se você pudesse fazer um breve esboço do algoritmo, acho que também seria realmente útil.

User834

Respostas:

Existem vários algoritmos que são todos acima, e praticamente todos eles foram inventados nos últimos 30 anos.

Provavelmente, a mais agradável é a classe de algoritmos chamada de classificação em bloco , incluindo a versão (chamada WikiSort) de Kim e Kutzner em 2008. Não é apenas uma memória estável e completamente in loco (O (1) sobrecarga de memória no modelo transdicotômico); também é adaptável e, portanto, executará menos etapas para classificar listas quase classificadas, convergindo para comparações de O (n) no caso de uma lista já classificada. Você pode encontrar uma implementação em C, C ++ e Java aqui: https://github.com/BonzaiThePenguin/WikiSort

Também é interessante o algoritmo GrailSort (também uma classificação em bloco) de Huang e Langston (1989-1992), que realmente supera o WikiSort em vários tipos de casos de teste. Uma implementação C ++ está disponível aqui: https://github.com/Mrrl/GrailSort

quintopia
fonte

Você pode escrever um mergesort estável no local. Veja isto para detalhes. Nas próprias palavras do autor:

Um belo algoritmo de mesclagem no local. Teste-o em matrizes invertidas para entender como as rotações funcionam. Classificação mais rápida no local estável. Não há risco de explodir uma pilha. Custo: um número relativamente alto de movimentos. A pilha ainda pode ser cara também. Essa é uma classificação de mesclagem com uma mesclagem inteligente no local que 'gira' as sub-matrizes. Este código é copiado literalmente da biblioteca stl C ++ e traduzido em Java.

Não copio o código aqui, mas você pode encontrá-lo no link ou verificando o C ++ STL. Informe-me se você gostaria que eu tentasse fornecer uma descrição mais detalhada do que está acontecendo aqui.

Patrick87
fonte

O (\ln n)

$O(\ln n)$

O (1)

$O(1)$

O (\ln n)

$O(\ln n)$

Knuth também aborda isso no TAoCP.

Raphael

O (n \ln^{2} n)

$O(n\ln^2n)$

Por favor, tome isso como um longo comentário sobre alguns pensamentos práticos. Embora essa não seja uma resposta para sua pergunta, acho que você pode estar interessado nesta discussão em Python:

$\lg(N!)$ $N-1$

[...]

Mesclar séries adjacentes de comprimentos A e B no local é muito difícil . Sabe-se que construções teóricas podem fazê-lo, mas são muito difíceis e lentas para uso prático . Mas se tivermos uma memória temporária igual a min (A, B), é fácil.

Fonte: bugs.python.org , autor: Tim Peters

$\mathcal{O}(n \log n)$

Observe também que o Timsort tem bom desempenho em matrizes já classificadas.

Então, o Python usa o Timsort (que é o Mergesort com alguns ajustes) e, como eu observei a implementação do Java há alguns anos, também foi o Mergesort (acho que agora eles também usam o Timsort).

Martin Thoma
fonte