DOUG LLOYD: Así que en CS50 aprendimos acerca una variedad de clasificación y búsqueda algoritmos. Y a veces puede ser un poco difícil de mantener la pista de lo algoritmo hace qué. Tenemos realmente sólo rozado la superficie también, hay muchas otras búsqueda y algoritmos de ordenación. Así que en este video vamos a simplemente tomar un par de minutos para tratar de destilar cada algoritmo hasta en sus elementos básicos para que pueda recordar más información importante acerca de ellos y ser capaz de articular el diferencias, si es necesario. 

La primera es la ordenación por selección. La idea básica de ordenación por selección se encuentra el elemento más pequeño sin clasificar en una matriz y cambiar con el primer elemento sin clasificar de esa matriz. Hemos dicho que el peor de los casos tiempo de ejecución de que se n al cuadrado. Y si quieres recordar por qué, toma un vistazo al vídeo ordenación por selección. El tiempo de ejecución mejor de los casos También está n al cuadrado. 

Burbuja especie, la idea detrás de esa uno es para intercambiar pares adyacentes. Así que esa es la clave que le ayuda recordar la diferencia aquí. Selección especie, es decir, hasta el momento, encontrar la burbuja smallest-- es un género intercambiar pares adyacentes. Intercambiamos pares adyacentes de elementos si están fuera de servicio, lo que efectivamente burbujas elementos más grandes a la derecha, y, al mismo tiempo, también comienza para mover elementos más pequeños a la izquierda. El peor de los casos el tiempo de ejecución caso de ordenamiento de burbuja está n al cuadrado. El tiempo de ejecución mejor de los casos de ordenamiento de burbuja es n. Porque en esa situación no actually-- puede ser que no tenga que hacer los canjes en absoluto. Sólo tenemos que hacer uno pasar a través de todos los elementos n. 

En la ordenación por inserción, la idea básica que aquí se está desplazando. Esa es la palabra clave para la ordenación por inserción. Vamos a entrar una vez a través la matriz de izquierda a derecha. Y mientras lo hacemos, estamos va a cambiar los elementos ya hemos visto para hacer espacio para más pequeños que necesitan para encajar en alguna parte de vuelta en esa porción ordenados. Así construimos la matriz ordenada de un elemento a la vez, de izquierda a derecha, y cambiamos las cosas para hacer espacio. El tiempo de ejecución del peor caso de ordenación por inserción está n al cuadrado. El tiempo mejor de los casos de gestión es n. 

Combinar sort-- la palabra clave aquí es dividir y combinar. Dividimos la gama, ya sea es seis elementos, ocho elementos, 10000 elements-- lo dividimos por medio, por medio, por medio, hasta que tengamos bajo array de n conjuntos de elementos de uno. Un conjunto de n uno conjuntos de elementos. Así que empezamos con un solo 1000-elemento de la matriz, y llegamos al punto en el que tiene 1.000 matrices de un elemento. Entonces empezamos a combinar esas matrices sub de nuevo juntos en el orden correcto. Así que tomamos dos conjuntos de un solo elemento y crear un array de dos elementos. Tomamos dos matrices de dos elementos y crear una matriz de cuatro elementos y así sucesivamente y así sucesivamente hasta que hayamos nuevamente reconstruido una matriz n elemento. 

El tiempo de ejecución del peor caso de fusionan especie es n veces log n. Tenemos n elementos, pero este proceso recombinación toma log n pasos para llegar copia de un arsenal completo. El mejor de los casos el tiempo de ejecución es también n log n porque este proceso en realidad no importa si la matriz era ordenados o no, para empezar. El proceso es el mismo, no hay no hay manera de cosas de cortocircuito. Así n log n en el peor de los casos, n log n en el mejor de los casos. 

Hablamos de dos buscar algoritmos. Así que la búsqueda lineal es sobre la iteración. Procedemos a través de la matriz una vez, de izquierda a derecha, tratando de encontrar el número que estamos buscando. El tiempo en el peor caso es ejecutar gran O de n. Nos podría tomar la iteración a través de cada elemento para encontrar el elemento que estamos buscando para, ya sea en la última posición, o nada en absoluto. Pero no podemos confirmar que hasta hemos visto todo. soy el mejor de los casos, nos encontramos de inmediato. El tiempo de ejecución mejor de los casos de búsqueda lineal es el omega de 1. 

Por último, hubo de búsqueda binaria, que requiere gama variada. Recuerde que es una muy consideración importante cuando se trabaja con búsqueda binaria. Es un requisito previo para el uso de it-- la matriz que está mirando a través de deben ser ordenados. De lo contrario, la palabra clave es divide y vencerás. Dividir la matriz en la mitad y eliminar la mitad de los elementos cada vez que a medida que avance a través. Debido a esto divide y vencerás y las cosas de división en medio enfoque, el tiempo de ejecución del peor caso de búsqueda binaria es log n, que es sustancialmente mejor que la búsqueda lineal n. El tiempo mejor de los casos de gestión sigue siendo uno. 

Podríamos encontrar inmediatamente el primera vez que hacemos una división, pero, de nuevo, recordar que aunque la búsqueda binaria es sustancialmente mejor que la búsqueda lineal en virtud de ser log n frente a n, es posible que tenga que pasar por el trabajo de ordenar la matriz primera, que podría hacer que sea menos eficaz dependiendo en el tamaño de la iteración ordenados. 

Soy Doug Lloyd, esto es CS50.