1 00:00:00,000 --> 00:00:05,726 >> [REPRODUCCIÓN DE MÚSICA] 2 00:00:05,726 --> 00:00:08,600 DOUG LLOYD: Selección tipo es un algoritmo que, como era de esperar, 3 00:00:08,600 --> 00:00:10,470 ordena un conjunto de elementos. 4 00:00:10,470 --> 00:00:12,470 Y algoritmo de recuperación es un conjunto paso a paso 5 00:00:12,470 --> 00:00:15,260 de instrucciones para completar una tarea. 6 00:00:15,260 --> 00:00:17,580 >> En la selección ordenar la idea básica es la siguiente, 7 00:00:17,580 --> 00:00:22,080 encontrar el elemento más pequeño y sin clasificar añadir al final de la lista ordenada. 8 00:00:22,080 --> 00:00:26,970 Efectivamente lo que esto hace es construir una lista ordenada, un elemento a la vez. 9 00:00:26,970 --> 00:00:29,800 Rompiendo con las que pseudocódigo podríamos afirmar que este algoritmo 10 00:00:29,800 --> 00:00:34,490 la siguiente, repetir esto hasta sin elementos no clasificados permanecen. 11 00:00:34,490 --> 00:00:38,660 Realice una búsqueda entre los no seleccionados datos para encontrar el valor más pequeño, 12 00:00:38,660 --> 00:00:44,130 a continuación, cambiar el valor más pequeño con el primer elemento de la parte sin clasificar. 13 00:00:44,130 --> 00:00:47,130 >> Se puede ayudar a visualizar esto, así que vamos a echar un vistazo a esto. 14 00:00:47,130 --> 00:00:49,710 Así que esto, sostengo, es una array sin clasificar y tengo 15 00:00:49,710 --> 00:00:53,040 se indica mediante la indicación de que todos de los elementos son de color rojo, 16 00:00:53,040 --> 00:00:54,420 que aún no están ordenados. 17 00:00:54,420 --> 00:00:57,670 Este es el entero parte no seleccionada de la matriz. 18 00:00:57,670 --> 00:01:02,020 >> Así que vamos a ir a través de los pasos de ordenación por selección para ordenar esta matriz. 19 00:01:02,020 --> 00:01:05,296 Así que de nuevo, vamos a repetir hasta que no permanecen sin clasificar elementos. 20 00:01:05,296 --> 00:01:07,920 Vamos a buscar a través de la datos para encontrar el valor más pequeño, 21 00:01:07,920 --> 00:01:11,990 y luego cambiar ese valor con el primer elemento de la parte sin clasificar. 22 00:01:11,990 --> 00:01:14,380 >> Ahora, de nuevo, todo el matriz es la parte sin clasificar. 23 00:01:14,380 --> 00:01:16,534 Todos los elementos son de color rojo sin clasificar. 24 00:01:16,534 --> 00:01:18,700 Así que buscamos a través y nos encontramos con el valor más pequeño. 25 00:01:18,700 --> 00:01:20,533 Empezamos por el principio, vamos hasta el final, 26 00:01:20,533 --> 00:01:23,630 nos encontramos con el valor más pequeño es, uno. 27 00:01:23,630 --> 00:01:24,860 Así que esa es la primera parte. 28 00:01:24,860 --> 00:01:29,440 Y luego la segunda parte, intercambiar ese valor con el primer elemento de la parte sin clasificar, 29 00:01:29,440 --> 00:01:31,340 o el primer elemento de rojo. 30 00:01:31,340 --> 00:01:34,980 >> En este caso que sería cinco, así que intercambiamos uno y cinco. 31 00:01:34,980 --> 00:01:37,320 Cuando hacemos esto, podemos vemos visualmente que hemos 32 00:01:37,320 --> 00:01:41,260 movido el elemento valorado más pequeño de la matriz, al principio. 33 00:01:41,260 --> 00:01:43,920 Efectivamente clasificación de ese elemento. 34 00:01:43,920 --> 00:01:47,520 >> Y por lo que podemos confirmar de hecho y el estado que uno, se clasifica. 35 00:01:47,520 --> 00:01:52,080 Y lo que vamos a indicar la parte ordenados de nuestra matriz, coloreando de azul. 36 00:01:52,080 --> 00:01:53,860 >> Ahora sólo repetimos el proceso de nuevo. 37 00:01:53,860 --> 00:01:57,430 Buscamos a través de la parte no seleccionada de la matriz para encontrar el elemento más pequeño. 38 00:01:57,430 --> 00:01:59,000 En este caso, es dos. 39 00:01:59,000 --> 00:02:02,100 >> Intercambiamos que con la primera elemento de la parte sin clasificar. 40 00:02:02,100 --> 00:02:05,540 En este caso dos también pasa a ser el primer elemento de la parte sin clasificar. 41 00:02:05,540 --> 00:02:08,650 Así que intercambiamos dos con sí mismo, que en realidad sólo deja dos 42 00:02:08,650 --> 00:02:11,257 donde está, y está ordenada. 43 00:02:11,257 --> 00:02:13,840 Continuando, buscamos a través para encontrar el elemento más pequeño. 44 00:02:13,840 --> 00:02:15,030 Son las tres. 45 00:02:15,030 --> 00:02:17,650 Intercambiamos con el primero elemento, que es cinco. 46 00:02:17,650 --> 00:02:19,450 Y ahora tres está ordenado. 47 00:02:19,450 --> 00:02:22,440 >> Buscamos a través de nuevo, y nos encontrar el elemento más pequeño es de cuatro. 48 00:02:22,440 --> 00:02:28,070 Intercambiamos con el primer elemento de la parte sin clasificar, y ahora cuatro se solucionó. 49 00:02:28,070 --> 00:02:29,910 >> Encontramos que cinco es el elemento más pequeño. 50 00:02:29,910 --> 00:02:32,900 Intercambiamos con el primero elemento de la parte sin clasificar. 51 00:02:32,900 --> 00:02:34,740 Y ahora de cinco se ordena. 52 00:02:34,740 --> 00:02:36,660 >> Y luego, por último, nuestra parte sin clasificar consiste 53 00:02:36,660 --> 00:02:38,576 de un solo elemento, así que buscar a través de 54 00:02:38,576 --> 00:02:41,740 y nos encontramos con que seis es el más pequeño, y de hecho, único elemento. 55 00:02:41,740 --> 00:02:44,906 Y entonces podemos afirmar que se ordena. 56 00:02:44,906 --> 00:02:47,530 Y ahora hemos cambiado nuestra gama de ser completamente sin clasificar 57 00:02:47,530 --> 00:02:52,660 en rojo, que ordenados por completo en azul, mediante la selección de clasificación. 58 00:02:52,660 --> 00:02:54,920 >> ¿Cuál es el peor de los casos aquí? 59 00:02:54,920 --> 00:02:57,830 Bueno, en el peor caso, tenemos que mirar por encima de 60 00:02:57,830 --> 00:03:02,170 todos los elementos de la matriz a encontrar el elemento más pequeño sin clasificar, 61 00:03:02,170 --> 00:03:04,750 y tenemos que repetir este proceso n veces. 62 00:03:04,750 --> 00:03:09,090 Una vez por cada elemento de la matriz porque sólo en este algoritmo, 63 00:03:09,090 --> 00:03:12,180 ordenar un elemento a la vez. 64 00:03:12,180 --> 00:03:13,595 >> ¿Cuál es el mejor de los casos? 65 00:03:13,595 --> 00:03:15,040 Bueno, es exactamente lo mismo, ¿no? 66 00:03:15,040 --> 00:03:18,440 De hecho, tenemos que siguen paso a paso cada elemento de la matriz 67 00:03:18,440 --> 00:03:22,040 con el fin de confirmar que se trata, de hecho, el elemento más pequeño. 68 00:03:22,040 --> 00:03:26,760 >> Así el peor tiempo de ejecución caso, tener que repetir un proceso n veces, 69 00:03:26,760 --> 00:03:28,960 una vez para cada uno de n elementos. 70 00:03:28,960 --> 00:03:31,940 Y en el mejor de los casos, tenemos que hacer lo mismo. 71 00:03:31,940 --> 00:03:35,340 >> Así que pensando en volver a nuestra caja de herramientas de la complejidad computacional, 72 00:03:35,340 --> 00:03:39,250 ¿qué crees que es el peor runtime caso para la selección de una especie? 73 00:03:39,250 --> 00:03:41,840 ¿Qué crees que es el mejor runtime caso para la selección de una especie? 74 00:03:41,840 --> 00:03:44,760 75 00:03:44,760 --> 00:03:49,325 >> ¿Sabía usted adivina O grande de n al cuadrado, y Big Omega de n al cuadrado? 76 00:03:49,325 --> 00:03:49,950 Usted tendría razón. 77 00:03:49,950 --> 00:03:52,490 Aquellos son, de hecho, la peor de los casos y la mejor racha caso 78 00:03:52,490 --> 00:03:55,100 veces, para la selección de especie. 79 00:03:55,100 --> 00:03:56,260 >> Soy Doug Lloyd. 80 00:03:56,260 --> 00:03:58,600 Esto es CS50. 81 00:03:58,600 --> 00:04:00,279