Adicionando elementos a uma matriz classificada

Qual seria a maneira mais rápida de fazer isso (de uma perspectiva algorítmica, bem como de uma questão prática)?

Eu estava pensando algo ao longo das seguintes linhas.

Eu poderia adicionar no final de uma matriz e, em seguida, usar o bubblesort, pois ele tem um melhor caso (array totalmente classificado no início) que está próximo disso e tem tempo de execução linear (no melhor caso).

Por outro lado, se eu souber que começo com uma matriz classificada, posso usar uma pesquisa binária para descobrir o ponto de inserção de um determinado elemento.

Meu palpite é que o segundo caminho é quase ideal, mas curioso para ver o que está por aí.

Como isso pode ser feito da melhor maneira?

Contamos o número de leituras e gravações de elementos da matriz. Para fazer a classificação por bolhas, você precisa de acessos (a gravação inicial até o fim e, no pior dos casos, duas leituras e duas gravações para fazer trocas). Para fazer a pesquisa binária, precisamos de ( para pesquisa binária e, na pior das hipóteses, para deslocar os elementos da matriz para a direita e, em seguida, 1 para escrever o elemento da matriz em sua posição correta).n 2 log n + 2 n + 1 2 log n 2 $1 + 4n$$n$$2\log n + 2n + 1$$2\log n$$2n$

Portanto, ambos os métodos têm a mesma complexidade para implementações de array, mas o método de pesquisa binária requer menos acessos a array a longo prazo ... assintoticamente, metade do mesmo. Existem outros fatores em jogo, naturalmente.

Na verdade, você poderia usar implementações melhores e contar apenas os acessos reais da matriz (não os acessos ao elemento a ser inserido). Você pode fazer para classificação de bolhas e para pesquisa binária ... portanto, se o acesso ao registro / cache for barato e o acesso à matriz for caro, pesquisando a partir do final e mudando ao longo do caminho (bolha mais inteligente tipo para inserção) poderia ser melhor, embora não assintoticamente.log n + 2 n + $2n + 1$$\log n + 2n + 1$

Uma solução melhor pode envolver o uso de uma estrutura de dados diferente. As matrizes fornecem acessos O (1) (acesso aleatório), mas as inserções e exclusões podem custar. Uma tabela de hash poderia ter O (1) inserções e exclusões, os acessos custariam. Outras opções incluem BSTs e pilhas, etc. Pode valer a pena considerar as necessidades de uso do seu aplicativo para inserção, exclusão e acesso e escolher uma estrutura mais especializada.

Observe também que se você deseja adicionar elementos a uma matriz classificada de elementos, uma boa idéia pode ser classificar eficientemente os itens e mesclar as duas matrizes; Além disso, matrizes classificadas podem ser construídas eficientemente usando, por exemplo, pilhas (classificação de pilha).n $m$$n$$m$

Se você tiver algum motivo para não usar o heap, considere usar a Classificação de inserção em vez de Classificação de bolha. É melhor quando você tem alguns elementos não classificados.

Como você está usando uma matriz, custa para inserir um item - quando você adiciona algo ao meio de uma matriz, por exemplo, é necessário mudar todos os elementos depois dele por um para que a matriz permaneça classificada .$O(n)$

A maneira mais rápida de descobrir onde colocar o item é como você mencionou, uma pesquisa binária, que é , portanto a complexidade total será , que está no ordem de .O ( n + lg n ) O ( n $O(\lg n)$$O(n + \lg n)$$O(n)$

Dito isto, se eu me senti particularmente irritado, eu poderia argumentar que você pode "adicionar a uma matriz classificada" em , simplesmente dando um tapa no final da matriz, pois a descrição não indica que a matriz deve permanecer classificado após a inserção do novo elemento.$O(1)$

De qualquer forma, não vejo nenhuma razão para separar as bolhas desse problema.

Patrick87 explicou tudo isso muito bem. Mas uma otimização adicional que você poderia fazer seria usar algo como um buffer circular: você pode mover itens à direita da posição do elemento inserido para a direita, como de costume. Mas você também pode mover itens para a esquerda da posição correta para a esquerda. Para fazer isso, você precisa tratar a matriz como circular, ou seja, o último item é anterior ao primeiro e também exige que você mantenha o índice onde os itens são iniciados atualmente.

Se você fizer isso, pode significar que você faz cerca da metade do acesso à matriz (assumindo uma distribuição uniforme dos índices nos quais você insere). No caso de fazer uma pesquisa binária para encontrar a posição, é trivial escolher se desloca para a esquerda ou para a direita. No caso de classificação por bolha, você precisa "adivinhar" corretamente antes de iniciar. Mas fazer isso é simples: basta comparar o item inserido com a mediana da matriz, o que pode ser feito no acesso a uma única matriz.

Eu usei o algoritmo de classificação de inserção efetivamente para esse problema. Ao mesmo tempo, tivemos um problema de desempenho com um objeto de tabela de hash, escrevi um novo objeto que usava a pesquisa binária em vez de aumentar significativamente o desempenho. Para manter a lista classificada, ele acompanharia o número de itens adicionados desde a última classificação (ou seja, número de itens não classificados), quando a lista precisava ser classificada devido a uma solicitação de pesquisa, ele executou uma classificação por inserção ou uma classificação rápida, dependendo na porcentagem de itens não classificados. O uso da classificação por inserção foi fundamental para melhorar o desempenho.