>> [REPRODUCCIÓN DE MÚSICA]
DOUG LLOYD: Selección tipo es un algoritmo que, como era de esperar,
ordena un conjunto de elementos.
Y algoritmo de recuperación es un conjunto paso a paso
de instrucciones para completar una tarea.
>> En la selección ordenar la idea básica es la siguiente,
encontrar el elemento más pequeño y sin clasificar añadir al final de la lista ordenada.
Efectivamente lo que esto hace es construir una lista ordenada, un elemento a la vez.
Rompiendo con las que pseudocódigo podríamos afirmar que este algoritmo
la siguiente, repetir esto hasta sin elementos no clasificados permanecen.
Realice una búsqueda entre los no seleccionados datos para encontrar el valor más pequeño,
a continuación, cambiar el valor más pequeño con el primer elemento de la parte sin clasificar.
>> Se puede ayudar a visualizar esto, así que vamos a echar un vistazo a esto.
Así que esto, sostengo, es una array sin clasificar y tengo
se indica mediante la indicación de que todos de los elementos son de color rojo,
que aún no están ordenados.
Este es el entero parte no seleccionada de la matriz.
>> Así que vamos a ir a través de los pasos de ordenación por selección para ordenar esta matriz.
Así que de nuevo, vamos a repetir hasta que no permanecen sin clasificar elementos.
Vamos a buscar a través de la datos para encontrar el valor más pequeño,
y luego cambiar ese valor con el primer elemento de la parte sin clasificar.
>> Ahora, de nuevo, todo el matriz es la parte sin clasificar.
Todos los elementos son de color rojo sin clasificar.
Así que buscamos a través y nos encontramos con el valor más pequeño.
Empezamos por el principio, vamos hasta el final,
nos encontramos con el valor más pequeño es, uno.
Así que esa es la primera parte.
Y luego la segunda parte, intercambiar ese valor con el primer elemento de la parte sin clasificar,
o el primer elemento de rojo.
>> En este caso que sería cinco, así que intercambiamos uno y cinco.
Cuando hacemos esto, podemos vemos visualmente que hemos
movido el elemento valorado más pequeño de la matriz, al principio.
Efectivamente clasificación de ese elemento.
>> Y por lo que podemos confirmar de hecho y el estado que uno, se clasifica.
Y lo que vamos a indicar la parte ordenados de nuestra matriz, coloreando de azul.
>> Ahora sólo repetimos el proceso de nuevo.
Buscamos a través de la parte no seleccionada de la matriz para encontrar el elemento más pequeño.
En este caso, es dos.
>> Intercambiamos que con la primera elemento de la parte sin clasificar.
En este caso dos también pasa a ser el primer elemento de la parte sin clasificar.
Así que intercambiamos dos con sí mismo, que en realidad sólo deja dos
donde está, y está ordenada.
Continuando, buscamos a través para encontrar el elemento más pequeño.
Son las tres.
Intercambiamos con el primero elemento, que es cinco.
Y ahora tres está ordenado.
>> Buscamos a través de nuevo, y nos encontrar el elemento más pequeño es de cuatro.
Intercambiamos con el primer elemento de la parte sin clasificar, y ahora cuatro se solucionó.
>> Encontramos que cinco es el elemento más pequeño.
Intercambiamos con el primero elemento de la parte sin clasificar.
Y ahora de cinco se ordena.
>> Y luego, por último, nuestra parte sin clasificar consiste
de un solo elemento, así que buscar a través de
y nos encontramos con que seis es el más pequeño, y de hecho, único elemento.
Y entonces podemos afirmar que se ordena.
Y ahora hemos cambiado nuestra gama de ser completamente sin clasificar
en rojo, que ordenados por completo en azul, mediante la selección de clasificación.
>> ¿Cuál es el peor de los casos aquí?
Bueno, en el peor caso, tenemos que mirar por encima de
todos los elementos de la matriz a encontrar el elemento más pequeño sin clasificar,
y tenemos que repetir este proceso n veces.
Una vez por cada elemento de la matriz porque sólo en este algoritmo,
ordenar un elemento a la vez.
>> ¿Cuál es el mejor de los casos?
Bueno, es exactamente lo mismo, ¿no?
De hecho, tenemos que siguen paso a paso cada elemento de la matriz
con el fin de confirmar que se trata, de hecho, el elemento más pequeño.
>> Así el peor tiempo de ejecución caso, tener que repetir un proceso n veces,
una vez para cada uno de n elementos.
Y en el mejor de los casos, tenemos que hacer lo mismo.
>> Así que pensando en volver a nuestra caja de herramientas de la complejidad computacional,
¿qué crees que es el peor runtime caso para la selección de una especie?
¿Qué crees que es el mejor runtime caso para la selección de una especie?
>> ¿Sabía usted adivina O grande de n al cuadrado, y Big Omega de n al cuadrado?
Usted tendría razón.
Aquellos son, de hecho, la peor de los casos y la mejor racha caso
veces, para la selección de especie.
>> Soy Doug Lloyd.
Esto es CS50.