>> 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.
>> 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?