Classifique uma matriz de

8

Estou tentando entender como posso classificar uma matriz de n elementos quando apenas logn não estão no lugar.

Ouvi dizer que classificar uma matriz com no máximo I inversões tem complexidade O(nregistro(Eu/n)). Porque eles sãoregistron elementos que não são classificados, no meu caso existem no máximo nregistron inversão.

A resposta para a pergunta é O(nregistroregistron) que é consistente com a fórmula, mas não consigo entender a "ideia por trás dela ou qual algoritmo de classificação a alcança.

user64264
fonte

Respostas:

9

Assumindo que "k elementos fora do lugar "significa que existem k elementos cuja exclusão deixa o resto da matriz classificada, há um O(n+kregistrok)algoritmo de tempo para classificar toda a matriz.

Em poucas palavras, calcule uma subsequência crescente de comprimento pelo menos n-2k, classifique os outros e mescle. O primeiro pode ser realizado a tempoO(n)por um algoritmo simples de pilha que empurra elementos um de cada vez e exibe os dois primeiros sempre que estão fora de ordem. A estratégia de exclusão ideal deve excluir pelo menos um desses elementos, para que o dano total seja ultrapassado por2k exclusões.

David Eisenstat
fonte
+1 para a idéia interessante. Apenas uma coisa (e provavelmente estou dividindo os cabelos aqui), você pode realmente fazer inserções em locais arbitrários, evitando aO(n)"todo mundo muda certo por favor" custa? Acredito que devemos acompanhar as inserções em uma estrutura separada, fazendo um passe final no final para produzir a matriz classificada.
quicksort
@quicksort melhor para apenas uma espécie as sucatas e methinks de mesclagem
David Eisenstat
1
É a mesma coisa, mas a fusão é mais limpa, eu concordo.
quicksort
1
Digno de menção é que isso é assintoticamente ideal (usando comparações) na dependência de n e k.
aelguindy 07/01
Bem, o algoritmo que você descreveu parece ser do tipo drop-merge .
Morwenn
5

Digamos que existem k elementos não no local.

Divida a matriz em sub-matrizes não decrescentes. Isso pode ser feito emΘ(n) tempo e resultará em no máximo 2ksubarrays. Agora nós apenas os juntamos em paresΘ(nregistrok) tempo, produzindo uma matriz classificada.

ordenação rápida
fonte