24

Sabe-se que existem várias formas de se ordenar os dados de uma coleção, alguns exemplos são os famosos bubble sort, insertion sort e selection sort.

Eu ouvi dizer que alguns algoritmos são estáveis e outros não. O que define um algoritmo de ordenação estável? Algum dos três do exemplo são estáveis?

Se possível eu gostaria de algum exemplo de algum algoritmo de ordenação que seja estável e uma representação em código que fosse fácil de ler (pseudo-linguagem, Python ou C#).

2
  • 5
    Ora ai está um tema bem complicado, a ordenação de dados.
    – Jorge B.
    Commented 8/03/2017 às 12:18
  • Lembre que o MIB é estável. Merge Sort Insertion Sort Bubble Sort Commented 13/08 às 15:44

2 Respostas 2

19

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

14

É importante onde tenha dados repetidos no roll todo. A classificação ocorre baseada em alguma chave que fornece o elemento base para a decisão de ordem. Se existirem dois elementos com a mesma chave um algoritmo estável colocará antes o elemento que aparece em primeiro antes do elemento repetido que apareceu em seguida, então acaba que a a posição absoluta do elemento de certa forma acaba fazendo parte da chave. Um algoritmo não estável nada garante a ordem dos elementos repetidos.

Mas não precisa usar a posição como desempatador, pode ser uma segunda chave definida, ou uma terceira, e assim por diante.

O mecanismo exato para se garantir essa característica não é definido, em tese é possível fazer com que qualquer algoritmo produza um resultado estável com o mecanismo secundário de apoio, mas obviamente se for para fazer isto é melhor usar outro algoritmo que faça o desejado de uma vez. Usar um segundo algoritmo fará ter um custo extra de processamento. Um exemplo é o Quicksort, que é o algoritmo mais popular, normalmente é instável, mas existe versão dele que consegue obter estabilidade com um custo extra.

É comum que um algoritmo instável possa obter um desempenho um pouco melhor que os estáveis pelo menos em certas situações, então pode ser uma boa escolha se não houver o requisito de ordenação dos repetidos. Isto pode ser crítico de acordo com a distribuição das chaves. Pensa em uma coleção de dados cujas chaves sejam todas repetidas (obviamente já está ordenada), tem algoritmo que pode ordenar em complexidade O(N), outros levarão o mesmo tempo, ou um meio termo se nenhum fosse repetido. Assim como tem algoritmos que se beneficiarão de uma coleção já ordenada enquanto outros não. Se é garantido que não há repetições, a escolha também não se importa com isso.

A Wikipedia tem um bom exemplo mostrando a preservação da ordem pela posição em algoritmo estável e não estável:

ALgoritmo estável/não estável

Note que houve um desempate pelo naipe.

E também tem a demonstração quando o desempatador é uma segunda chave, então aqui primeiro ordena os naipes e depois os números:

Algoritmo com chave composta

Lá no artigo tem uma lista dos algoritmos classificando-os por estáveis ou não estáveis.

Exemplo que Quicksort que é instável em C# pode ser visto no Rosetta Code.

Exemplo que Merge sorte que é estável em C# pode ser visto no Rosetta Code.

Lá pode ser visto exemplos de outras linguagens e outros algoritmos que possuem a mesma característica.

3
  • Adoro suas respostas @bigown. "Um algoritmo não estável nada garante a ordem dos elementos repetidos". Isso quer dizer que o algoritmo pode errar? Dar o resultado errado? Commented 14/03/2017 às 17:09
  • 3
    @NotTheRealHemingway Obrigado. não me lembro de todo o texto, mas acho que está escrito algo sobre isso aí. Não é resultado errado, é o esperado, erro só se fosse inesperado. Neste tipo de algoritmo é especificado que no momento que ache elementos repetidos, a ordem desses repetidos não é garantida. No algoritmo estável é garantido que eles aparecerão na mesma ordem que estava originalmente na coleção. Isso só vale para os repetidos. Então tem problema que os repetidos podem aparecer em qualquer ordem, em problema que eles precisam manter a ordem dos repetidos que estava antes de classificar.
    – Maniero
    Commented 14/03/2017 às 17:14
  • @bigown é um Big Data, segura meu +1 Commented 16/03/2017 às 14:31

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .