terça-feira, maio 29, 2007

Bubble sort, Insertion sort e Selection sort

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


Até a próxima! Esperem que métodos de quick sort, merge sort e heap sort ainda virão.

Um comentário:

Anônimo disse...

intiresno muito, obrigado