Aprendendo métodos de ordenação

Aprendendo métodos de ordenação


Objetivos

Este objeto de aprendizagem apresenta atividades e fundamentos sobre a ordenação de dados, descrevendo em detalhes quatro métodos que podem ser utilizados nesta tarefa.

A ferramenta é indicada para estudantes de graduação, especialmente alunos da disciplina de algoritmos. O AMO pode ser usado como apoio para o ensino presencial por professores e alunos em sala de aula ou na realização de atividades extra classe.

  • Público: Estudantes de graduação, especialmente alunos da disciplina de algoritmos. O AMO pode ser usado como apoio para o ensino presencial por professores e alunos em sala de aula ou na realização de atividades extra classe.
  • Autores: Evandro Franzen, Maria Claudete Wildner, Mouriac Halen Diemer, Luis Antônio Schneiders.
  • Assessoria técnica: Artur Welp


Aprendendo métodos de ordenação


Situação problema:

O professor da disciplina de Algoritmos decide que a ordem de apresentação dos projetos finais, que representam a terceira nota do semestre, será por ordem crescente das datas de aniversário dos estudantes. Para tanto, entrega o conjunto de datas de aniversário dos estudantes regularmente matriculados nesta disciplina em uma estrutura de dados conhecida como vetor e decide que a própria turma encontre e aplique um método de ordenação deste vetor. Bem, embora os estudantes conheçam vetores e os pré-requisitos para a utilização dos mesmos, ainda não conhecem os métodos de ordenação destes, problema que decide resolver com a aplicação de um Objeto de Aprendizagem (OA) específico.

Resultado esperado:

É esperado que, com base no vetor recebido e com o apoio do Objeto de Aprendizagem para ordenação de vetores, os estudantes apresentem o vetor com as datas de aniversário ordenadas em ordem crescente para que este seja utilizado pelo professor na organização das apresentações dos projetos finais em sua disciplina de Algoritmos.

Para verificar os seus conhecimentos sobre o conteúdo básico de algoritmos, resolva o Desafio Inicial.

Se o seu score ficar abaixo de 70%, acesse e faça um bom estudo do material indicado abaixo:

Aprendendo métodos de ordenação


Algoritmos de ordenação

Aprendendo métodos de ordenação


Bubble sort

Um dos métodos de ordenação mais conhecidos é o Bubble Sort. Este algoritmo também é chamado de ordenação por flutuação ou bolha e é um dos que apresenta uma das menores complexidades. A lógica do algoritmo consiste em percorrer a lista diversas vezes, fazendo com que o menor elemento seja inserido no topo. O termo “bolha” diz respeito a esta ideia, ou seja, a bolha (menor elemento) deve “emergir” até chegar a superfície.

Neste algoritmos os elementos são comparados aos pares (o primeiro com o segundo, o segundo com o terceiro, o terceiro com o quarto, ...) em rodadas sucessivas, trocando suas posições sempre que necessário. Na primeira rodada o elemento maior acabará se posicionado na última posição, ou seja, na sua posição definitiva. Portanto, na rodada seguinte, o maior elemento já estará posicionado. Assim a cada rodada podemos reduzir uma comparação. Uma lista de n elementos estará ordenada depois de n-1 rodadas ou, antes disso, quando percebemos que ao final de uma rodada nenhuma troca ocorreu.

Acompanhe este exemplo:

Considere que é necessário ordenar a lista de números 10, 7, 3, 15, 9. Para ordenar esta lista de 5 elementos serão necessárias 4 rodadas de comparação. Iniciamos a primeira rodada comparando o número 10 e o 7 e trocamos suas posições, gerando a lista 7, 10, 3, 15, 9. Continuamos comparando agora o 10 com 3 e novamente trocamos suas posições, gerando a lista 7, 3, 10, 15, 9. Seguimos comparando o 10 com o 15 (sem trocar) e depois o número 15 com o número 9, trocando suas posições e gerando, ao final a primeira rodada a lista 7, 3, 10, 9, 15. Observe que o número 15 acabou posicionado ao final da lista.

