sábado, 5 de outubro de 2013

Counting Sort

Normalmente estamos acostumados com algoritmos de ordenação como o MergeSort e QuickSort que funcionam em tempo de execução da ordem de O( lg(n) ) ou até mesmo outros como BubbleSort, Insertion Sort ou Selection Sort, que chegam a tempos de ordenação da ordem de O( n² ). Estes algoritmos são normalmente ensinados nos cursos de graduação. Daí acostumamos com tempos de ordenação grandes e esquecemos que existem algumas situações onde conseguimos tempos de ordenação da ordem de O( n ).

O Counting Sort é utilizado para ordenar vetores de tipos inteiros onde os valores contidos no vetor estão em um intervalo [min, max].  Para ser executado, faz uso de 2 arrays auxiliares, mas com isto consegue um bom tempo de ordenação.

Vamos ver um vídeo com a demonstração deste tipo de ordenação: