Métodos de Ordenação em Javascript

Prévia do material em texto

Estrutura de Dados
Ordenação
Introdução
● A ORDENAÇÃO corresponde ao processo de reorganizar (rearranjar) 
um conjunto de dados em ordem crescente ou decrescente.
● Consiste na ordenação, na forma crescente ou decrescente, de uma 
seqüência S, composta de n elementos que podem ser comparados 
entre si, conforme uma relação total de ordem.
● Tem como objetivo principal facilitar a recuperação posterior de itens 
em um conjunto ordenado de dados.
Introdução
● Ex:
● Chamada dos Alunos;
● Dicionário;
● Andares de um prédio;
● Etc;
Classificação dos métodos de ordenação
● Os métodos de ordenação podem ser classificados quanto a memória 
utilizada para realizar a ordenação.
● Ordenação Interna
- Para os casos em que o volume de dados a ser ordenado cabe todo na 
memória principal.
- Nº de registros a serem ordenado é pequeno;
- Uso de vetores (arrays).
● Ordenação Externa
- Para os casos em que o volume de dados NÃO cabe todo na memória 
principal.
- Uso de memória secundária (fita ou disco) para armazenar a coleção de 
dados.
Métodos de Ordenação
● BubbleSort 
● SelectionSort 
● InsertionSort 
● QuickSort 
Ordenação BubbleSort
● Classificação dos elementos de uma tabela (vetor) através da troca 
imediata dos itens que estiverem fora da ordem.
• Os elementos de menor valor irão emergindo para o início da tabela 
como se fossem bolhas.
O Algoritmo
Para o número de (n-1) elementos faça
Para cada elemento da tabela faça
Se o elemento atual for maior que o elemento seguinte, então
Troca os elementos de posição
Fim-se
Fim-para
Fim-para
O método consiste na comparação de cada elemento da coleção com os seus 
demais. Caso os elementos estejam fora de ordem, então realiza-se a troca 
das posições desses elementos.
Repete-se o processo para os N-1 elementos da coleção de dados.
Exemplo
● Dado a seguinte tabela (vetor):
T = {3,1,5,4,2}
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
Resultado Final
1 2 3 4 5
0 1 2 3 4
Conclusões
● Método mais simples;
● O mais lento.
Exercício 1
● Implemente a classe Ordenacao com o método bubbleSort para os 
seguintes casos: 
a. Implemente o método de bubbleSort, recebendo como parâmetro um 
vetor de inteiros e realizando a ordenação do vetor tendo como chave do 
registro o próprio conteúdo do vetor (números inteiros).
b. Implemente o método de bubbleSort, recebendo como parâmetro um 
vetor de Strings contendo a relação de nomes de alunos de uma turma, e 
realizando a ordenação do vetor tendo como chave do registro o próprio 
conteúdo do vetor (nomes).
c. Implemente o método de bubbleSort, recebendo como parâmetro um 
vetor de Alunos contendo os dados dos alunos (matricula, nome, nota de 
av1 e nota de av2) de uma turma, e realizando a ordenação do vetor tendo 
como chave do registro a matricula do aluno.
Exercício 2
● Implemente uma aplicação que solicite o tamanho da coleção da 
dados a ser recebido e em seguida solicite os dados, depois realize a 
ordenação (chamando o método de ordenação bubbleSort da classe 
Ordenacao) e ao final exiba o resultado da ordenação e o tempo gasto 
(em segundos) para ordenar a coleção nos seguintes casos :
a. para uma coleção de dados inteiros.
b. para uma coleção de dados referente aos nomes de uma turma de 
alunos.
c. para uma coleção de dados de alunos (matricula, nome, nota de av1 e 
nota de av2) de uma turma.
Ordenação SelectionSort
● Classificação dos elementos de uma tabela (vetor) através da troca 
dos itens que estiverem fora da ordem.
• Melhoria do método Bubble-sort (bolha), pois reduz o n° de 
comparações e de trocas em memória.
• Faz uso de um elemento pivô.
● Utiliza o algoritmo da busca do menor elemento.
O Algoritmo
Para o número de (n-1) elementos faça
Guarda-se a posição do pivô (elemento n)
Para cada elemento da tabela a partir da posição (n+1) faça
Se o pivô for maior que o elemento corrente, então
Guarde a posição do elemento de menor valor
Fim-se
Fim-para
Troca-se o conteúdo do elemento pivô com o conteúdo do 
menor elemento encontrado
Fim-para
O método consiste na seleção de um elemento pivô para cada iteração 
(repetição) e a busca pelo menor elemento à direita deste pivô. Ao final da 
iteração troca-se de posição o elemento pivô com o elemento de menor valor. 
Repete-se o processo para os N-1 elementos da coleção de dados.
Exemplo
● Dado a seguinte tabela (vetor):
T = {3,1,5,4,2}
Exemplo
3 1 5 4 2
3 1 5 4 2
3 1 5 4 2
3 1 5 4 2
3 1 5 4 2
1
1
1
1
1
menor0 1 2 3 4
T
1 =
T
2 =
T
3 =
T
4 =
Troca:
pivô
1 3 5 4 2
Exemplo
1 3 5 4 2
1 3 5 4 2
1 3 5 4 2
1 3 5 4 2
2
3
4
4
menor0 1 2 3 4
T
5 =
T
6 =
T
7 =
Troca:
pivô
1 2 5 4 3
Exemplo
1 2 5 4 3
1 2 5 4 3
1 2 5 4 3
3
4
4
menor0 1 2 3 4
T
8 =
T
9 =
Troca:
pivô
1 2 3 4 5
Exemplo
1 2 3 4 5 4
menor0 1 2 3 4
T
10 =
Não há troca
pivô
1 2 3 4 5
Resultado Final
0 1 2 3 4
Conclusões
● Método simples.
• Otimiza o n° de comparações do Bubble-sort.
• Reduz o n° de comparações para N * (N-1)
 2
