Esses termos são usados em algumas estruturas de dados para definir como os elementos são inseridos e mantidos, o que quer dizer cada uma? Sorted e ordered quer dizer a mesma coisa? Unordered quer dizer que é aleatório?
1 Resposta
Ordered
Ou ordenado, significa que a coleção de dados da estrutura está em alguma ordem. Em geral isso significa que a ordem de entrada é usada. Mas não é definido que seja exatamente assim, apenas que tem uma ordem. O termo é usado quando independentemente do valor adicionado no elemento, ele é colocado em alguma ordem.
Na maioria dos casos os mesmos dados entrados em ordem diferente produzirá um resultado diferente.
O array é o melhor exemplo deste tipo de estrutura. Mas a maioria das estruturas são ordenadas de alguma forma.
Unordered
Ou não ordenado, significa que os elementos não tem uma ordem claramente definida. Não significa que seja aleatório, e em geral você poderá listar todos os elementos e ter o mesmo resultado em todas as vezes que o fizer nos mesmos dados, mas como eles virão não tem uma definição. Não há garantias de que ordem seja esta.
Isso é detalhe de implementação. Pode ser que na próxima versão não esteja na mesma ordem. Pode até ser que na próxima execução não esteja.
Por exemplo em uma tabela de espalhamento, a função de hash não determina o índice, ela determina um código que será usado para achar um índice, o índice depende de alguns fatores, entre eles o tamanho da estrutura. Haverá uma ordem, ela não será aleatória, mas não é garantido que ela sempre será assim com o mesmo roll de dados entrado, então desconsidera-se que ela exista. Mesmo que ela permaneça igual, ela não pode ser considerada relevante como característica daquela estrutura.
As diferenças podem ocorrer por causa do compilador e versão utilizados, biblioteca, sistema operacional, hardware, configuração, ordem de entrada, volume de dados no momento e até versão do código que cria os objetos que são elementos desta coleção. Não importa o motivo, não confie na ordem que estão dispostos.
Não há garantias que seja a ordem de entrada dos valores, que a chave seja uma sequência, que seja uma ordem de acordo com seus valores ou chaves. O que pode enganar as pessoas, e por isso eu sempre digo: funcionar é diferente de estar certo.
Mesmo que observe uma certa ordem não tome como algo estável. Não confie no que você observa, nos bastidores pode ser diferente.
Existe o não ordenado aleatório também.
Uma tabela hash é o melhor exemplo, pelo menos sob certo ponto de vista.
Sorted
Ou classificado significa que há uma ordem definida por um critério previamente estabelecido baseado no valor do elemento inserido na coleção de dados. Esse valor pode ser uma chave ou o valor principal. Então toda coleção classificada também é ordenada.
Uma árvore, nas suas várias formas, é o melhor exemplo disto.
Algumas estruturas que são normalmente ordenadas podem acabar tendo seus dados classificados, mas não quer dizer que a estrutura seja considerada classificada, apenas aquela instância naquele momento tem esta característica, é circunstancial. Então para uma estrutura ser considerada sorted ela deve garantir essa condição. Em geral há uma chave que determine a classificação, desde que a chave seja considerada como parte do valor do elemento.
Um array tem uma chave classificada, que é seu índice, mas ele não faz parte do valor do elemento.
Uma tabela de banco de dados é ordenada, se ela tiver um ID
como chave, e isso é quase obrigatório, pode ser considerada classificada também. Um índice é classificado, pelo menos a maioria deles.
Outras características
Independente destas formas é possível entender as coleções como mono ou multivaloradas, onde se permite que a chave ou valor possa se repetir, neste caso precisa analisar também se os repetidos possuem ordem ou não, se são classificados ou não em seu subconjunto.
Se os dados são heterogêneos como lida com a ordem ou classificação?
Certamente estou deixando passar alguma coisa.
Confusão de termos
É muito comum, eu mesmo faço isso, as pessoas usarem o termo ordenado quando na verdade querem dizer classificado. O que significa que a tag ordenação está quase sempre errada nas perguntas (por isso ela foi renomeada).
-
Tenho um pouco de dificuldade de entender o conceito de unordered. Se uma função de hash vai determinar o índice do elemento numa array, de certa maneira ela está determinando uma ordem. Não? Commented 24/01/2018 às 18:56
-
@bfavaretto demorei mas editei, pena que eu esqueci algo importante que ia postar :)– Maniero ♦Commented 31/01/2018 às 12:46
-