O keysort é um método de ordenação no qual ordena-se não o arquivo mantido em memória secundaria, mas sim um array que contém todos os endereços e chaves de acesso do arquivo.
Para isso, passa-se todas as chaves e endereços do arquivo para um array momentâneo. Este array sera passado para uma função que ira ordena-lo. Antes da função, o array esta ordenado pelos endereços, apos a função ele estará ordenado pelas chaves.
Assim, cria-se um novo arquivo cujo endereço de cada chave sera o seu índice no vetor ordenado.
Link para o código > https://repl.it/@lucas_santoli/QueSorte
Custo > O(n²), pois para ler o arquivo o custo é n, para ordenar o array, utiliza-se um quicksort de custo n², e para criar um novo arquivo, o custo também é n, totalizando O(2n+n²) = O(n²).
Como o custo desse algoritmo é diretamente dependente do custo do algoritmo de ordenação auxiliar que será utilizado para organizar os dados (neste caso, o Quick Sort), é possível melhorar o custo do KeySort utilizando um algoritmo de ordenação cujo pior caso tenha uma complexidade mais plausível que a quadrática, como o HeapSort, por exemplo.
ResponderExcluirEsse método de passar os endereços e chaves para um array não funciona muito bem caso o numero de endereços e chaves seja muito grande, e não caiba na memória principal. Uma possível alternativa para esse caso seria usar o external merge sort ou external distribution sort, que são sinónimos do merge sort e quick sort respectivamente.
ResponderExcluirMelhoria do método:
ResponderExcluir- Em vez de escrever um novo arquivo ordenado, escreve-se a lista de
chaves ordenadas a lista de chaves e respectivos RRNs dos registros
acaba se tornando um índice para os registros do arquivo.
- Deste modo, a pesquisa por um registro em particular pode ser feita por
pesquisa binária, na memória RAM (o índice cabe na memória).