MARCA GROZEN-SMITH: Hola, soy Marcos Grozen-Smith, y esta es la ordenación rápida. Al igual que la ordenación por inserción y la burbuja especie, la ordenación rápida es un algoritmo para ordenar una lista o una matriz de cosas. Para simplificar, vamos a suponer que los las cosas son sólo números enteros, pero sabemos que trabaja para la ordenación rápida más allá de los números. Inicio rápido es un poco más complicado de inserción o de burbujas, pero es también mucho más eficiente en la mayoría de los casos. Espera un segundo. ¿Acaba de decir "más casos ", no" todos "? Curiosamente, ninguna. No todos los casos son la misma. No te preocupes por este detalle si no han visto la notación O grande todavía, pero Ordenación rápida es una operación O (n al cuadrado) algoritmo en el peor, al igual que inserción o especie de burbuja. Sin embargo, por lo general actúa mucho más como un viejo m algoritmo analógico. ¿Por qué? Nos pondremos en contacto con eso más tarde. Pero por ahora, vamos a aprender cómo funciona la ordenación rápida. 

Así que vamos a caminar a través de este Quicksorting matriz de enteros de menor a más grande. Aquí tenemos los enteros 6, 5, 1, 3, 8, 4, 7, 9, y 2. En primer lugar, elegimos el elemento final de esta matriz - en este caso, dos - y llamar a que el "pivote". A continuación, se empezar a tener en cuenta dos cosas - uno, el índice más bajo, lo que me referiré a como mantenerse a la derecha del la pared, y, dos, el más a la izquierda elemento, que voy a llamar a la "corriente elemento. "Lo que vamos a hacer es buscar todos los otros elementos, otros que el pivote, y poner todos los elementos menor que el pivote para la izquierdo de la pared y todos aquellos mayor que el pivote para la derecho de la pared. Entonces, finalmente, nos dejaremos caer el pivote justo en esa pared para poner entre todos los números más pequeños de lo que y todos los números más grandes. 

Así que vamos a hacer eso. Levante el 2, poner la pared en la comenzando, y llame al 6 la "corriente elemento ". Así que queremos ver nuestro elemento actual, el 6. Y puesto que es más grande que el 2, lo dejamos ahí para la derecho de la pared. A continuación, pasamos a mirar el 5 como nuestro elemento actual y ver que esta es, de nuevo, más grande que el de pivote, por lo que dejarlo donde está a la derecha lado de la pared. Seguimos adelante. Nuestro elemento actual es ahora 1, y - oh. Esto es diferente ahora. El elemento actual es ahora menor que el pivote, por lo que queremos ponerlo a la izquierda de la pared. Para ello, vamos a cambiar la elemento actual con el índice más bajo sentado justo a la derecha de la pared. Ahora, pasamos la pared hasta un índice por lo que el 1 es a la izquierda lado de la pared ahora. 

Espere. Acabo confundido los elementos de la lado derecho de la pared, ¿no? No se preocupe. Eso está bien. Lo único que nos importa por ahora es que todos estos elementos a la derecho de la pared son más grandes que el pivote. No hay pedido actual se asume todavía. 

Ahora, de vuelta a la clasificación. Así que continuamos mirando el resto de los elementos. Y en este caso, vemos que hay no hay otros elementos menos que el pivote, así que les dejamos en todo el lado derecho de la pared. Finalmente, llegamos al elemento actual y ver que es el pivote. Ahora, eso quiere decir que tenemos dos secciones de la matriz, el primer ser pequeña en el pivote y en el lado izquierdo de la pared, y el segundo ser mayor que el pivote para la lado derecho de la pared. Queremos poner el elemento de pivote entre los dos, y entonces sabremos que el pivote está en su derecho lugar clasificado final. Así que cambiamos el primer elemento de la lado derecho de la pared con el pivote, y sabemos del pivote en su posición correcta. 

Luego se repite este proceso para el subarrays izquierda y derecha del pivote. Desde la última submatriz es sólo una elemento largo, sabemos que eso es ya ordenada, porque ¿cómo se puede estar fuera de ordenar si usted es sólo un elemento? Por el lado derecho de la submatriz, nos ver que el pivote es 5, y el muro está justo a la izquierda de la 6. Y el elemento actual también que comienza como el 6. Así que 6 es mayor que 5. Lo dejamos donde está en el lado derecho de la pared. Ahora, pasando, 3 es menor que 5. Así que cambiamos con el primer elemento apenas a la derecha de la pared. Ahora, me mudé de la pared hasta una. Ahora, pasando a la 8. 8 es mayor que 5, y así lo dejamos. El 4 es menor que 5, por lo que cambiar él. Y en. Y en. 

Cada vez que repetimos el proceso en el lados izquierdo y derecho de la matriz de. nosotros elegir un pivote y hacer las comparaciones y crear otro nivel de la izquierda y subarrays derecha. Esta llamada recursiva continuará hasta llegamos al final cuando hemos dividido la matriz global en sólo subconjuntos de longitud 1. A partir de ahí, sabemos que la matriz se ordena ya que cada elemento tiene, al algún momento, ha sido un pivote. En otras palabras, para cada elemento, todo los números a la izquierda son menores valores y todos los números a la derecho tienen mayores valores. 

Este método funciona muy bien si el valor del pivote elegido es aproximadamente en el centro rango de los valores de la lista. Esto significaría que, después de que nos movemos elementos alrededor, hay casi tantos elementos a la izquierda del pivote ya que hay a la derecha. Y la naturaleza de divide y vencerás de la Luego se toma el algoritmo quicksort todo el provecho a. Esto crea un tiempo de ejecución de O (n log n,) el n porque tenemos que hacer n menos 1 comparaciones en cada generación y registro n porque tenemos que dividir la lista log n veces. Sin embargo, en el peor de los casos, este algoritmo en realidad puede ser de O (n al cuadrado.) Supongamos que en cada generación, el pivote que pasa a ser el más pequeño o el más grande de la números que estamos de clasificación. Esto significaría romper la lista n veces y la toma de N menos 1 comparaciones cada vez. Por lo tanto, o de n al cuadrado. 

¿Cómo podemos mejorar el método? Una buena manera de mejorar el método es para reducir la probabilidad de que el tiempo de ejecución es siempre realmente O de n al cuadrado. Recuerde que esta peor, peor de los casos sólo puede ocurrir cuando la pivote elegido es siempre el más alto o el valor más bajo en la matriz. Para garantizar que esto es menos probable que ocurra, podemos encontrar el pivote por la elección de múltiples elementos y teniendo el valor de la mediana. 

Mi nombre es Mark Grozen-Smith, y esto es CS50. 

Para simplificar, vamos a suponer que los las cosas son sólo números enteros, pero saber que QUICKSERT - QUICKSERT? Lo siento. 

Aquí tenemos los enteros 6, 5, 1, 3, 8, 4, 9. 

ALTAVOZ 1: ¿En serio? 

ALTAVOZ 2: No se detiene allí. 

ALTAVOZ 1: ¿En serio?