Algoritmos de ordenação

1/8

Desde os primórdios da computação, o problema de ordenação tem atraído um grande número de

pesquisas, talvez devido à complexidade de resolvêlo

de forma eficiente, apesar de sua declaração simples

e familiar. Por exemplo, foi analisado tipo bolha tão cedo quanto 1956. Um limite fundamental de

comparação triagem algoritmos é que eles exigem tempo linearithmic O

,

no pior caso, embora não seja

possível um melhor desempenho em dados reais, e com base na comparação de algoritmos, tais como a

contagem de classificação, pode ter um melhor desempenho. Embora muitos considerem que classifica um

problema resolvido algoritmos

asymptotically ideais são conhecidos desde meados do século 20 novos

algoritmos úteis estão ainda a ser inventado, com o namoro agora amplamente utilizados Timsort a 2002,

e a biblioteca tipo a ser publicado pela primeira vez em 2006.

Algoritmos de ordenação são predominantes nas aulas de ciência da computação introdutória, onde a

abundância de algoritmos para o problema fornece uma introdução suave para uma variedade de

algoritmos conceitos fundamentais, tais como a notação O grande, dividir e conquistar algoritmos,

estruturas de dados, tais como pilhas e árvores binárias, algoritmos aleatórios, melhor, pior e análise média

caso, as compensações espaço de tempo e limites superiores e inferiores.

Classificação

Algoritmos de ordenação muitas vezes são classificados por:

Complexidade computacional das comparações elemento em termos do tamanho da lista. Para

algoritmos típicos de classificação de série bom comportamento é O, com tipo paralelo em O, e

mau comportamento é um comportamento O. Ideal para uma espécie de série é O, mas isso

não é possível no caso da média, triagem paralelo ideal é de triagem com base O. Comparação

algoritmos, que avaliam os elementos da lista através de uma operação de comparação chave

abstrato, é necessário pelo menos comparações S para a maioria das entradas.

Complexidade computacional de swaps.

O uso de memória. Em particular, alguns algoritmos de ordenação são "in place". A rigor, uma

no lugar espécie precisa de apenas O memória além dos itens que estão sendo ordenadas; às

vezes, O (log) de memória adicional é considerado "in place".

Recursão. Alguns algoritmos são ou recursiva recursiva ou não, enquanto outros podem ser

ambos.

Estabilidade: algoritmos de ordenação estáveis manter a ordem relativa de registros com

chaves iguais.

Querendo ou não eles são uma espécie de comparação. Uma espécie de comparação examina

os dados apenas comparando dois elementos com um operador de comparação.

Método geral: inserção, o intercâmbio, a seleção, a fusão, etc. tipos de câmbio incluem bubble

sort e quicksort. Tipos de seleção incluem agitador tipo e heapsort. Também se o algoritmo é

de série ou em paralelo. O restante desta discussão se concentra quase exclusivamente sobre

algoritmos de série e assume operação serial.

Adaptabilidade: Quer ou não o presortedness da entrada afeta o tempo de execução.

Algoritmos que levar isso em conta são conhecidos por ser adaptável.

Estabilidade

Ao classificar alguns tipos de dados, apenas parte dos dados é examinado para determinar a ordem de

classificação. Por exemplo, no cartão de triagem exemplo para a direita, os cartões estão sendo

selecionados por seu posto, e seu terno está sendo ignorada. Isso permite a possibilidade de múltiplas



27/05/2015 Algoritmo de ordenação, classificação, comparação de algoritmos, algoritmos de ordenação Populares, padrões de uso de memória e índice de cl…

data:text/html;charset=utf8,%

3Cp%20style%3D%22marginbottom%

3A%2015px%3B%20color%3A%20rgb(126%2C%20126%2C%20126)%3B%20font…

2/8

versões corretamente ordenados diferentes da lista original. Algoritmos de ordenação estáveis escolher um

destes, de acordo com a seguinte regra: se dois itens são considerados iguais, como os dois 5 cartões,

então sua ordem relativa serão preservados, de modo que, se um veio antes do outro na entrada, mas

também irá vir antes do outro na saída.

Mais formalmente, os dados que estão sendo classificados pode ser representado como um registro ou

tupla de valores, e parte dos dados que é usado para classificação é chamado a chave. No exemplo o

cartão, cartões são representados como um registro, e a chave é o rank. Um algoritmo de ordenação é

estável se sempre que houver dois registros R e S com a mesma chave, e R S aparece antes na lista

original, em seguida, R sempre aparecerá antes S na lista de classificação.

Quando