Repete-se então todo o processo, pela segunda vez, considerando apenas os 4 primeiros elementos 7, 3, 10 e 9, pois o número 15 já está posicionado. No final desta rodada a lista será 3, 7, 9, 10, 15. Repete-se o processo considerando agora apenas os 3 primeiro elementos 3, 7 e 9, pois é sabido que os dois valores maiores já estão posicionados corretamente. Como não houve trocas nesta terceira rodada podemos interromper o processo, ou seja a quarta e última rodada não será necessária.

Abaixo observe as ilustrações do funcionamento do algoritmo.




					ALGORITMO BubbleSort
					INÍCIO
						DECLARE
							vetor[5] NUMÉRICO
							nãoOrdenado NUMÉRICO
							últimaTroca NUMÉRICO
							aux NUMÉRICO

						// preencher vetor com alguns números
						vetor[0] ← 7
						vetor[1] ← 3
						vetor[2] ← 4
						vetor[3] ← 1
						vetor[4] ← 5

						// início do método de ordenação
						posNãoOrdenado ← 4 	// um a menos do que o tamanho do vetor
						posÚltimaTroca ← 4	// um a menos do que o tamanho do vetor

						ENQUANTO posÚltimaTroca > 0
						INÍCIO
							posÚltimaTroca ← 0
							PARA i ← 0 ATÉ posNãoOrdenado FAÇA
							INÍCIO
								SE vetor[i] > vetor[i+1]
								INICIO
							aux ← vetor[i]
							vetor[i] ← vetor[i+1]
							vetor[i+1] ← aux
							posÚltimaTroca ← i
								FIM
							FIM
							posNãoOrdenado ← posÚltimaTroca
						FIM

						// exibir o vetor ordenado
						PARA i ← 0 ATÉ 4 FAÇA
						INÍCIO
						ESCREVA vetor[i]
						FIM
					FIM
                          
					public class BubbleSort
					{
						 public static void main(String[] args)
						 {
							  // preencher vetor com alguns números
							  int[] vetor = { 7,3,4,1,5 };

							  // início do método de ordenação
							  int posNãoOrdenado = vetor.length-1;
							  int posÚltimaTroca = vetor.length-1;

							  while (posÚltimaTroca > 0)
							  {
								   posÚltimaTroca = 0;
								   for (int i=0; i < posNãoOrdenado; i++)
								   {
										if (vetor[i] > vetor[i+1])
										{
											 int aux = vetor[i];
											 vetor[i] = vetor[i+1];
											 vetor[i+1] = aux;
											 posÚltimaTroca = i;
										}
								   }
								   posNãoOrdenado = posÚltimaTroca;
							  }

							  // exibir o vetor ordenado
							  for (int i=0; i < vetor.length; i++)
							  {
								   System.out.println(vetor[i]);
							  }
						 }
					}
                          

Aprendendo métodos de ordenação


Shell sort



Animação


Aprendendo métodos de ordenação


Select sort



Animação


Aprendendo métodos de ordenação


Insert sort

Neste algoritmo deve-se percorrer a sequência da esquerda para a direita, ou seja, em cada rodada elege-se um elemento para análise (inciando pela esquerda) e procura-se a posição em que ele deve ser inserido, sempre em comparação com seus anteriores. Ao descobrir a posição de inserção todos os elementos entre esta posição e a posição onde está o elemento eleito, são deslocados uma posição para direita, transferindo o elemento eleito para a posição de inserção.

Acompanhe este exemplo:

Considere que desejamos ordenar a sequência de números 3, 1, 4, 2, 7. Começamos elegendo o número 1 (que está na segunda posição), então comparamos o número 1 com os seus anteriores e percebemos que a posição correta dele é a primeira. Deslocamos então o número 3 uma casa para direita e o número 1 assume a posição inicial. A lista fica então 1, 3, 4, 2, 7. Elegemos agora o número 4 (que está na posição 3) e o comparamos com os seus anteriores. Percebemos que a posição dele não deve ser mudada, pois todos os anteriores são menores do que ele. Passamos então para o número 2 (que está na posição 4) e o comparamos com seus anteriores. A posição correta dele é a segunda, então deslocamos todos os elementos entre a segunda posição e a quarta posição uma casa para a direita e inserimos o número 2 na segunda posição. A lista fica então 1, 2, 3, 4, 7. Continuamos o processo agora elegendo o número 7 (que está na quinta posição). Comparamos o número 7 com seus anteriores e percebemos que não há necessidade de mudança. A lista estará ordenada quando atingirmos o último elemento, ou seja, esta lista encontra-se ordenada.

