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

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;
    }
   }
  }
 }

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<n;j++) {

x = v[j];

for(i=j-1;i>=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<tam-1;i++)

{

min=i;

for (j=i+1;j<tam;j++)

{

if (vetor[j]<vetor[min])

min=j;

}

aux=vetor[i];

vetor[i]=vetor[min];

vetor[min]=aux;

}

}

Casos a considerar:

Pior e melhor caso: O(n2)

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;