Quais são os métodos de ordenação?

Question

Quais as diferenças e empregabilidade dos métodos de ordenação Selection Sort, Insertion Sort e Bubble Sort?

Ana Bizerra · Answer

Métodos de Ordenação Simples: Bubble Sort, Insertion Sort e Selection Sort ü BUBBLE SORT O Bubble Sort é um algoritmo de ordenação simples que precisa de O(n2) comparações para ordenar n itens. Ele é um dos mais simples algoritmos de ordenação conhecidos, mas geralmente é considerado muito ineficiente para trabalhos que ordenam um grande número de elementos. É essencialmente equivalente ao insertion sort --- ele compara e troca os mesmos pares de elementos, apenas em uma ordem diferente. Apesar de serem muito simples, o insertion sort e o bubble sort tendem a ser os mais eficientes algoritmos de ordenação que se destinam a ordenar um pequeno número de elementos. O algoritmo bubble sort faz: 1. compara elementos adjacentes. Se o primeiro é maior do que o segundo, então a troca é realizada. 2. faz isto para cada par de elementos adjacentes, começando com os dois primeiros e terminando com os dois últimos. Neste ponto o último elemento deve ser o maior de todos. 3. repete os passos para todos os elementos exceto para o último. 4. continua repetindo, cada vez com um elemento a menos, até não existam mais pares para se comparar. void bubbleSort(int array[], int length) { int i, j, temp; for(i = length - 1; i > 0; i--) for(j = 0; j < i; j++) if(array[j] > array[j+1]) /* compara elementos vizinhos */ { temp = array[j]; /* troca array[j] e array[j+1] */ array[j] = array[j+1]; array[j+1] = temp; } } Casos a considerar: Melhor caso: Verifica-se quando o vetor já está ordenado. Pior caso: Verifica-se quando o vetor está ordenado na ordem inversa. Neste algoritmo tanto o melhor caso, como o pior caso tem ordem "n2" porque em ambos os casos os ciclos são sempre realizados até ao fim, mesmo quando os elementos já estão ordenados. ü INSERTION SORT O Insertion Sort é um algoritmo eficiente para ordenar um pequeno número de elementos. Basicamente, este algoritmo varre um array de elementos da esquerda para a direita e a medida que avança vai deixando os elementos mais a esquerda ordenados. Obs.: Para colocar em ordem decrescente experimente trocar o > por < dentro do laço mais interno. void insertion(int v[], int n) { int i, j, x; for(j=1;j=0 && v[i]>x;--i) v[i+1] = v[i]; v[i+1] = x; } } Casos a considerar: Melhor caso: quando o array já está ordenado. Neste caso a comparação no laço interno sempre falhará na primeira comparação e o tempo de execução dependerá apenas do laço externo. O tempo de execução obedecerá a uma função linear e a complexidade do algoritmo será de O(n). Pior caso: quando o array está na ordem inversa. Nesta situação para cada iteração do laço externo, o laço interno executará n-1 vezes, onde n é o valor da variável j no laço externo. Temos que a complexidade de tempo do algoritmo neste caso será de O(n(n-1)) = O(n2-n) = O(n2). ü SELECTION SORT O Selection Sort é um algoritmo que ordena itens verificando repetidamente os itens restantes para encontrar o menor deles e movê-lo para uma posição final. A idéia por trás do selection sort é que para ordenar N itens você tem que passar por todos eles. 1. No primeiro passo você encontra o maior valor, e então troca ele pelo último item. Assim o maior item está agora na posição N. 2. No segundo passo você faz uma varredura apenas nos N-1 elementos. O maior dos itens é troca de posição com o item na posição N-1. Assim o maior de todos os itens está agora na última posição; o segundo maior na segunda maior posição. 3. Este processo é repetido, com um item sendo colocado na sua posição correta a cada vez. 4. Depois de N passos, a coleção inteira de dados está ordenada. Uma variação simples é encontrar o menor item a cada vez e colocá-lo na frente. Para ordenar em ordem decrescente, o maior item é encontrado a cada vez e movido para a frente. void selectionSort(int vetor[],int tam) { int i,j; int min,aux; for (i=0;i

Lucas Nunes · Answer

Os três algoritmos mais básicos de ordenação. A implementação é em Java.

O bubble sort consiste em prover, em cada passo i, os menores elementos para o início do vetor, de tal forma que o i-ésimo menor estará na sua posição correta.

O insertion sort consiste em manter os i primeiros elementos ordenados entre si. No passo i, insere o i+1 elemento na posição correta entre os i primeiros.

Já o selection sort consiste em, a cada passo i, colocar na i-ésima posição o menor elemento entre os n-i elementos restantes.

Abaixo seguem as implementações:


 public void insertionSort(int a[]) {
  for (int i=1;i< a.length;i++) {
   for (int j=i;j>0;j--){
    if (a[j]< a[j-1]) {
     int temp = a[j];
     a[j] = a[j-1];
     a[j-1] = temp;
    }
    else {
     break;
    }
   } 
  } 
 }


 public void selectionSort(int a[]) {
  for (int i=0;i< a.length-1;i++){
   int menor = i;
   for (int j=i+1;j< a.length;j++) {
    if (a[j]< a[menor]){
     menor = j;
    } 
   }
   int temp = a[menor];
   a[menor] = a[i];
   a[i] = temp;
  }
 }


 public void bubbleSort(int[] a) {
  for (int i=0;i< a.length;i++) {
   for (int j=a.length-1;j>i;j--) {
    if (a[j]< a[j-1]) {
     int temp = a[j];
     a[j]= a[j-1];
     a[j-1] = temp;
    }
   }
  }
 }

Jonathas Alves · Answer

método de ordenação insertion sort, (inserção);
método de ordenação selection sort (seleção);
método de ordenação bubble sort(bolha);
método de pesquisa sequencial;
método de pesquisa binária;

Biossegurança

Quais são os métodos de ordenação?

Respostas

Crie sua conta grátis para liberar essa resposta. 🤩

Ainda com dúvidas?

Perguntas dessa disciplina

Estrutura de dados

Como fazer um algoritmo de busca binária e sequencial?

Pessoal me Estudando para a prova me deparei com essa questão.

Quem poderia mim ajudar indicando um bom material de ESTRUTURA DE DADOS ou um bom livro

Conteúdos escolhidos para você

Ordenação

Exercicio ordenacao

Métodos de Ordenação - Métodos Simples

Os métodos de arquivamento

Mais conteúdos dessa disciplina