Podemos saber se uma coleção está quase classificada sem aplicar um algoritmo de classificação? - bubble-sort, classificação

No artigo da wikipedia sobre algoritmos de ordenação, http://en.wikipedia.org/wiki/Sorting_algorithm#Summaries_of_popular_sorting_algorithms em Bubble sort diz:A classificação de bolhas também pode ser usada eficientemente em uma lista de qualquer tamanho que esteja quase classificado (isto é, os elementos não estão significativamente fora do lugar)

Então, minha pergunta é: sem classificar a lista usando um algoritmo de classificação primeiro, como saber se que é quase classificado ou não?

Respostas:

Você está familiarizado com a classificação geral inferiorlimite? Você pode provar que, em um algoritmo de classificação baseado em comparação, qualquer algoritmo de classificação deve fazer comparações Ω (n log n) no caso médio. A maneira como você prova isso é através de um argumento teórico da informação. A ideia básica é que existem n! possíveis permutações da matriz de entrada, e desde que a única maneira que você pode aprender sobre qual permutação você tem é fazer comparações, você tem que fazer pelo menos lg n! comparações para ter certeza de que você conhece a estrutura de sua permutação de entrada.

Eu não tenho trabalhado a matemática sobre isso, mas euSuspeito que você poderia fazer argumentos semelhantes para mostrar que é difícil aprender o quão ordenado é um array específico. Essencialmente, se você não faz um grande número de comparações, então você não seria capaz de distinguir um array que "Na maior parte é ordenada a partir de uma matriz que é realmente muito longe de ordenada. Como resultado, todos os algoritmos que eu conheço dessa medida "classificação" demoram um bom tempo para fazê-lo.

Por exemplo, uma medida do nível de "classificação" em uma matriz é o número de inversões nessa matriz. Você pode contar o número de inversões em uma matriz no tempo O (n log n) usando um algoritmo de divisão e conquista baseado em mergesort, mas com esse tempo de execução você pode simplesmente ordenar a matriz.

Normalmente, a maneira que você sabe que o seuarray foi principalmente resolvido para saber algo a priori sobre como ele foi gerado. Por exemplo, se você estiver observando os dados de temperatura reunidos das 8h às 12h, é muito provável que os dados já estejam praticamente ordenados (modulo alguma variação na qualidade das leituras do sensor). Se os seus dados analisarem o preço das ações ao longo do tempo, é provável que sejam classificados principalmente a menos que a empresa tenha uma trajetória realmente instável. Alguns outros algoritmos também classificam parcialmente matrizes; por exemplo, não é incomum que implementações de quicksort parem ordenando quando o tamanho da matriz deixada para ordenar é pequeno e para seguir tudo com uma passada de ordenação de inserção final, desde então todo elemento não estará muito longe de sua posição final então.

Eu não acredito que exista qualquer medida padronizada de quão ordenado ou aleatório é um array.

Você pode criar sua própria medida - comoconte o número de pares adjacentes que estão fora de ordem (sugerido no comentário) ou conte o número de números maiores que ocorrem antes de números menores na matriz (isso é mais complicado do que um simples passo único).