Ordenação

tal que:

a1< a2 < … < an

para alguma relação de ordem.

Algumas ordens são facilmente definidas. Por exemplo, a ordem numérica, ou a ordem alfabética - crescente ou decrescente. Contudo, existem ordens, especialmente de dados compostos, que podem ser não triviais de se estabelecer.
A Grande maioria das ordenações, são feita a partir da chamada busca binaria que é um algoritmo de busca em vetores que segue o “paradigma” de divisão de conquista.
Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado a chamada chave com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor. Além de existir a busca binaria, quando falamos de algortmos de ordenação existem mais dois metodos de “buscas” que são a Bogosort e a Buscar Linear.
A Bogsort, na qual também é chamada de bozo sort, blort sort e vai-na sort ou até mesmo estou com sort é um algoritmo de ordenação extremamente ineficiente, baseado na reordenação aleatória dos elementos. Não é utilizado na prática, como contrução de um programa mas pode ser usado no ensino de algorítmos mais eficientes. Seu nome veio do engraçado termo quantum bododynamics e, ultimamente, a palavra bogus esse algoritmo é probabilistico por natureza. Se todos os elementos a serem ordenados são distintos, a complexidade esperada é.
O tempo exato de execução esperado depende do quantos diferentes valores de elementos ocorrem, e quantas vezes cada um deles ocorre, mas para casos não triviais o tempo esperado de execução é exponencial ou super-exponencial a. Ele termina pela mesma razão do Teorema do macaco infinito, existe alguma probabilidade de que aconteça a permutação correta, dado que em