Abaixo observe a ilustração do funcionamento do algoritmo.




                            Pseudo-código

                            ALGORITMO InsertionSort
                            INÍCIO
                                DECLARE
                                    vetor[5] NUMÉRICO
                                    posElemento NUMÉRICO // posição do elemento que está sendo analisado
                                    posInserção NUMÉRICO // posição em que o elemento deve ser inserido
                                    aux NUMÉRICO
                                    i NUMÉRICO

                                // preencher vetor com alguns números
                                vetor[0] ← 7
                                vetor[1] ← 3
                                vetor[2] ← 4
                                vetor[3] ← 1
                                vetor[4] ← 5

                                // início do método de ordenação
                                PARA j ← 1 ATÉ 5 FAÇA
                                INÍCIO
                                    i ← 0
                                    posElemento ← j
                                    posInserção ← j

                                    ENQUANTO i < posElemento
                                    INÍCIO
                                        SE vetor[posElemento] < vetor[i]
                                        INÍCIO
                                            posInserção ← i
                                            i ← posElemento
                                        FIM
                                        i ← i + 1
                                    FIM

                                    SE posInserção < posElemento // há necessidade de reposicionamento
                                    INÍCIO
                                        aux ← vetor[posElemento]
                                        PARA i ← posElemento ATÉ posInserção-1 PASSO -1 FAÇA
                                        INÍCIO
                                            vetor[i] ← vetor[i-1]
                                        FIM
                                        vetor[posInserção] ← aux
                                    FIM
                                FIM

                                // exibir o vetor ordenado
                                PARA i ← 1 ATÉ 5
                                INÍCIO
                                    ESCREVA vetor[i]
                                FIM
                            FIM
                          
                            public class InsertionSort
                            {
                                public static void main(String[] args)
                                {
                                    // preencher vetor com alguns números
                                    int[] vetor = { 7,3,4,1,5 };

                                    // início do método de ordenação
                                    for (int j = 1; j < vetor.length; j++)
                                    {
                                        int i = 0;
                                        int posElemento = j; // posição do elemento que está sendo analisado
                                        int posInsercao = j; // posição em que o elemento deve ser inserido
                                        while (i < posElemento)
                                        {
                                            if (vetor[posElemento] < vetor[i])
                                            {
                                                posInsercao = i;
                                                i = posElemento;
                                            }
                                            i++;
                                        }
                                        if (posInsercao < posElemento) // há necessidade de reposicionamento
                                        {
                                            int aux = vetor[posElemento];
                                            for (i=posElemento; i > posInsercao; i--)
                                            {
                                                vetor[i] = vetor[i-1];
                                            }
                                            vetor[posInsercao] = aux;
                                        }
                                    }

                                    // exibir o vetor ordenado
                                    for (int i : vetor)
                                    {
                                        System.out.println(i);
                                    }
                                }
                            }
                          

Aprendendo métodos de ordenação


Guia

Ao clicar no botão iniciar você será direcionado à página inicial que irá descrever o problema da ordenação e na qual você irá realizar um desafio com questões sobre algoritmos e ordenação de dados. A realização da atividade é muito importante porque irá demonstrar a importância da ordenação de dados e também vai estimular a sua busca pelo conhecimento sobre os métodos descritos.

Após o desafio inicial você poderá continuar o seu caminho por este objeto, acessando informações sobre os seguintes métodos: Bubble sort, Shell sort, Select sort e Insert sort. Em cada uma das páginas que apresentam os métodos citados você encontrará textos, vídeos e uma atividade que contribuirá para que você compreenda os conceitos e o funcionamento dos algoritmos.

Mapa de navegação

Imagem para o mapa de navegação

Vá em frente e bom aprendizado!

Créditos

Conteúdo e Desenvolvimento

Evandro Franzen

Maria Claudete Wildner

Mouriac Halen Diemer

Luis Antônio Schneiders

Revisão

Maria Elisabete Bersch

Assessoria técnica

Artur Welp

Logo da Univates Licença Creative Commons