Estabilidade nos algoritmos de ordenação – um tratamento da igualdade

Onel Harrison Blocked Desbloquear Seguir Seguindo 28 de dezembro

Algoritmos estão no coração da ciência da computação. Algoritmos usados para classificar são alguns dos mais fundamentais, úteis e, consequentemente, onipresentes.

Algoritmo – um conjunto finito de etapas não ambíguas para resolver um problema específico.

Constantemente e muitas vezes inconscientemente classificamos e confiamos na ordem dos objetos agrupados. Por exemplo, classificamos as tarefas em uma lista de acordo com a prioridade. Nós empilhar livros nas prateleiras por sua altura. Classificamos as linhas em uma planilha ou banco de dados ou confiamos na ordem alfabética das palavras em um dicionário. Às vezes, até percebemos um certo tipo de beleza em arranjos ordenados.

Foto de Mikael Kristenson em Unsplash

Como programadores, saber como classificamos é importante porque afeta o aspecto de um arranjo ordenado. Nem todos os tipos ordenam os objetos da mesma maneira! Devido a isso, os resultados das operações de classificação diferem com base nos algoritmos usados. Se isso não for reconhecido, poderemos surpreender a nós mesmos ou às pessoas que usam nosso software.

A estabilidade dos algoritmos de classificação é uma das propriedades distintivas entre eles. Ele lida com o modo como o algoritmo trata itens comparáveis com chaves de classificação iguais.

Chave de classificação – Uma chave usada para determinar a ordem dos itens em uma coleção, por exemplo, idade, altura, posição no alfabeto, etc.

Um algoritmo de classificação estável mantém a ordem relativa dos itens com chaves de classificação iguais. Um algoritmo de classificação instável não. Em outras palavras, quando uma coleção é classificada com um algoritmo de classificação estável, os itens com as mesmas chaves de classificação preservam sua ordem depois que a coleção é classificada.

Um exemplo, código e uma demonstração

Imagem mostrando o efeito da classificação estável

A imagem acima ilustra o efeito de uma classificação estável. À esquerda, os dados foram classificados em ordem alfabética por nome. Depois de classificar os dados por Grade, você pode ver que a ordem alfabética dos nomes foi mantida para cada linha com o mesmo Grade.

Imagem mostrando o efeito da classificação instável

Com um tipo instável, não há garantia de que a ordem alfabética seja mantida, conforme mostrado na imagem acima.

Você nem sempre precisa de um tipo estável

Saber se o tipo que você usa é estável é particularmente importante. Especialmente em situações em que seus dados já têm algum pedido que você gostaria de manter ao classificá-lo por outra chave de classificação. Por exemplo, você tem linhas em uma planilha contendo dados do aluno que, por padrão, são classificados por nome. Você também gostaria de classificá-lo por notas, mantendo a ordem de classificação dos nomes.

Por outro lado, a estabilidade do tipo não importa quando as chaves de classificação dos objetos em uma coleção são os objetos em si – uma matriz de inteiros ou cadeias de caracteres, por exemplo – porque não podemos dizer a diferença entre os duplicados chaves.

 // JavaScript 
 // $ 5 dólares se você puder dizer corretamente quais 4 na classificação 
// array foi o primeiro 4 quando a matriz não foi classificada.
 números var = [5, 4, 3, 4, 9]; 
numbers.sort (); // [3, 4, 4, 5, 9]
 // Uma segunda viagem ao redor do mundo, cortesia do Flash, para 
// quem quer que me diga corretamente qual 'harry' no array ordenado foi
// o segundo 'harry' no array indiferenciado.
 var names = ['harry', 'barry', 'harry', 'cisco']; 
names.sort (); // ['barry', 'cisco', 'harry', 'harry']

Os tipos estão em toda parte – conheça seus tipos

É muito fácil descobrir se a classificação padrão em sua linguagem de programação ou biblioteca é estável. A documentação deve incluir esta informação. Por exemplo, a ordenação padrão é estável em Python , instável em Ruby e indefinida em JavaScript (depende da implementação do navegador).

Aqui estão alguns algoritmos de classificação comuns e sua estabilidade:

  • Tipo de Inserção – Estável
  • Seleção de seleção – instável
  • Bubble Sort – Estável
  • Merge Sort – Estável
  • Tipo de Shell – Instável
  • Timsort – Estável

Veja a Wikipedia para uma lista mais exaustiva.

É tempo de demonstração

Esta demonstração mostra o efeito do uso de um algoritmo de classificação estável (ordenação de inserção) e instável (classificação de seleção) para classificar uma pequena tabela de dados. Eu me diverti um pouco e praticamente revisei o React enquanto construí isso. Dê uma olhada na fonte .

Qual é o próximo?

Se você tem sede de mais conhecimento sobre a estabilidade de outros algoritmos de classificação, a Wikipedia possui uma boa tabela de comparação e informações adicionais sobre algoritmos de classificação bem conhecidos.

Até a próxima vez, paz.

Aprendeu algo novo ou gostou de ler este artigo? Aplauda-o ?, compartilhe-o para que os outros possam ler também e siga adiante para mais. Sinta-se livre para deixar um comentário também.

