MARK GROZEN-SMITH: Oi, eu sou Mark Grozen-Smith, e este é Quicksort. Assim como tipo de inserção e da bolha sort, Quicksort é um algoritmo para ordenar uma lista ou uma matriz de coisas. Para simplificar, vamos supor que os coisas são apenas números inteiros, mas saber que Quicksort trabalha para mais do que apenas números. Início rápido é um pouco mais complicado de inserção ou bolha, mas é também muito mais eficiente na maioria dos casos. Espere um segundo. Ele acabou de dizer "mais casos, "não" todos "? Curiosamente, não. Nem todos os casos são os mesmos. Não se preocupe com esse detalhe, se você não vi notação O grande ainda, mas Quicksort é um O (n ao quadrado) algoritmo na pior das hipóteses, apenas como inserção ou bubble sort. No entanto, ele geralmente age muito mais como uma m algoritmo analógico antigo. Por quê? Voltaremos a isso mais tarde. Mas, por enquanto, vamos apenas aprender Quicksort como funciona. 

Então, vamos caminhar por este Quicksorting array de inteiros de menor para o maior. Aqui temos os inteiros 6, 5, 1, 3, 8, 4, 7, 9, e 2. Primeiro, escolha o elemento final de essa matriz - neste caso, dois - e chamar isso de "pivot". Em seguida, nós começar a olhar para duas coisas - um, o menor índice, que vou me referir como ficar à direita do a parede, e, dois, mais à esquerda elemento, que eu vou chamar de "atual elemento. "O que nós vamos fazer é olhar todos os outros elementos, outros que o pivô, e colocar todos os elementos menor do que o pivô ao esquerda da parede e todos aqueles maior do que o pivô ao direita da parede. Então, finalmente, vamos soltar o pivô direito na parede para colocá-lo entre todos os números menores do que e todos os números maiores. 

Então, vamos fazer isso. Pegue o 2, coloque a parede no começando, e chamar a 6 o "atual elemento. "Por isso, queremos olhar para nosso elemento atual, o 6. E já que é maior do que o 2, nós deixá-lo lá para o direita da parede. Em seguida, passamos a olhar para o 5 como o nosso elemento atual e ver que esta é, mais uma vez, maior do que o pivô, de modo que deixá-lo onde está à direita lado da parede. Nós seguir em frente. Nosso elemento atual é agora 1 e - oh. Isso é diferente agora. O elemento atual é agora menor do que o pivô, por isso, queremos colocá-lo para a esquerda da parede. Para fazer isso, vamos mudar o elemento atual com o menor índice de sentado à direita do muro. Agora, passamos a parede acima de um índice de modo que o 1 está à esquerda lado da parede agora. 

Espere. Eu só confunde os elementos da lado direito da parede, não foi? Não se preocupe. Isso é bom. A única coisa que nos preocupamos por enquanto é que todos estes elementos para o direita da parede é maior que o pivô. Sem ordem real é assumido ainda. 

Agora, de volta para a classificação. Então, nós continuamos a olhar para o resto dos elementos. E, neste caso, vemos que há não há outros elementos menor do que o pivot, por isso deixá-los todos em no lado direito da parede. Finalmente, chegamos ao elemento atual e ver que ele é o pivô. Agora, isso significa que temos dois seções da matriz, sendo o primeiro pequeno sobre o pivô e no lado esquerdo do muro, eo segundo sendo maior do que o pivô ao lado direito da parede. Queremos colocar o elemento pivô entre os dois, e então saberemos que o pivô está no seu direito lugar ordenada final. Então trocamos o primeiro elemento na lado direito da parede, com o pivô, e sabemos do pivô na sua posição correta. 

Em seguida, repita este processo para o subarrays esquerda e à direita do pivô. Uma vez que a última sub-disposição é apenas um elemento longo, sabemos que já está ordenada, porque como você pode estar fora de encomendar se você é apenas um elemento? Para o lado direito da sub-disposição, temos ver que o pivô é 5, e a parede está à esquerda do 6. E o elemento atual também começa como o 6. Assim 6 é maior do que 5. Nós deixá-lo onde está a lado direito da parede. Passando agora, 3 é inferior a 5. Então vamos mudar isso com o primeiro elemento logo à direita da parede. Agora, me mudei a parede até um. Agora, passar para a 8. 8 é maior do que 5, e por isso deixá-lo. A 4 é inferior a 5, de modo que ele mude. E diante. E diante. 

Cada vez que repetir o processo no os lados da matriz da esquerda e da direita. nós escolher um pivô e fazer as comparações e criar um outro nível de esquerda e subarrays direita. Esta chamada recursiva continuará até chegamos ao fim quando temos dividido a matriz global em apenas subarrays de comprimento 1. De lá, sabemos que a matriz é classificada porque cada elemento tem, pelo algum momento, sido um pivô. Em outras palavras, para cada elemento, todos os números à esquerda são menores valores e todos os números para o direito têm maiores valores. 

Este método funciona muito bem se o valor do pivô é escolhido aproximadamente no meio intervalo de valores da lista. Isto significaria que, depois de passarmos elementos ao redor, há cerca de tantas elementos à esquerda do eixo de rotação como existem para a direita. E a natureza divide e conquista da Algoritmo Quicksort é então levado aproveitar. Isso cria um tempo de execução de O (n log n,) o n porque nós temos que fazer n menos 1 comparações em cada geração e log n porque temos que dividir a lista log n vezes. No entanto, no pior dos casos, este algoritmo pode realmente ser o (n quadrado.) Suponha em cada geração, o pivô só acontece a ser o menor ou o maior dos números que estamos classificação. Isto significaria quebrar a lista n vezes e tomada n menos 1 comparações a cada momento. Assim, o de n ao quadrado. 

Como podemos melhorar o método? Uma boa maneira de melhorar o método é para reduzir a probabilidade de que o tempo de execução é sempre verdade o de n ao quadrado. Lembre-se disso pior, pior cenário só pode acontecer quando o pivô escolhido é sempre a maior ou menor valor na matriz. Para garantir isso é menos provável de acontecer, podemos encontrar o pivô por escolher vários elementos e tomando o valor mediano. 

Meu nome é Mark Grozen-Smith, e este é CS50. 

Para simplificar, vamos supor que os coisas são apenas números inteiros, mas saber que Quicksert - Quicksert? Desculpe. 

Aqui temos os números inteiros 6, 5, 1, 3, 8, 4, 9. 

COLUNA 1: Sério? 

COLUNA 2: Não pára por aí. 

COLUNA 1: Sério?