• Continua lento.
Exercício 3
● Acrescente a classe Ordenacao a implementação do método 
SelectionSort para os seguintes casos:
a. recebendo como parâmetro um vetor de inteiros e realizando a 
ordenação do vetor tendo como chave do registro o próprio conteúdo do 
vetor (números inteiros).
b. recebendo como parâmetro um vetor de Strings contendo a relação de 
nomes de alunos de uma turma, e realizando a ordenação do vetor tendo 
como chave do registro o próprio conteúdo do vetor (nomes).
c. recebendo como parâmetro um vetor de Alunos contendo os dados dos 
alunos (matricula, nome, nota de av1 e nota de av2) de uma turma, e 
realizando a ordenação do vetor tendo como chave do registro a matricula 
do aluno.
Exercício 4
● Modifique a classe aplicação criada no Exercício 2 para que faça 
chamanda ao método de ordenação selectionSort da classe Ordenacao, 
e exiba ao final o resultado da ordenação e o tempo gasto (em 
segundos) para ordenar a coleção nos seguintes casos :
a. para uma coleção de dados inteiros.
b. para uma coleção de dados referente aos nomes de uma turma de 
alunos.
c. para uma coleção de dados de alunos (matricula, nome, nota de av1 e 
nota de av2) de uma turma.
Ordenação InsertionSort
● Classificação dos elementos de uma tabela (vetor) através da troca 
dos itens que estiverem fora da ordem à esquerda de um elemento 
pivô.
• Melhoria do método selection-sort, pois reduz o n° de comparações e 
de trocas em memória.
• Faz uso de um elemento pivô.
● Utiliza o algoritmo da busca do menor elemento (à esquerda do pivô).
● O processo realiza a movimentação dos elementos de chaves maiores 
para à direita, abrindo-se espaço para inserção do elemento pivô.
● Assemelha-se ao processo de ordenação de uma mão de cartas 
(baralho).
O Algoritmo
Para o número de (n-1) elementos, a partir do 2º elemento faça
Guarda-se o pivô (elemento n)
Enquanto não atingir o limite esquerdo e o elemento (n+1) for 
maior que o pivô faça
Move-se o elemento (n+1) uma posição para a direita
fim_enquanto
Insere-se o elemento pivô na posição encontrada.
Fim-para
O método consiste na seleção de um elemento pivô, iniciando a partir a 2ª 
posição da coleção. A cada iteração (repetição) movem-se os elementos de 
chave maior que o pivô, à esquerda deste, até que se encontre um elemento 
de valor menor que o pivô, ou se alcance o limite esquerdo da coleção de 
dados. Neste momento realiza-se a inserção do elemento pivô entre o menor 
elemento e o último maior elemento à esquerda da posição inicial do pivô. 
Repete-se o processo para os N-1 elementos da coleção de dados.
Exemplo
● Dado a seguinte tabela (vetor):
T = {3,1,5,4,2}
Exemplo
3 1 5 4 2
3 1 5 4 2
1 3 5 4 2
1
Pivô
0 1 2 3 4
T
1 =
mover:
pivô
1 3 5 4 2
inserir:
resultado
Exemplo
1 3 5 4 2
1 3 5 4 2
5
Pivô
0 1 2 3 4
T
2 =
pivô
1 3 5 4 2
Não há movimento de dado 
nem inserção
resultado
T
3 =
Exemplo
1 3 5 4 2
1 3 5 4 2
1 3 5 5 2
4
Pivô
0 1 2 3 4
T4 =
pivô
1 3 4 5 2resultado
mover:
inserir:
Exemplo
1 3 4 5 2
1 3 4 5 2
1 3 4 5 5
1 3 4 5 5
1 3 4 4 5
1 3 3 4 5
1 3 3 4 5
2
Pivô
0 1 2 3 4
T
6 =
pivô
mover:
mover:
inserir:
T
7 =
mover:
T
8 =
Exemplo
0 1 2 3 4
1 2 3 4 5
Resultado Final
Conclusões
● Método simples.
● É um método estável, pois deixa os elementos com chaves de 
registros iguais na mesma posição relativa.
• Aproximadamente 2x mais rápido que o método Bubble-sort (bolha), e 
tem desempenho superior ao Selection-sort.
Exercício 5
● Dado a seguinte sequencia S:
S = {7, 19, 24, 13, 31, 8, 82, 18 ,44, 63, 5, 29}
● Realize, passo-a-passo e por escrito, a ordenação segundo o método 
InsertionSort. 
Exercício 6
● Acrescente a classe Ordenacao a implementação do método 
InsertionSort para os seguintes casos:
a. recebendo como parâmetro um vetor de inteiros e realizando a 
ordenação do vetor tendo como chave do registro o próprio conteúdo do 
vetor (números inteiros).
b. recebendo como parâmetro um vetor de Strings contendo a relação de 
nomes de alunos de uma turma, e realizando a ordenação do vetor tendo 
como chave do registro o próprio conteúdo do vetor (nomes).
c. recebendo como parâmetro um vetor de Alunos contendo os dados dos 
alunos (matricula, nome, nota de av1 e nota de av2) de uma turma, e 
realizando a ordenação do vetor tendo como chave do registro a matricula 
do aluno.
Exercício 7
● Modifique a classe aplicação criada no Exercício 2 para que faça 
chamanda ao método de ordenação insertionSort da classe Ordenacao, 
e exiba ao final o resultado da ordenação e o tempo gasto (em 
segundos) para ordenar a coleção nos seguintes casos :
a. para uma coleção de dados inteiros.
b. para uma coleção de dados referente aos nomes de uma turma de 
alunos.
c. para uma coleção de dados de alunos (matricula, nome, nota de av1 e 
nota de av2) de uma turma.
Exercício 8
● Compare os resultados obtidos na execução das ordenações BubbleSort, 
SelectionSort e InsertionSort considerando o volume de dado e o tempos 
gastos. 
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39