iSorting: Um estudo sobre otimização em algoritmos de ordenação
Marcelo Josué Telles 1
Paulo Henrique Santini 1
Sandro José Rigo 1
José Vicente Canto dos Santos 1
Jorge Luis Victória Barbosa 1
Resumo: A ordenação de elementos é importante em situações de geração de índices em tabelas
de banco de dados, modelagem de sistemas inteligentes, aprendizagem de máquina, classificação
de elementos, identificação de padrões, além das situações clássicas presentes no tratamento de estruturas de dados. Na literatura atual existem diferentes algoritmos que atendem esta tarefa, alguns
são mais eficientes de acordo com as características dos elementos. Visando otimizar a tarefa de
ordenação independente do algoritmo, este artigo apresenta um estudo comparativo e propõe tarefas de pré-processamento, a fim de reduzir o tempo para ordenação. O pré-processamento proposto
consiste em gerar segmentos por intervalos fazendo com que cada um tenha elementos semelhantes.
É apresentada a técnica de pré-processamento e um comparativo entre os algoritmos de ordenação. Os resultados observados mostram que é possível reduzir o tempo necessário para a ordenação
adotando-se a técnica de pré-processamento.
Palavras-chave:
Dados.
Complexidade de Algoritmos, Algoritmos de Ordenação, Pré-processamento de
Abstract:
The ordering of elements is important in situations generation indexes in database
tables, modeling intelligent systems, machine learning, classification of elements, patterns identification, beyond the classical situations present in data structures. In the current literature, there are
various algorithms that meet this task, some are more efficient in accordance with the characteristics
of the elements. To optimize the independent ordering task of the algorithm, this paper presents a
comparative study and proposed pre-processing tasks in order to reduce the time for sorting. The
proposed preprocessing is to generate segments at intervals making each has similar elements. Preprocessing technique and a comparison between the sorting algorithms is displayed. Our results
show that it is possible to reduce the time required for sorting by adopting the pre-processing technique.
Keywords: Comparative, complexity of algorithms, preprocessing.
1
Introdução
Na literatura [1] existem diversos algoritmos de ordenação, assim como comparativos [2], [3] e [4], os
quais indicam que dependendo das características dos elementos a serem ordenados, existe um algoritmo mais
adequado. Os comparativos ainda apresentam mais detalhes, tais como, o custo de processamento, questões de
implementação e compreensão lógica do algoritmo. Em algumas situações não é possível identificar o algoritmo
mais adequado, ou não é possível modificar o algoritmo que é utilizado.
Este artigo apresenta uma análise dos principais algoritmos de ordenação e um estudo sobre os efeitos
originados de tarefas de pré-processamento, de modo a avaliar o quanto é possível otimizar a tarefa de ordenação
com atividades adicionais preliminares, independente do algoritmo a ser utilizado. A otimização consiste em
reduzir o número de operações de troca de elementos e consequentemente o tempo necessário para ordenação.
1 Programa
Interdisciplinar de Pós-Graduação em Computação Aplicada (PIPCA), UNISINOS - São Leopoldo (RS) - Brasil
{rigo,jvcanto,[email protected]} {marcelojtelles,[email protected]}
http://dx.doi.org/10.5335/rbca.2015.XXX
Revista Brasileira de Computação Aplicada(ISSN 2176-6649), Passo Fundo, v. 7, n. 1, p. xx-xx, abr. 2015
1
Existem características nos algoritmos de ordenação, que são indicadas em determinadas situações. Desta
forma, a correta identificação do algoritmo mais adequado para cada situação é uma tarefa importante, pois permite
realizar a ordenação utilizando menos processamento.
Identificar o melhor algoritmo para cada caso torna-se um desafio na área de complexidade de algoritmos,
pois isso implica em conhecer os elementos a serem ordenados. Como este conhecimento prévio nem sempre é
possível, a alternativa de pré-processamento se torna bastante viável. Para verificar o impacto desta alternativa em
cada algoritmo, são realizados testes comparativos entre os mesmos.
Uma das limitações dos trabalhos analisados [5] é a implementação do processo de paralelismo para melhorar somente o algoritmo Merge Sort, a fim de disponibilizar uma solução objetiva para a redução do tempo de
execução do mesmo. O paralelismo pode ser adequado para Merge Sort, porém, o mesmo não se enquadra para os
demais algoritmos de ordenação.
A abordagem proposta consiste em aplicar uma técnica de pré-processamento, a qual é capaz de reduzir
as operações necessárias para realizar a ordenação. Para ilustrar o impacto da tarefa de pré-processamento são
apresentados gráficos comparativos, que apresentam as diferenças entre os tempos necessários para realizar a
ordenação.
Este artigo está organizado da seguinte forma. Seção II contém uma breve descrição sobre os conceitos,
entre eles: tipos de algoritmos de ordenação presentes na literatura, custo dos algoritmos, melhor caso e pior caso.
A seção III é dedicada a técnica de pré-processamento, incluindo metodologia e implementação nos algoritmos
de ordenação. A seção IV apresenta os testes e resultados obtidos com a técnica proposta. Finalmente, a seção V
apresenta as considerações finais e possíveis trabalhos futuros.
2
Revisão da Literatura
A principal diferença entre os algoritmos de ordenação é a recursividade e forma como os elementos são
segmentados o que pode reduzir significativamente [6] a quantidade de trocas necessárias para ordenação dos elementos [7]. Os algoritmos de ordenação clássicos encontrados na literatura são: Método de Ordenação pela Bolha
(Bubble Sort), Método de Ordenação por Seleção (Selection Sort), Método de Ordenação por Inserção (Insertion
Sort), Método de Ordenação Rápido (Quick Sort), Método de Ordenação por Fusão (Merge Sort), Método de Ordenação pela Raiz (Radix Sort), Método de Ordenação proposto pelo matemático e cientista da computação Donald
L. Shell (Shell Sort) e Método de Ordenação pelo “Monte” (Heap Sort). Não foi considerado o método Cocktail
Sort (ou Shaker Sort) que funciona como Bubble Sort bidirecional. Quanto ao método Counting Sort é apresentado
sua complexidade, mas não foi analisado, pois se destina apenas à ordenação de inteiros. Já os métodos Bogo Sort
e Bucket Sort não foram analisados neste artigo, pois o algoritmo Bogo Sort é um método de ordenação apenas
para fins didáticos, sendo pouco utilizado na prática. Enquanto que o método Bucket Sort utiliza a segmentação
dos elementos por arrays (definidos como Buckets) e aplica-se a ordenação apenas de números inteiros.
Antes da apresentação dos algoritmos é descrita a estrutura na qual os dados são armazenados para ordenação, pois nos algoritmos de ordenação tal estrutura é manipulada. A ordenação deve deslocar os elementos de
posição, não apenas ordenar os índices dos mesmos. Os elementos a serem ordenados estão organizados em uma
estrutura de dados definidos em uma classe codificada na linguagem Java, denominada “Arquiva”. A estrutura tem
um número inteiro (valor) e duas palavras (letra e nomeArquivo). O número será utilizado para ordenação, a letra
é apenas para contemplar uma informação extra, enquanto que “nomeArquivo” representa o nome do arquivo no
qual se encontram as duas informações anteriores. Na listagem 1 é apresentada a classe “Arquiva”:
Listagem 1: Classe para os Dados
1
2
3
4
5
6
7
8
9
/**
*
* Comentário: Classe responsável por tratar os arquivos com os elementos a serem ordenados.
*
*/
public class Arquiva {
String letra;
int valor;
String nomeArquivo;
Revista Brasileira de Computação Aplicada(ISSN 2176-6649), Passo Fundo, v. 7, n. 1, p. xx-xx, abr. 2015
2
10
public Arquiva(){
this.letra = null;
this.valor = 0;
this.nomeArquivo = null;
}
...
11
12
13
14
15
16
17
}
Os elementos a serem ordenados serão alocados em um array do tipo “Arquiva”. Os métodos tradicionais
de busca e alteração de valores (get, set) foram suprimidos na listagem anterior, mas foram implementados.
2.1
Algoritmos de ordenação
No método de Ordenação pela Bolha (Bubble Sort) [1], é realizada uma primeira interação, onde o atributo
valor é comparado dois a dois. Caso o primeiro seja maior do que o segundo a troca é feita e isso é repetido
sucessivamente até os dois últimos elementos. Na próxima interação o último elemento não é analisado, já que o
maior elemento já está na posição correta. Na listagem 2 segue a implementação deste método:
Listagem 2: Ordenação pela Bolha
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
*
* Bubble Sort
* Ordenação pela Bolha
* Comentário: Código responsável por fazer a ordenação utilizando o conceito da bolha (Bubble Sort ) , este faz uma
* intera ção entre todos os elementos , sendo que a segunda intera ção é apenas do primeiro até o penúltimo , a terceira
* é do primeiro até antepenúltimo . Cada interação faz a comparação de dois elementos , se o elemento da posição i for
* maior que o elemento da posição seguinte , é feita a troca da posição dos elementos .
*
*/
for (int a = 0; a < quantos - 1; a++) {
for (int i = 0; i < (quantos - 1) - a; i++) {
if(arquiva[i].getValor() > arquiva[i+1].getValor()){
temp.setNomeArquivo(arquiva[i+1].getNomeArquivo());
temp.setValor(arquiva[i+1].getValor());
temp.setLetra(arquiva[i+1].getLetra());
arquiva[i+1].setNomeArquivo(arquiva[i].getNomeArquivo());
arquiva[i+1].setValor(arquiva[i].getValor());
arquiva[i+1].setLetra(arquiva[i].getLetra());
arquiva[i].setNomeArquivo(temp.getNomeArquivo());
arquiva[i].setValor(temp.getValor());
arquiva[i].setLetra(temp.getLetra());
}
}
}
Na implementação apresentada é possível identificar que cada troca de posição implica na modificação da
posição dos três atributos da classe “Arquiva”.
No método de Ordenação por Seleção (Selection Sort) [8], é feita a comparação entre o primeiro elemento
e todos demais elementos do conjunto, a fim de encontrar um elemento menor do que o primeiro. Caso seja
encontrado é feita a troca de posição dos elementos. Na sequência o segundo elemento é comparado com os
demais e assim sucessivamente. Na listagem 3 segue o algoritmo:
Listagem 3: Ordenação por Seleção
1
2
3
4
5
6
/**
*
* Selection Sort
* Ordenação por Seleção
* Comentário: O método de ordenação por sele ção percorre os elementos de uma forma semelhante com o método da bolha,
* no entanto as trocas são realizadas em uma quantidade bem inferior .
Revista Brasileira de Computação Aplicada(ISSN 2176-6649), Passo Fundo, v. 7, n. 1, p. xx-xx, abr. 2015
3
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
*
*/
for (int i = 0; i < arquiva.length - 1; i++) {
indiceMenor = i;
for (int j = i + 1; j < arquiva.length; j++) {
if (arquiva[j].getValor() < arquiva[indiceMenor].getValor()) {
indiceMenor = j;
}
}
if (indiceMenor != i) {
temp.setValor(arquiva[indiceMenor].getValor());
temp.setNomeArquivo(arquiva[indiceMenor].getNomeArquivo());
temp.setLetra(arquiva[indiceMenor].getLetra());
arquiva[indiceMenor].setValor(arquiva[i].getValor());
arquiva[indiceMenor].setNomeArquivo(arquiva[i].getNomeArquivo());
arquiva[indiceMenor].setLetra(arquiva[i].getLetra());
arquiva[i].setValor(temp.getValor());
arquiva[i].setNomeArquivo(temp.getNomeArquivo());
arquiva[i].setLetra(temp.getLetra());
}
}
Para conjuntos com muitos elementos este algoritmo executa muitas operações, pois o conjunto é lido da
posição corrente até o final todas as vezes. Note que além de comparar todos elementos, ainda existe mais uma
comparação que é feita no final (linha 16) para identificar se deve ser realizada a troca. A vantagem do método
Selection Sort é que as trocas são feitas apenas para as posições corretas dos elementos, diferente do método Bubble
Sort.
No método de Ordenação por Inserção (Insertion Sort) [9], é dado que o conjunto está ordenado até uma
determinada posição (i). A cada interação é verificado se o elemento atual (j) é menor que o elemento anterior
(j-1), caso afirmativo a troca é feita. Na listagem 4 segue o algoritmo:
Listagem 4: Ordenação por Inserção
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
*
* Insertion Sort
* Ordenação por Inserção
* Comentário: O método de inser ção percorre todos os elementos fazendo os testes para com o primeiro e
* segundo elemento, inserindo o elemento maior em uma posição mais a frente .
*
*/
int i;
for (int j = 1; j < arquiva.length; j++) {
temp.setValor(arquiva[j].getValor());
temp.setNomeArquivo(arquiva[j].getNomeArquivo());
temp.setLetra(arquiva[j].getLetra());
i = j - 1;
while (i >= 0 && arquiva[i].getValor() > temp.getValor()) {
arquiva[i + 1].setValor(arquiva[i].getValor());
arquiva[i + 1].setNomeArquivo(arquiva[i].getNomeArquivo());
arquiva[i + 1].setLetra(arquiva[i].getLetra());
i = i - 1;
}
arquiva[i + 1].setValor(temp.getValor());
arquiva[i + 1].setNomeArquivo(temp.getNomeArquivo());
arquiva[i + 1].setLetra(temp.getLetra());
}
Para conjuntos com elementos praticamente ordenados este método se mostra bastante eficiente. Sua principal utilização é em conjuntos com poucos elementos. Uma desvantagem é quando os elementos a serem ordenados,
encontram-se na forma inversa, uma vez que resulta um grande número de trocas.
Revista Brasileira de Computação Aplicada(ISSN 2176-6649), Passo Fundo, v. 7, n. 1, p. xx-xx, abr. 2015
4
No método de Ordenação por Fusão (Merge Sort) [8], os elementos a serem ordenados são separados em
dois conjuntos de forma que a ordenação é feita separadamente em cada um destes, por fim é feita a leitura de
um valor de cada conjunto a fim de identificar qual elemento deve ser colocado no conjunto resultante, de forma
a ficar ordenado. Neste método é necessário armazenar a última posição de cada conjunto, pois é possível que
um conjunto tenha sido todo copiado para o conjunto final, necessitando apenas copiar os elementos do outro
conjunto. A listagem 5 a implementação que chama as ordenações (linhas 15 e 16) dos elementos e fusão (linha
17) dos conjuntos:
Listagem 5: Ordenação por Fusão
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
*
* Merge Sort
* Ordenação por Fusão
* Comentário: O algoritmo a seguir divide o conjunto com os elementos em dois . Cada conjunto é ordenado com a chamada
* do método sortToMerge, linhas 15 e 16. Este método é chamado recursivamente até que todo conjunto seja dividido em
* segmentos ordenados. Por fim os segmentos são unificados pelo método merge. O método merge tem por finalidade realizar
* a comparação entre os 2 segmentos gerados e identificar o elemento e ser lido a fim de deixar o vetor resultante
* ordenado.
*
*/
public static Arquiva[] sortToMerge(Arquiva[] vetor, int inicio, int fim) {
if (inicio < fim) {
int meio=(inicio+fim)/2;
sortToMerge(vetor, inicio, meio);
sortToMerge(vetor, meio+1, fim);
merge(vetor, inicio, meio, fim);
}
return vetor;
}
Este método de ordenação utiliza recursividade para ordenação dos elementos, este recurso evita que o
conjunto seja lido até o final, fazendo menos trocas dos elementos. Outra vantagem deste método é que ele divide
o problema em dois, fazendo com que o número de operações seja menor. Sua principal desvantagem é a utilização
de memória para alocar o conjunto resultante.
No método de Ordenação Rápida (Quick Sort) [8], um elemento é escolhido como pivô, em seguida todos
elementos antes do pivô devem ser menores que pivô e todos elementos depois devem ser maiores, isso é feito de
forma recursiva, isto é, para cada parte do conjunto esta divisão é feita sucessivamente. Na listagem 6 segue a parte
principal deste método de ordenação:
Listagem 6: Ordenação Rápida
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
*
* Quick Sort
* Ordenação Rápida
* Comentário: O algoritmo percorre o conjunto iniciando pelos elementos posicionados na primeira e última posição
* do conjunto (2 laços intermedi ários ) . Tanto o elemento da primeira posição quanto o da última são comparados com o
* elemento central do conjunto . A troca de elementos é feita apenas depois de uma comparação. Nos dois testes lógicos
* tem−se a chamada recursiva para o método.
*
*/
private static Arquiva[] quick(Arquiva[] array, int indiceMenor, int indiceMaior) {
int i = indiceMenor;
int j = indiceMaior;
int pivo = array[indiceMenor+(indiceMaior-indiceMenor)/2].getValor();
while (i <= j) {
while (array[i].getValor() < pivo) {
i++;
}
while (array[j].getValor() > pivo) {
j--;
}
if (i <= j) {
Revista Brasileira de Computação Aplicada(ISSN 2176-6649), Passo Fundo, v. 7, n. 1, p. xx-xx, abr. 2015
5
array=trocaValores(array, i, j);
i++;
j--;
23
24
25
}
}
if (indiceMenor < j)
quick(array, indiceMenor, j);
if (i < indiceMaior)
quick(array, i, indiceMaior);
return array;
26
27
28
29
30
31
32
33
}
Na implementação do método Quick Sort a escolha do pivô tem bastante impacto no seu número de operações. A escolha do pivô pode ser fixa ou aleatória, no caso apresentado, foi fixa, o pivô é sempre o elemento da
posição do meio do array. A expectativa é que este valor não seja o maior do conjunto nem o menor. Na linha 20 o
método chama a rotina “trocaValores” que é responsável por trocar os elementos de posição, sendo que o elemento
da posição (i) vai para posição (j) e o elemento da posição (j) vai para posição (i). Este método de ordenação é
amplamente utilizado na prática.
No método de Ordenação pela Raiz (Radix Sort) [8] os elementos são comparados por partes, isto é, cada
elemento é ordenado baseando-se em uma parte do seu valor, isso é feito com o dígito menos significativo (para
elementos com mesma quantidade de dígitos). Com esta primeira análise é feita a alocação dos elementos com o
dígito menos significativo igual a 0 (zero) antes dos elementos com dígito menos significativo igual a 1 (um). O
passo seguinte consiste em ler o próximo dígito dos elementos e repetir o processo. Este algoritmo de ordenação
também utiliza o conceito de ordenação por contagem, desta forma é necessário espaço em memória para que os
elementos sejam alocados temporariamente. Mesmo se tratando de análise dos dígitos este método de ordenação
pode ser utilizado para ordenação de palavras, basta converter os caracteres das palavras por valores numéricos,
usando, por exemplo, o código ASCII. Na listagem 7 segue a implementação Radix Sort.
Listagem 7: Ordenação pela Raiz
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
*
* Radix Sort
* Ordenação pela Raiz
* Comentário: O algoritmo analisa cada dí gito de cada elemento do conjunto . Na linha 17 é realizado o teste
* para verificar se o dí gito de cada possí vel posição de um inteiro de 32 bits é um valor negativo . Tais valores
* são alocados em um conjunto temporário . No final este conjunto é preenchido com os demais valores ( linha 30) .
* Por fim ( linha 37) os valores são armazenados no array original .
*
*/
for (int desloca = Integer.SIZE - 1; desloca > -1; desloca--) {
Arquiva[] temp;
temp = new Arquiva[tam];
int j = 0;
for (int i = 0; i < tam; i++) {
boolean mover = original[i].getValor() << desloca >= 0;
if (desloca == 0 ? !mover : mover) {
temp[j] = new Arquiva();
temp[j].setValor(original[i].getValor());
temp[j].setNomeArquivo(original[i].getNomeArquivo());
temp[j].setLetra(original[i].getLetra());
j++;
} else {
original[i - j].setValor(original[i].getValor());
original[i - j].setNomeArquivo(original[i].getNomeArquivo());
original[i - j].setLetra(original[i].getLetra());
}
}
29
30
31
32
33
for (int i = j; i < temp.length; i++) {
temp[i]=new Arquiva();
temp[i].setValor(original[i - j].getValor());
temp[i].setNomeArquivo(original[i - j].getNomeArquivo());
Revista Brasileira de Computação Aplicada(ISSN 2176-6649), Passo Fundo, v. 7, n. 1, p. xx-xx, abr. 2015
6
temp[i].setLetra(original[i - j].getLetra());
34
}
35
36
for (int i = 0; i < tam; i++) {
original[i].setValor(temp[i].getValor());
original[i].setNomeArquivo(temp[i].getNomeArquivo());
original[i].setLetra(temp[i].getLetra());
}
37
38
39
40
41
42
}
O algoritmo Radix Sort faz 32 vezes a leitura de todo o conjunto. Isso parece ser algo relativamente
complexo, mas cada uma destas 32 comparações não é uma tarefa complexa, pois se trata de uma comparação
de apenas 1 dígito.
O método de Ordenação Shell Sort, proposto pelo matemático e cientista da computação Donald L. Shell
[10] é uma extensão do Insertion Sort, pois permite trocas por elementos que estão distantes, isto é, não troca
elementos imediatamente distinto, mas sim o elemento mais adequado a posição [11]. Na listagem 8 segue a
implementação Shell Sort.
Listagem 8: Ordenação proposta pelo Donald L. Shell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
*
* Shell Sort
* Ordenação proposta pelo Donald L. Shell
* Comentário: O algoritmo compara o elemento central com o primeiro elemento( linha 20) . O processo se repete sendo
* que o segundo elemento é comparado com o próximo elemento depois da posição central , seguindo este processo até
* que não seja realizada nenhuma troca e que o último elemento trocado seja menor que o próximo elemento lido ,
* controlado pelo i do laço da linha 13.
*
*/
int incremento = tam / 2;
while (incremento > 0) {
for (int i = incremento; i < tam; i++) {
int j = i;
Arquiva temp;
temp = new Arquiva();
temp.setValor(elementos[i].getValor());
temp.setNomeArquivo(elementos[i].getNomeArquivo());
temp.setLetra(elementos[i].getLetra());
while (j >= incremento && elementos[j - incremento].getValor() > temp.getValor()) {
elementos[j].setValor(elementos[j - incremento].getValor());
elementos[j].setNomeArquivo(elementos[j - incremento].getNomeArquivo());
elementos[j].setLetra(elementos[j - incremento].getLetra());
j = j - incremento;
}
elementos[j].setValor(temp.getValor());
elementos[j].setNomeArquivo(temp.getNomeArquivo());
elementos[j].setLetra(temp.getLetra());
}
if (incremento == 2) {
incremento = 1;
} else {
incremento *= (5.0 / 11);
}
}
Este método de ordenação utiliza espaço em memória para alocar temporariamente os elementos. Foram
propostas alterações [12] e [13] visando reduzir o número de comparações realizadas por este método de ordenação.
O método de Ordenação pelo “Monte” (Heap Sort) [1], utiliza conceitos de árvores binárias para identificar o maior elemento dentre um sub conjunto (2 filhos e um nó raiz). A rotina responsável por manter os maiores
valores (Heap máximo), na raiz é definida como MAX-HEAPIFY [1]. Na listagem 9 segue o método “heapify”,
responsável por esta tarefa.
Revista Brasileira de Computação Aplicada(ISSN 2176-6649), Passo Fundo, v. 7, n. 1, p. xx-xx, abr. 2015
7
Listagem 9: Ordenação pelo Monte
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
*
* Heap Sort
* Ordenação pelo monte
* Comentário: O algoritmo segmenta o conjunto identificando um elemento mais central ( linha 3) que será comparado
* (pelo método siftDown) com dos dois ú ltimos elementos do conjunto . A troca é realizada fazendo com que a próxima
* comparação seja feita , seguindo−se para o in í cio do conjunto e deslocando os elementos da esquerda do elemento
* central para a sua direita .
*
*/
public static void heapify(Arquiva[] a, int tam){
int noRoot = (tam - 2) / 2;
while (noRoot >= 0){
siftDown(a, noRoot, tam - 1);
noRoot--;
}
}
O método “siftDown” realiza a troca dos elementos, da mesma forma que é feito, por exemplo, no método
Bubble Sort. Para dados com elementos aleatórios, este método de ordenação se mostra bastante adequado, pois
mantém sua complexidade (melhor e pior caso) em valores próximos. Uma das desvantagens deste método é a
utilização de memória para construção e armazenamento da árvore binária.
Além dos algoritmos a serem implementados pelo desenvolver, também existem métodos de ordenação em
diversas linguagens de programação. Adicionalmente será analisado o tempo gasto pelo método de ordenação
sort() da classe Collections, presente na linguagem de programação Java. Será usado este método, passando dois
parâmetros, o primeiro é o conjunto de elementos, o outro é um comparador, que foi implementado. Neste caso, na
implementação foi definido o valor inteiro para ser adotado na ordenação, assim como foi feito nas implementações
descritas acima.
2.2
Custo dos algoritmos
Analisando a complexidade envolvida nos algoritmos de ordenação, foram adotadas duas principais considerações, o melhor caso e o pior caso. A Tabela 1 apresenta um comparativo nesta perspectiva. Neste comparativo
também é apresentado o algoritmo de ordenação Counting Sort o qual pressupõe que cada um dos n elementos da
entrada é um inteiro no intervalo de 1 até k. A ideia deste algoritmo de ordenação é que para cada elemento x da
entrada é identificado a quantidade de elementos menores que x. Com base nesta informação é possível inserir o
elemento x na sua posição correta. Conforme mostra a Tabela 1, as principais complexidades são:
1)O(n2 )
2)O(n lg(n))
3)O(d(n + k))
4)O(k + n).
Para ilustrar a complexidade de cada algoritmo é apresentada a Figura 1, que exibe um gráfico, sendo que
o eixo vertical representa as diferentes complexidades, no eixo horizontal é apresentado o valor de “n”, que indica
a quantidade de elementos a serem ordenados, os valores escolhidos para “n” iniciam em 10 e vão até 50 (os
elementos variam de 1 até 500). Cada linha no gráfico indica o resultado das complexidades para cada valor de
“n”, sendo possível identificar que a complexidade 1) O(n2 ) (linha na cor verde) aumenta significativamente com
relação as demais.
3
Pré-Processamento
Diante dos conceitos apresentados sobre ordenação, é possível desenvolver operações de pré-processamento
para facilitar tal processo. O pré-processamento consiste em uma técnica de suporte, uma vez que apenas segmenta
os elementos de acordo com faixas. Tais faixas são geradas baseando-se em limites inferiores e superiores dos
elementos a serem ordenados, sendo que é necessário conhecer previamente o maior e o menor elemento. O pré-
Revista Brasileira de Computação Aplicada(ISSN 2176-6649), Passo Fundo, v. 7, n. 1, p. xx-xx, abr. 2015
8
Tabela 1: Complexidade dos algoritmos de ordenação
Algoritmo
melhor caso pior caso
1)Bubble Sort
O(n2 )
O(n2 )
2
2)Selection Sort O(n )
O(n2 )
3)Insertion Sort O(n)
O(n2 )
4)Merge Sort
O(n lg(n))
O(n lg(n))
5)Quick Sort
O(n lg(n))
O(n2 )
6)Radix Sort
O(n)
O(d(n + k)) *
7)Shell Sort
O(n lg(n))
O(n2 )
8)Heap Sort
variável
O(n lg(n))
9)Counting Sort variável
O(k + n) **
Legenda da TABELA 1.
n = quantidade de elementos no conjunto de entrada.
lg(n) = logaritmo binário de n, lg2 (n). Onde 2x = n [1].
∗ d = quantidade de dígitos; k = possíveis valores para cada dígito [1].
∗∗ k = valor do último elemento do intervalo presente no conjunto [1].
Figura 1: Comparativo das Complexidades
processamento se diferencia do conceito dividir para conquistar [14], uma vez que os elementos não são apenas
segmentados e sim organizados por faixas de similaridade, fazendo com que qualquer elemento do segmento 1
(um), seja menor que qualquer elemento do segmento 2 (dois).
Os elementos são provenientes de arquivos JSON (JavaScript Object Notation), gerados de forma automática por métodos desenvolvidos para a criação dos arquivos e escolha de números aleatórios (Reversed, Random,
Few Unique e Nearly Sorted), conforme critérios estipulados pelo usuário. Conforme a disposição dos elementos
a serem ordenados, um método de ordenação pode ser mais eficiente do que outro. Diante desta adversidade gerada pelos dados, foram realizados 10 (dez) testes com cada um dos algoritmos (com e sem o pré-processamento).
Antes da ordenação, o algoritmo deve realizar a leitura de “n” arquivos e obter os elementos que se deseja ordenar,
Revista Brasileira de Computação Aplicada(ISSN 2176-6649), Passo Fundo, v. 7, n. 1, p. xx-xx, abr. 2015
9
isto é, cada arquivo contém um elemento.
A tarefa de pré-processamento foi implementada considerando dois aspectos: distribuição dos dados e
quantidade de elementos a serem ordenados. Diante destes dois aspectos se identifica que quanto mais elementos a
serem ordenados, mais custo tem o pré-processamento. Para tratar do primeiro aspecto, que consiste em identificar
como os dados serão distribuídos, é feito um laço de repetição que segmenta os elementos a serem ordenados na
quantidade de conjuntos (array), definida pelo usuário.
4
Implementação
Os algoritmos de ordenação foram utilizados em amostras distintas de dados, isto é, os elementos a serem
ordenados foram distribuídos de forma aleatória (Random), praticamente ordenado (Nearly Sorted), praticamente
desordenado (Reversed) e poucos elementos únicos (Few Unique) também de forma aleatória. O intervalo da
entrada, ou seja, dos elementos a serem ordenados, foi definido de 1 até 200000.
O comparativo foi realizado levando-se em consideração quantas comparações2 são feitas e quantas trocas
(de posição dos elementos na memória) são realizadas na ordenação [15]. A tarefa de pré-processamento que
é realizada antes da ordenação também foi computada, pois o pré-processamento tem um custo que deve ser
considerado.
Para realização dos testes foi implementada uma rotina de inicialização, essa rotina funciona da seguinte
forma: é definido por um parâmetro a quantidade de arquivos e outro parâmetro permite definir a distribuição dos
elementos. Dentro de cada arquivo gerado existe um objeto no formato JSON, com duas tags. A primeira tag
contém uma palavra, a segunda contém um número, que será o elemento a ser ordenado. Segue a estrutura do
arquivo: "letra": "AJBY","valor":110272.
Cada arquivo recebe um nome diferente, gerado automaticamente, por exemplo: arquivo_1.json. No entanto, o número (no caso _1) não é utilizado nas ordenações, permitindo que o arquivo tivesse um nome qualquer,
este recurso foi escolhido apenas para gerar nomes distintos para os “n” arquivos. A palavra gerada dentro da tag
letra, pode ser qualquer palavra.
Antes da ordenação dos elementos, são lidos os arquivos que foram criados anteriormente e o conteúdo
da tag letra, bem como o número que está dentro da tag valor, são armazenados em um array de 5 mil posições.
Adicionalmente é armazenado o nome do arquivo, a fim de possibilitar que no final seja exibida uma lista com
os nomes dos arquivos de forma ordenada pelo número que este contém. Com isso, tem-se todos os atributos
(letra, valor, nomeArquivo) para compor a estrutura com os dados a serem ordenados. Em seguida são aplicados
os algoritmos de ordenação.
Para melhorar os algoritmos de ordenação, foi implementada uma técnica, que consiste em agrupar os
elementos por semelhança. O agrupamento é feito durante a leitura dos arquivos, os elementos ficam segmentados
em “n” array. A quantidade de comparações realizadas após a implementação da técnica é variável, uma vez
que, cada um dos array pode conter uma quantidade variada de elementos. A expectativa é que exista a mesma
quantidade de elementos em cada array, no entanto este número pode variar. Para realizar esta segmentação, cada
elemento foi comparado, afim de identificar o grupo do mesmo. A seguir na listagem 10 é apresentada a técnica
para segmentação.
Listagem 10: Listagem para segmentação dos grupos
1
2
3
4
5
6
7
8
9
10
2 As
/**
*
* Comentário: Este código percorre os elementos e para cada elemento é feito um teste para verificar qual é o seu
* respectivo segmento.
*
*/
for (int i = 0; i < x; i++) {
divTemp = (double)200000/x;
a = 1+(divTemp*i);
b = divTemp*(i+1);
comparações são feitas entre dois inteiros, mas podem ser, também, entre dois caracteres.
Revista Brasileira de Computação Aplicada(ISSN 2176-6649), Passo Fundo, v. 7, n. 1, p. xx-xx, abr. 2015
10
if ((arquiva[j].getValor() >= a) && (arquiva[j].getValor() <= b)) {
arquiva2[i][gs[i]]=new Arquiva();
arquiva2[i][gs[i]].setValor(arquiva[j].getValor());
arquiva2[i][gs[i]].setNomeArquivo(arquiva[j].getNomeArquivo());
arquiva2[i][gs[i]].setLetra(arquiva[j].getLetra());
gs[i]++;
}
11
12
13
14
15
16
17
18
}
A variável x indica a quantidade de array(s) que os elementos serão divididos. Na linha 16 é realizado o
incremento na variável “gs”, que é responsável por armazenar a quantidade de elementos em cada array.
4.1
Testes
É possível reduzir a complexidade segmentando os elementos em array(s). Para exemplificar tal redução é
apresentada a Tabela 2, onde é exibida a complexidade, dividindo-se 50 elementos em 1, 2, 3, 4 e 5 array.
Tabela 2: Complexidade dos algoritmos de ordenação com divisão dos elementos
Complexidade n = 50 n = 25 ∗ 2 n ∼
= 16 ∗ 3 n ∼
= 12 ∗ 4 n = 10 ∗ 5
1)O(n2 )
2500
1250
768
576
500
2)O(n lg(n))
282
232
192
172
166
3)O(d(n + k)) 360
420
468
528
600
4)O(k + n)
550
1050
1548
2048
2550
Legenda da TABELA 2.
n = 50 indica que os 50 elementos foram alocados em um único array.
n = 25 ∗ 2 indica que os 50 elementos foram alocados em dois arrays.
n∼
= 16 ∗ 3 indica que os 50 elementos foram alocados em três arrays.
n∼
= 12 ∗ 4 indica que os 50 elementos foram alocados em quatro arrays.
n = 10 ∗ 5 indica que os 50 elementos foram alocados em cinco arrays.
Na Figura 2 é exibido um gráfico, sendo que o eixo vertical representa as quantidades de array em que
os 50 elementos foram segmentados. Este gráfico ilustra que apenas as complexidades O(n2 ) e O(n lg(n)) se
beneficiam da segmentação.
Nos testes de ordenação foram registrados os tempos de execução de cada algoritmo. O computador utilizado possuía a seguinte configuração: processador Intel Core I5 2.5GHz, 4GB DDR3 1333MHz de memória RAM
e disco rígido de 500GB 5400RPM.
Cada algoritmo de ordenação foi executado 10 vezes e o tempo utilizado como base foi a média destes 10
testes. Foram analisados os 8 algoritmos de ordenação (Bubble Sort, Insertion Sort, Selection Sort, Quick Sort,
Merge Sort, Radix Sort, Shell Sort, Heap Sort) descritos na seção II e também o método de ordenação sort() da
classe Collections da linguagem Java. Cada um dos algoritmos foi aplicado em 4 tipos de espalhamento (Random,
Nearly Sorted, Reversed e Few Unique) e a quantidade de grupos testada foi 2, 4, 8, 12, 16 e 20.
O primeiro algoritmo testado foi o Bubble Sort. Na Figura 3 (a) Bubble Sort é apresentado o gráfico
comparativo dos tempos de execução do algoritmo Bubble Sort aplicado nos elementos a serem ordenados. É
possível verificar que com o aumento da quantidade de grupos o tempo necessário para ordenação é reduzido.
A redução de tempo é verificada em todos os tipos de espalhamento de elementos. Em seguida foi testado o
algoritmo Insertion Sort, na Figura 3 Insertion Sort é apresentado o gráfico comparativo dos tempos de execução
deste aplicado nos elementos a serem ordenados.
O terceiro algoritmo foi o Selection Sort. Na Figura 4 (a) Selection Sort é apresentado o gráfico comparativo
dos tempos de execução deste algoritmo aplicado nos elementos a serem ordenados. O quarto algoritmo foi o Quick
Sort. Na Figura 4 (b) Quick Sort é apresentado o gráfico comparativo dos tempos de execução do mesmo. Este
Revista Brasileira de Computação Aplicada(ISSN 2176-6649), Passo Fundo, v. 7, n. 1, p. xx-xx, abr. 2015
11
Figura 2: Comparativo dos Grupos
Figura 3: Algoritmo Bubble Sort e Insertion Sort
(a) Bubble Sort
(b) Insertion Sort
algoritmo apresentou pouca redução no tempo de ordenação nos espalhamentos Random, Few Unique e Nearly
Sorted, sendo que no espalhamento Reversed não houve redução no tempo e sim, aumento. Este aumento ocorreu
pois o pré-processamento não reduziu o tempo neste tipo de espalhamento, apenas nos outros 3 espalhamentos.
O quinto algoritmo foi o Merge Sort. Na Figura 5 (a) Merge Sort é apresentado o gráfico comparativo dos
tempos de execução deste algoritmo aplicado nos elementos a serem ordenados. O sexto algoritmo foi o Radix
Sort. Na Figura 5 (b) é apresentado o gráfico comparativo dos tempos de execução deste aplicado nos elementos
a serem ordenados. Quando o espaço de memória não é um recurso limitante, é preferível utilizar Radix Sort, já
que este algoritmo utiliza um espaço de memória para organizar os elementos já ordenados na sua posição correta.
Radix Sort é o mais recomendado para ordenar elementos de mesmo tamanho, tais como datas, CEPs, CPF e
endereço IP.
O sétimo algoritmo foi o Shell Sort. Na Figura 6 (a) Shell Sort é apresentado o gráfico comparativo dos
tempos de execução deste, aplicado nos elementos a serem ordenados. O oitavo algoritmo foi o Heap Sort. Na
Revista Brasileira de Computação Aplicada(ISSN 2176-6649), Passo Fundo, v. 7, n. 1, p. xx-xx, abr. 2015
12
Figura 4: Algoritmo Selection Sort e Quick Sort
(a) Selection Sort
(b) Quick Sort
Figura 5: Algoritmo Merge Sort e Radix Sort
(a) Merge Sort
(b) Radix Sort
Figura 6 (b) Heap Sort é apresentado o gráfico comparativo dos tempos de execução deste aplicado nos elementos
a serem ordenados.
Por fim o nono algoritmo foi o sort(), da classe Colletions da linguagem Java. Na Figura 7 é apresentado o
gráfico comparativo dos tempos de execução do método sort() aplicado nos elementos a serem ordenados.
5
Conclusão
Neste artigo foi apresentado o funcionamento dos algoritmos de ordenação mais comuns na literatura. Para
melhorar o processo de ordenação é apresentada uma alternativa, que consiste em segmentar os elementos a serem
ordenados. Esta tarefa é realizada durante o carregamento dos dados, ou seja, durante a leitura dos arquivos que
contém os números a serem ordenados. Uma das vantagens proposta por esta alternativa é a redução do tempo
gasto pelos algoritmos de complexidade O(n2 ) e O(n lg(n)), conforme foi demonstrado na Figura 2.
A complexidade dos algoritmos é dada por equações descritas na seção II. A fim de verificar o resultado
prático da alternativa proposta, cada algoritmo de ordenação foi analisado 10 vezes em cada tipo de espalhamento.
Em seguida o mesmo foi feito, porém com os elementos a serem ordenados, agrupados em 2, 4, 8, 12, 16 e 20
grupos. Nos testes foi possível identificar a redução no tempo de execução ao aumentar os grupos, sendo que
ocorre uma estabilidade entre 16 e 20 grupos. Outra constatação importante foi que os algoritmos que inicialmente
Revista Brasileira de Computação Aplicada(ISSN 2176-6649), Passo Fundo, v. 7, n. 1, p. xx-xx, abr. 2015
13
Figura 6: Algoritmo Shell Sort e Heap Sort
(a) Shell Sort
(b) Heap Sort
Figura 7: Collections Sort
apresentavam um tempo de execução bastante distinto, chegaram em valores próximos quando a tarefa de processamento segmentou os elementos entre 16 e 20 grupos. Outro fator que pode ser levado em consideração é a
arquitetura do computador, pois isso pode levar os algoritmos a apresentar diferenças no tempo de execução.
O conceito de dividir uma tarefa complexa em tarefas menores também pode ser aplicado ao caso estudado.
No entanto a técnica de pré-processamento é mais adequada, visto que o pré-processamento pode ser feito no
momento em que os dados são lidos dos arquivos, implicando em pouco acréscimo de código.
A técnica da bolha aplicada em um array de 5 mil elementos, apresenta custo de: 25000000, pois adota a
complexidade dada por O(n2 ). Com a técnica de agrupamento por semelhança o custo é reduzido pela metade
(se for criado 2 grupos), acrescido da quantidade de comparações adicionadas no pré-processamento (2 para cada
elemento neste caso). A redução segue enquanto a quantidade de grupos aumenta, no caso de gerar 4 grupos, o
custo é de aproximadamente 6250000 no entanto existe um limite. No caso de 5 mil arquivos a quantidade ideal
de grupos é de 3500. No entanto durante os testes se percebeu que todos os algoritmos se estabilizam ao gerar 20
grupos.
É possível que em conjuntos com mais de 5000 elementos as quantidades de grupos para chegar a estabilidade pode ser maior. Em trabalhos futuros almeja-se verificar o comportamento dos algoritmos em conjuntos
maiores do que 5000 elementos.
Revista Brasileira de Computação Aplicada(ISSN 2176-6649), Passo Fundo, v. 7, n. 1, p. xx-xx, abr. 2015
14
Agradecimentos
Os autores gostariam de agradecer aos professores, Sandro José Rigo, José Vicente Canto dos Santos e
Jorge Luis Victória Barbosa, do Programa Interdisciplinar de Pós-Graduação em Computação Aplicada (PIPCA)
da UNISINOS, que não mediram esforços para auxiliar na pesquisa. Fica o agradecimento a todo grupo de pesquisa
do MobiLab/UNISINOS (Laboratório de Computação Móvel), que contribuíram para a definição da técnica de préprocessamento e com sugestões para melhora do texto. Fica registrado o profundo agradecimento a CAPES/Brasil
(Coordenação de Aperfeiçoamento de Pessoal de Nível Superior), PROSUP/Brasil (Programa de Suporte à PósGraduação de Instituições de Ensino Particulares), Santander Universidades pela bolsa de mestrado e CNPq/Brasil
(Conselho Nacional de Desenvolvimento Científico e Tecnológico) pelo apoio a pesquisa.
Referências
[1]
CORMEN, T. H. et al. Algoritmos: teoria e prática. 2nd. ed. [S.l.]: Elsevier, 2002.
[2]
BABU, D. et al. Array-indexed sorting algorithm for natural numbers. In: Communication Software and
Networks (ICCSN), 2011 IEEE 3rd International Conference on. [S.l.: s.n.], 2011. p. 606–609.
[3]
SINGH, S.; KAUR, S. Freeze Sorting Algorithm Based on Even-Odd Elements. IOSR Journal of Engineering, v. 4, n. 3, p. 18–23, 2014.
[4]
SAREEN, P. Comparison of sorting algorithms (on the basis of average case). International Journal of Advanced Research in Computer Science and Software Engineering, ACM, v. 3, n. 3, p. 522–532, mar. 2013.
ISSN 2277 128X.
[5]
GARCIA, A. M.; CERA, M. C.; MERGEN, S. L. Analisando o Desempenho da Paralelização no Algoritmo
de Ordenação Mergesort In-place. [S.l.]: E&9, 2013.
[6]
DARLINGTON, J. A synthesis of several sorting algorithms. Acta Informatica, Springer-Verlag, v. 11, n. 1,
p. 1–30, 1978. ISSN 0001-5903. Disponível em: <http://dx.doi.org/10.1007/BF00264597>.
[7]
ZAKI, M. J.; JR, W. M. Data Mining and Analysis: Fundamental Concepts and Algorithms. [S.l.]: Cambridge University Press, 2014.
[8]
GOODRICH, M. T.; TAMASSIA, R. Data Structures and Algorithms in Java. 2nd. ed. New York, NY, USA:
John Wiley & Sons, Inc., 2000. ISBN 0471383678, 9780471383673.
[9]
ASCENCIO, A. F. G.; ARAÚJO, G. S. d. Estrutura de dados: algoritmos, análise da complexidade e implementações em JAVA e C/C++. [S.l.]: Pearson Prentice Hall, 2010. ISBN 9788576058816.
[10] SHELL, D. L. A High-speed Sorting Procedure. Commun. ACM, ACM, New York, NY, USA, v. 2, n. 7, p.
30–32, jul. 1959. ISSN 0001-0782. Disponível em: <http://doi.acm.org/10.1145/368370.368387>.
[11] SHAHZAD, B.; AFZAL, M. T. Enhanced ShellSorting Algorithm. Computer Journal of Enformatika, v. 21,
n. 6, p. 66–70, 2007.
[12] POONEN, B. The Worst Case in Shellsort and Related Algorithms. Journal of Algorithms, v. 15, p. 101–124,
1993.
[13] PLAXTON, C. G.; SUEL, T. Lower Bounds for Shellsort. Departament of Computer Science, University of
Texas at Austin, 1992.
[14] PATEL, Y.; SINGH, N.; VASHISHTHA, L. Fuse sort algorithm a proposal of divide & conquer based sorting
approach with o(nloglogn) time and linear space complexity. In: Data Mining and Intelligent Computing
(ICDMIC), 2014 International Conference on. [S.l.: s.n.], 2014. p. 1–6.
[15] KNUTH, D. E. Sorting and Searching, volume 3 of The Art of Computer Programming. [S.l.]: MA: AddisonWesley, 1973.
Revista Brasileira de Computação Aplicada(ISSN 2176-6649), Passo Fundo, v. 7, n. 1, p. xx-xx, abr. 2015
15