Estabilidade nos algoritmos de ordenação – um tratamento da igualdade

Onel Harrison 28 de dezembro

Algoritmos estão no coração da ciência da computação. Algoritmos usados para classificar são alguns dos mais fundamentais, úteis e, consequentemente, onipresentes.

Algoritmo – um conjunto finito de etapas não ambíguas para resolver um problema específico.

Constantemente e muitas vezes inconscientemente classificamos e confiamos na ordem dos objetos agrupados. Por exemplo, classificamos as tarefas em uma lista de acordo com a prioridade. Nós empilhar livros nas prateleiras por sua altura. Classificamos as linhas em uma planilha ou banco de dados ou confiamos na ordem alfabética das palavras em um dicionário. Às vezes, até percebemos um certo tipo de beleza em arranjos ordenados.

Foto de Mikael Kristenson em Unsplash

Como programadores, saber como classificamos é importante porque afeta o aspecto de um arranjo ordenado. Nem todos os tipos ordenam os objetos da mesma maneira! Devido a isso, os resultados das operações de classificação diferem com base nos algoritmos usados. Se isso não for reconhecido, poderemos surpreender a nós mesmos ou às pessoas que usam nosso software.

A estabilidade dos algoritmos de classificação é uma das propriedades distintivas entre eles. Ele lida com o modo como o algoritmo trata itens comparáveis com chaves de classificação iguais.

Chave de classificação – Uma chave usada para determinar a ordem dos itens em uma coleção, por exemplo, idade, altura, posição no alfabeto, etc.

Um algoritmo de classificação estável mantém a ordem relativa dos itens com chaves de classificação iguais. Um algoritmo de classificação instável não. Em outras palavras, quando uma coleção é classificada com um algoritmo de classificação estável, os itens com as mesmas chaves de classificação preservam sua ordem depois que a coleção é classificada.

Um exemplo, código e uma demonstração

Imagem mostrando o efeito da classificação estável

A imagem acima ilustra o efeito de uma classificação estável. À esquerda, os dados foram classificados em ordem alfabética por nome. Depois de classificar os dados por Grade, você pode ver que a ordem alfabética dos nomes foi mantida para cada linha com o mesmo Grade.

Imagem mostrando o efeito da classificação instável

Com um tipo instável, não há garantia de que a ordem alfabética seja mantida, conforme mostrado na imagem acima.

Você nem sempre precisa de um tipo estável

Saber se o tipo que você usa é estável é particularmente importante. Especialmente em situações em que seus dados já têm algum pedido que você gostaria de manter ao classificá-lo por outra chave de classificação. Por exemplo, você tem linhas em uma planilha contendo dados do aluno que, por padrão, são classificados por nome. Você também gostaria de classificá-lo por notas, mantendo a ordem de classificação dos nomes.

Por outro lado, a estabilidade do tipo não importa quando as chaves de classificação dos objetos em uma coleção são os objetos em si – uma matriz de inteiros ou cadeias de caracteres, por exemplo – porque não podemos dizer a diferença entre os duplicados chaves.

 // JavaScript 
 // $ 5 dólares se você puder dizer corretamente quais 4 na classificação 
// array foi o primeiro 4 quando a matriz não foi classificada.
 números var = [5, 4, 3, 4, 9]; 
numbers.sort (); // [3, 4, 4, 5, 9]
 // Uma segunda viagem ao redor do mundo, cortesia do Flash, para 
// quem quer que me diga corretamente qual 'harry' no array ordenado foi
// o segundo 'harry' no array indiferenciado.
 var names = ['harry', 'barry', 'harry', 'cisco']; 
names.sort (); // ['barry', 'cisco', 'harry', 'harry']

Os tipos estão em toda parte – conheça seus tipos

É muito fácil descobrir se a classificação padrão em sua linguagem de programação ou biblioteca é estável. A documentação deve incluir esta informação. Por exemplo, a ordenação padrão é estável em Python , instável em Ruby e indefinida em JavaScript (depende da implementação do navegador).

Aqui estão alguns algoritmos de classificação comuns e sua estabilidade:

  • Tipo de Inserção – Estável
  • Seleção de seleção – instável
  • Bubble Sort – Estável
  • Merge Sort – Estável
  • Tipo de Shell – Instável
  • Timsort – Estável

Veja a Wikipedia para uma lista mais exaustiva.

É tempo de demonstração

Esta demonstração mostra o efeito do uso de um algoritmo de classificação estável (ordenação de inserção) e instável (classificação de seleção) para classificar uma pequena tabela de dados. Eu me diverti um pouco e praticamente revisei o React enquanto construí isso. Dê uma olhada na fonte .

Qual é o próximo?

Se você tem sede de mais conhecimento sobre a estabilidade de outros algoritmos de classificação, a Wikipedia possui uma boa tabela de comparação e informações adicionais sobre algoritmos de classificação bem conhecidos.

Até a próxima vez, paz.

Aprendeu algo novo ou gostou de ler este artigo? Aplauda-o ?, compartilhe-o para que os outros possam ler também e siga adiante para mais. Sinta-se livre para deixar um comentário também.