MARK GROZEN-SMITH: Ola, eu son Mark Grozen-Smith, e este é Quicksort. Así como tipo de inserción e da burbulla sort, Quicksort é un algoritmo para ordenar unha lista ou unha matriz de cousas. Para simplificar, imos supor que os cousas son só números enteiros, pero saber que Quicksort traballa para máis que números. Inicio rápido é un pouco máis complicado de inserción ou burbulla, pero é tamén moito máis eficiente na maioría dos casos. Espere un segundo. El acaba de dicir "máis casos "non" todo "? Curiosamente, non. Non todos os problemas son os mesmos. Non hai problema con ese detalle, se non vin notación O gran aínda, pero Quicksort é un O (n ao cadrado) algoritmo no peor dos casos, só como inserción ou bubble sort. Con todo, el xeralmente actúa moito máis como unha m algoritmo analóxico antigo. Por que? Volveremos a iso máis tarde. Pero, polo de agora, imos só aprender Quicksort como funciona. 

Entón, imos camiñar por este Quicksorting array de enteiros de menor ao maior. Aquí temos os enteiros 6, 5, 1, 3, 8, 4, 7, 9, e 2. Primeiro, seleccione o elemento final de esa matriz - neste caso, dous - e chamar iso de "pivot". Logo nós comezar a ollar para dúas cousas - un, o menor índice, que vou referir como ir á dereita do a parede, e, dous, máis á esquerda elemento, que eu vou chamar de "actual elemento. "Que imos facer é mirar todos os outros elementos, outros que o pivote, e poñer todos os elementos menor que o pivote ao esquerda do muro e todos aqueles maior que o pivote ao dereita da pantalla. Entón, finalmente, imos soltar o pivote dereito na parede para poñelas entre todos os números menores que e todos os números máis grandes. 

Entón, imos facelo. Colla o 2, engada a parede no comezando, e chamar a 6 o "actual elemento. "Por iso, queremos mirar noso elemento actual, o 6. E xa que é maior que o 2, nós deixar alí para o dereita da pantalla. Logo pasamos a mirar o 5 como o noso elemento actual e ver que esta é, unha vez máis, maior que o pivote, de xeito que deixar onde está á dereita lado da parede. Nós seguir adiante. O noso elemento actual é agora 1 e - oh. Isto é diferente agora. O elemento actual é agora menor que o pivote, polo que queremos poñelas á esquerda da pantalla. Para iso, imos cambiar o elemento actual co menor índice de sentado á dereita do muro. Agora pasamos a parede por riba de un índice de xeito que o 1 está á esquerda lado do muro agora. 

Espera. Eu só confunde os elementos da parte dereita da pantalla, non foi? Non te preocupes. Iso é bo. O único que nos preocupa polo de agora é que todos estes elementos ao dereita do muro é maior que o pivote. Sen orde real é asumido aínda. 

Agora, de volta á clasificación. Entón, nós seguimos a mirar para o resto dos elementos. E neste caso, podemos ver que hai non hai outros elementos menor que o pivot, polo que deixalos todos na na parte dereita da pantalla. Por último, chegamos ao elemento actual e ver que é o pivote. Agora, isto significa que temos dous seccións da matriz, sendo o primeiro pequeno sobre o pivote e na parte esquerda do muro, eo segundo sendo maior que o pivote ao lado dereito da pantalla. Queremos poñer o elemento pivote entre os dous, e entón saberemos que o pivote está no seu dereito lugar ordenada final. Entón trocamos o primeiro elemento na parte dereita da pantalla, co pivote, e sabemos do pivote na súa posición correcta. 

A continuación, repita este proceso para o subarrays esquerda e á dereita do pivote. Xa que a última sub-disposición é só un elemento longo, sabemos que xa está ordenada, porque como pode estar fóra de solicitar se é só un elemento? Para o lado dereito da sub-disposición, temos ver que o pivote é 5, e a parede está á esquerda do 6. E o elemento actual tamén comeza como o 6. Así 6 é maior que 5. Nós deixar onde está a lado dereito da pantalla. Pasando agora, 3 é inferior a 5. Entón imos cambiar isto co primeiro elemento logo á dereita da pantalla. Agora, me mudei a parede ata un. Agora, pasar á 8. 8 é maior que 5, e por iso deixar. A 4 é inferior a 5, de xeito que cambie. E diante. E diante. 

Cada vez que repetir o proceso no lados da matriz da esquerda e da dereita. nós escoller un pivote e facer as comparacións e crear outro nivel de esquerda e subarrays dereita. Esta chamada recursiva continuará ata chegamos ao final cando temos dividido a matriz global en só subarrays de lonxitude 1. De alí, sabemos que a matriz é clasificada xa que cada elemento ten, polo nalgún momento, foi un pivote. Noutras palabras, para cada elemento, todos os números á esquerda son menores valores e todos os números ao dereito teñen maiores valores. 

Este método funciona moi ben se o valor do pivote é escollido aproximadamente no medio intervalo de valores da lista. Isto significaría que, despois de pasarmos elementos ao redor, hai preto de tantas elementos á esquerda do eixe de rotación como hai á dereita. E a natureza divide e conquista de Algoritmo Quicksort é entón levado aproveitar. Isto xera un tempo de execución de O (n log n,) o n porque temos que facer n menos 1 comparacións en cada xeración e rexistro n porque temos que dividir a lista log n veces. Con todo, no peor dos casos, este algoritmo realmente pode ser o (n cadrado.) Supoña en cada xeración, o pivote só acontece a ser o menor ou o máis grande dos números que estamos clasificación. Isto significaría romper a lista n veces e toma n menos 1 comparacións en cada momento. Así, o de n ao cadrado. 

Como podemos mellorar o método? Unha boa forma de mellorar o método é para reducir a probabilidade de que o tempo de execución é sempre certo o de n ao cadrado. Teña en conta que diso peor, peor escenario só pode ocorrer cando o pivote elixido é sempre a máis ou menor valor na matriz. Para garantir isto é menos probable de ocorrer, podemos atopar o pivote por escoller varios elementos e tomando o valor mediano. 

O meu nome é Mark Grozen-Smith, e este é CS50. 

Para simplificar, imos supor que os cousas son só números enteiros, pero saber que Quicksert - Quicksert? Sentímolo. 

Aquí temos os números enteiros 6, 5, 1, 3, 8, 4, 9. 

COLUMNA 1: Serio? 

COLUMNA 2: Non deixa por aí. 

COLUMNA 1: Serio?