Quicksort como un método de programación

En 1960, K. A. Hoar desenvolveu un método para a rápida clasificación de información, tornouse o máis famoso. Hoxe, é amplamente utilizado na programación, xa que ten unha morea de propiedades positivas: Pode ser usado para casos xerais, que esixe un pequeno aumento na memoria adicional, compatible con diferentes tipos de listas e doado de aplicar. Pero hai desvantaxes, que ten quicksort: usando traballo permitiu unha morea de erros, e é un pouco inestable.

Con todo, é a versión máis estudados. Tras a primeira Hoare pago, moitos fan o estudo denso. gran base estableceuse en cuestións teóricas de atopar o tempo gastado no traballo, que é sostida por evidencias empíricas. Houbo propostas reais para mellorar o algoritmo básico e maior velocidade.

Quicksort é moi común, se pode atopar en todas partes. Na súa base ao método é aplicado TList.Sort, presente en todas as versións (excepto 1) Delphi, a función de biblioteca de tempo que levou para completar, qsort en C ++.

O principio básico de funcionamento pode formularse como un "dividir e conquistar". Ocorre quebrando a lista en dous grupos e clasificaranse para cada parte de seu. Segue-se que máis atención debe ser dada ao proceso de separación, durante o cal ocorre o seguinte: é determinado por un elemento de base e concepto reorganizados súa lista enteira. Construído á esquerda dun grupo de candidatos, cuxo valor é menor que o resto regras de transferencia. Acontece que o principal elemento da lista ordenada está no seu debido lugar. A fase seguinte - un desafío funcións de ordenación recursivas a ambos os dous lados dos elementos en relación á base. Remata o proceso funciona só a lista contén só un elemento, que debe ser ordenada. Así, a fin de dominar unha función de programación como unha especie rápida, é necesario coñecer o traballo de algoritmos de nivel inferior: a) a elección do membro de base; b) unha lista de intercambio máis eficaz para producir dous conxuntos con valores menores e maiores.

Familiarizarse con os primeiros principios. Ao escoller o membro de base, que idealmente ser seleccionado a partir da lista de media. A continuación, no contraataque divídese en dúas metades iguais. Só calcular o valor medio da lista é moi difícil, por iso mesmo a clasificación máis rápido ignora este lado cálculo. Pero a elección do elemento básico co valor máximo ou mínimo - tampouco é a mellor opción. No caso de tal determinación dunha crea listas baleiras Garantirase, eo segundo completo. De aí a conclusión de que, como o membro de base debe ser escollido o que está máis preto da media, pero o máximo e mínimo.

Xa que a elección é determinada, pode avanzar no algoritmo de descomposición. Este así chamado lazos internos clasificación rápida. Todo está construído en dous índices de acceso rápido: primeiro pasar por riba dos elementos de esquerda a dereita, o segundo, pola contra, de dereita a esquerda. Comeza dereito execución da operación: o índice está na lista e comparar todos os valores para o principal. O ciclo está completo cando o elemento é inferior ou igual ao da liña de base. É dicir, hai unha comparación e diminúe o valor do índice. Na man esquerda cando o traballo remate maior ou igual valor. Aquí, o valor de comparación aumenta.

Nesta fase do algoritmo de particionamento que comprende quicksort, dúas situacións poden xurdir. A primeira é que o índice da esquerda é menor que a dereita. Isto indica un erro, entón hai elementos en que se indica na lista están á orde errada. Saída - cambiar os seus lugares. A segunda situación é cando tanto da columna é igual ou cruzado. Isto indica unha separación exitosa da lista, é dicir, o traballo xa está concluído.