Um algoritmo de ordenação é considerado estável quando consegue preservar a ordem de registro de chaves iguais, em outras palavras se os registros aparecem na sequencia ordenada na mesma ordem em que estão na sequencia inicial.
Um exemplo de algoritmo estável, ordenando a sequencia de numeros (chaves) com letras (registros)
3[a], 2[b], 2[c], 1[d]
Obrigatóriamente o resultado será:
1[d], 2[b], 2[c], 3[a]
Os algoritmos não estaveis sujeitam os elementos associados aos objetos a serem ordenados:
1[d], 2[c], 2[b], 3[a]
Um algoritmo é estável quando números com o mesmo valor aparecem no arranjo de saída na mesma ordem em que se encontram no arranjo de entrada.
Essa propriedade é importante quando os dados satélites que acompanham os elementos sendo ordenado devem ser transportados juntamente com o elemento.
O algoritmo de ordenação por contagem é estável já que ele faz a leitura no array intermediário de trás para frente na hora de criar o vetor resultante. Mas é a manutenção desta estabilidade que obriga que o algoritmo utilize um array auxiliar. Se a propriedade de estabilidade não precisasse ser mantida, o algoritmo já poderia ir trabalhando no próprio array inicial, usando menos memória.
exemplos:
Ordenação bubble sort (estável)
for(i=n-1;i>0;i--)
for(j=0;j
if( v[j] > v[j+1])
swap(v[j], v[j+1]);
Ordenação por inserction sort (estável)
for(j=1; j
chave = v[j];
i = j-1;
while(i >= 0 && v[i] > chave){
v[i+1] = v[i];
i--;
}
v[i+1] = chave;
}
Ordenação QuickSort (Não estável)
#include
using namespace std;
int partition(int vec[], int left, int right) {
int i, j;
i = left;
for (j = left + 1; j <= right; ++j) {
if (vec[j] < vec[left]) {
++i;
swap(vec[i], vec[j]);
}
}
swap(vec[left], vec[i]);
return i;
}
void quickSort(int vec[], int left, int right) {
int r;
if (right > left) {
r = partition(vec, left, right);
quickSort(vec, left, r - 1);
quickSort(vec, r + 1, right);
}
}
QuickSort da stdlib.h
#include
int compara(const void *pa , const void *pb){
int a = *(int *)pa;
int b = *(int *)pb;
return a-b;
}
qsort(v,n,sizeof(n) , compara);
tenho uma implementação em Java de bubble sort, inserction sort e selection sort.
public class Main {
public static void main(String[] args) {
int[] vetor = { 3, 2, 2, 1 };
System.out.println(Arrays.toString(bubbleSort(vetor)));
System.out.println(Arrays.toString(insertionSort(vetor)));
System.out.println(Arrays.toString(selectionSort(vetor)));
}
public static int[] bubbleSort(int vetor[]) {
for (int i = vetor.length; i >= 1; i--) {
for (int j = 1; j < i; j++) {
if (vetor[j - 1] > vetor[j]) {
int aux = vetor[j];
vetor[j] = vetor[j - 1];
vetor[j - 1] = aux;
}
}
}
return vetor;
}
public static int[] insertionSort(int[] vetor) {
for (int i = 0; i < vetor.length; i++) {
int valor = vetor[i];
int j = i - 1;
while (j >= 0 && vetor[j] >= valor) {
vetor[j + 1] = vetor[j];
j--;
}
vetor[j + 1] = valor;
}
return vetor;
}
public static int[] selectionSort(int[] vetor) {
for (int i = 0; i < vetor.length; i++) {
int indiceMinimo = i;
for (int j = i + 1; j < vetor.length; j++) {
if (vetor[j] < vetor[indiceMinimo]) {
indiceMinimo = j;
}
}
int valor = vetor[indiceMinimo];
vetor[indiceMinimo] = vetor[i];
vetor[i] = valor;
}
return vetor;
}
}
neste link existem mais exemplos