que tipo de algoritmo vc usaria pra ordenar um vetor de BILHOES de inteiros???

hitler
(usa openSUSE)

Enviado em 09/11/2017 - 23:27h

eu usava selection sort pra fazer a ordenacao de pequenos vetores, mas oq vcs usariam pra ordenar centenas ou ate mesmo milhares de bilhoes de inteiros no menor espaco de tempo?

phoemur
(usa Debian)

Enviado em 11/11/2017 - 22:21h

https://www.quora.com/What-is-the-most-efficient-way-to-sort-a-million-32-bit-integers

paulo1205
(usa Ubuntu)

Enviado em 13/11/2017 - 05:41h

Muitas vezes a seleção do algoritmo de ordenação depende das condições de contorno. Você tem restrições de armazenamento? De tempo de tempo de acesso aos dados (e.g. ordenar em disco é mais lento que ordenar em memória)? De tempo total de execução? Precisa de ordenação estável? Recursividade é possível? Está trabalhando com arrays ou com listas (no seu caso, já que você falou em vetor, são arrays)? É mais importante que a execução seja executada o mais rapidamente possível (algoritmos adaptativos) ou ela deve se manter constante? Permite execução paralela de partes do algoritmo?

O algoritmo mostrado pelo phoemur é muito interessante, especialmente para mim, que não o conhecia. Pelo lado positivo não usa comparações entre os valores a serem ordenados, o que elimina o limite mínimo de execução de O(n·log n), é estável e não recorre a recursividade. Por outro lado, ele introduz um segundo nível de indireção (array de ponteiros, o que dá na mesma que ponteiros para ponteiros) dentro de um laço de repetição, usa três arrays além do array original a ser ordenado (um array de saída de cada iteração, com o mesmo tamanho do array a ser ordenado (que é a principal fraqueza do Merge Sort), um para a quantidade de baldes, e o outro para apontar em qual local do array de saída começa cada balde), e ainda coloca dois desses arrays na pilha.

O último problema é fácil de resolver, trocando . A dupla indireção, só se se aumentasse o consumo de memória, passando de O(n) para algo próximo de O(n²), o que seria um absurdo total.

Seu problema menciona centenas de bilhões de inteiros. Para centenas de bilhões de inteiros, você teria de ter memória da ordem casa de terabyte ou mais, seja ela em RAM ou em disco. Pense com cuidado.