escrever matriz de cadeias consecutivas não classificada ordenada em um arquivo de forma eficiente - c, matrizes, algoritmo, desempenho, classificação

Eu tenho uma matriz de strings contendo números consecutivos não ordenados (intervalo de 0 a n), e. [7a, 1b, 2c, 0d, 6e, 5f, 3g, 4h], e eu quero escrever os números em ordem em um arquivo.

Após o exemplo:

0d
1b
2c
3g
4h
5f
6e
7a

A string não é do mesmo tamanho.

Eu estava tentando encontrar uma maneira de fazer isso rápido esem ocupar muito espaço. Eu encontrei uma maneira que eu posso fazer em O (n) complexidade de espaço e O (n) desempenho: Eu crio um array com n células e insiro cada string para o seu número de célula.

for (i = 0; i < n; i++)
sortedArray[originalArray[i]] = originalArray[i]

... algo parecido (criando uma nova matriz no tamanho da original e preenchendo-a em uma execução) e, em seguida, com outro loop para gravar o conteúdo da matriz classificada no arquivo.

Mas estou procurando uma maneira melhor de fazer isso.

Respostas:

Supondo que os números principais em seuAs strings são de fato consecutivas e não repetitivas, você não atingirá uma complexidade de tempo melhor do que a que você faria com a abordagem descrita na pergunta, ou algo ao longo dessas linhas. Requer espaço de trabalho proporcional ao número de strings.

Em comparação,

• uma ordenação de mesclagem padrão também requer espaço de trabalho proporcional ao número de strings (mas você pode se safar com metade da abordagem da pergunta, se tiver "cuidado") e O(n log n) complexidade do tempo. Alternativamente,
• tipo rápido classifica no local e tem O(n log n) complexidade do tempo em média; se você implementá-lo com cuidado, então requer apenas O(log n) espaço de trabalho no pior dos casos - uma quantidade constante por quadro de pilha na versão recursiva, ou uma pilha que acomoda muitos elementos em uma não recursiva.
• uma classificação de mesclagem no local requer O(log n) espaço de trabalho (e não requer tanto cuidado para conseguir isso quanto o tipo rápido), e tem O(n^2) complexidade do tempo em média. Tende a bater a maioria dos outros O(n^2) se aproxima bastante, na maioria das vezes.
• tipo de inserção classifica no local e exige O(1) espaço de trabalho, mas tem O(n^2) complexidade do tempo. É bem compreendido, fácil de implementar e muito rápido na prática para pequenos tamanhos de entrada.

Existem muitas outras alternativas, mas eu achoesses são razoavelmente representativos de suas opções. Qual deles atende melhor às suas necessidades depende dos limites do tamanho do seu problema e de como você pesa o espaço versus a velocidade. Se o tamanho do problema puder ser muito grande e você não puder pagar O(n) espaço sobrecarga, em seguida, dar rápido classificar cuidadoconsideração. Se o tamanho do problema for pequeno, mas a conservação do espaço for extremamente importante, considere a classificação por inserção. Se a alta velocidade é importante e você pode arcar com o custo do espaço, sua abordagem original é muito atraente.