[Powered by Google Translate] TOMMY: Vamos a echar un vistazo a la ordenación por selección, un algoritmo para la toma de una lista de números y clasificarlas. Un algoritmo, recuerde, es simplemente un paso a paso procedimiento para llevar a cabo una tarea. La idea básica detrás de la ordenación por selección es dividir la lista en dos partes - una porción ordenados y una porción sin clasificar. En cada paso del algoritmo, un número se mueve desde la unsorted porción a la porción ordenados hasta que finalmente la toda la lista está ordenada. Así que aquí está una lista de seis números - 23, 42, 4, 16, 8, y 15. En este momento toda la lista se considera sin ordenar. A pesar de que un número como 16 puede estar ya en su correcta ubicación, nuestro algoritmo no tiene manera de saber que hasta que el toda la lista está ordenada. Así que vamos a considerar cada número que se unsorted hasta que ordenar nosotros mismos. Sabemos que queremos que la lista sea en orden ascendente. Así que vamos a querer construir la porción ordenada de nuestra lista de izquierda a derecha, el más pequeño al más grande. Para hacerlo, tendremos que encontrar el elemento mínimo sin clasificar y lo sitúan en el extremo de la parte ordenados. Dado que esta lista no está ordenada, la única manera de hacerlo es ver todos los elementos de la parte sin clasificar, recordando qué elemento es el más bajo y comparando cada elemento a eso. Así que lo primero que veremos el 23. Este es el primer elemento que hemos visto, así que voy a recordar como el mínimo. A continuación vamos a ver 42. 42 es mayor que 23, por lo que 23 sigue siendo el mínimo. El siguiente es el 4, que está a menos de 23, así que vamos a recordar 4 como el nuevo mínimo. Siguiente es 16, que es mayor que 4, de modo 4 todavía es el mínimo. 8 es mayor que 4, y 15 es mayor que 4, por lo que debe ser 4 el elemento más pequeño sin clasificar. Así que a pesar de que como seres humanos podemos ver inmediatamente que el 4 es el elemento mínimo, nuestro algoritmo tiene que ver cada elemento sin clasificar, incluso después de que hayas encontrado el 4 - el elemento mínimo. Así que ahora que hemos encontrado el elemento mínimo, 4, vamos a querer para moverlo a la parte de la lista ordenada. Dado que este es el primer paso, esto significa que queremos poner 4 en el principio de la lista. En este momento 23 se encuentra al principio de la lista, por lo vamos a cambiar el 4 y 23 de la. Así que ahora la lista se parece a esto. Sabemos que 4 debe estar en su ubicación final, porque es tanto el elemento más pequeño y el elemento al principio de la lista. Así que esto significa que no siempre tenga que moverse de nuevo. Así que vamos a repetir este proceso para agregar un elemento más a la ordenados parte de la lista. Sabemos que no tenemos que mirar a la 4, porque es ya ordenados. Así que podemos empezar en el 42, que vamos a recordar como el elemento mínimo. Así que la próxima veremos el 23, que es inferior a 42, por lo que Recuerdo 23 es el nuevo mínimo. A continuación vemos el 16 que es menor que 23, por lo 16 es el nuevo mínimo. Ahora nos fijamos en el 8, que es menos de 16, por lo 8 es el nuevo mínimo. Y finalmente 8 es menor que 15, por lo que sabemos que 8 es un mínimo elemento sin clasificar. Así que eso significa que deberíamos añadir 8 al ordenar parte de la lista. En este momento 4 es el único elemento clasificado, por lo que queremos colocar el próximo 8 al 4. Dado que 42 es el primer elemento en la parte no seleccionada de la lista, vamos a querer cambiar el 42 y el 8. Así que ahora la lista se parece a esto. 4 y 8 representan la parte ordenada de la lista, y el números restantes representan la unsorted parte de la lista. Así que vamos a continuar con otra iteración. Empezamos con 23 esta vez, ya que no es necesario buscar en el 4 y el 8 ya porque no tienen ya se ha solucionado. 16 es menor que 23, por lo que va a recordar 16 como el nuevo mínimo. 16 es menor que 42, pero 15 es menor que 16, por lo que debe ser 15 el elemento unsorted mínimo. Así que ahora queremos intercambiar el 15 y el 23 de nos dan esta lista. La parte ordenada de la lista se compone de 4, 8 y 15, y estos elementos están aún sin clasificar. Pero da la casualidad de que el siguiente elemento sin clasificar, 16, ya está ordenado. Sin embargo, no hay manera de que nuestro algoritmo para saber que el 16 por ya se encuentra en su ubicación correcta, por lo que todavía tenemos que repetir exactamente el mismo proceso. Así vemos que 16 es menor que 42, y 16 es menor que 23, por lo 16 debe ser el elemento mínimo. Es imposible cambiar este elemento consigo mismo, para que podamos simplemente deje en este lugar. Así que tenemos que pasar uno más de nuestro algoritmo. 42 es mayor que 23, por lo que debe ser el 23 elemento unsorted mínimo. Una vez que cambie el 23 y 42 de la, acabamos con nuestro último lista ordenada - 4, 8, 15, 16, 23, 42. Sabemos 42 debe estar en el lugar correcto, ya que es la único elemento a la izquierda, y que es una especie de selección. Ahora vamos a formalizar nuestro algoritmo con algunos pseudocódigo. En la línea uno, podemos ver que necesitamos para integrar más cada elemento de la lista. Excepto el último elemento, ya que el elemento 1 lista ya está ordenada. En la segunda línea, consideramos que el primer elemento de la unsorted parte de la lista para ser el mínimo, como lo hicimos con nuestra ejemplo, así que tenemos algo para comparar. La línea tres se inicia un segundo bucle en el que iterar sobre cada elemento sin clasificar. Sabemos que después de i iteraciones, la porción ordenados de la lista debe tener i elementos en ella, ya que cada paso clase un elemento. De modo que el elemento no seleccionados debe estar en la posición i + 1. En la línea cuatro, se compara el elemento actual al mínimo elemento que hemos visto hasta ahora. Si el elemento actual es menor que el mínimo elemento, entonces recordamos el elemento actual como la nueva mínimo en la línea cinco. Por último, en las líneas seis y siete, cambiamos el mínimo elemento con el elemento sin clasificar primero, de tal modo añadir a la porción de la lista ordenada. Una vez que tenemos un algoritmo, una pregunta importante nosotros como programadores se cuanto tiempo me llevará? En primer lugar, voy a hacer la pregunta ¿cuánto tiempo se necesita para que esta algoritmo para ejecutarse en el peor de los casos? Recordemos que representamos esta carrera tiempo con la notación O grande. Con el fin de determinar el elemento unsorted mínimo, se esencialmente tenían que comparar cada elemento de la lista para cada otro elemento en la lista. Intuitivamente, esto suena como una junta de operación n al cuadrado. En cuanto a nuestro pseudocódigo, también tenemos un bucle anidado dentro otro bucle, que en realidad suena como una junta de operación n al cuadrado. Sin embargo, recuerde que no había necesidad de mirar por encima de la lista completa para determinar el elemento unsorted mínimo? Una vez que supimos que el 4 se clasifican, por ejemplo, no nos necesitamos ver de nuevo. Lo mismo ocurre con este menor es el tiempo de ejecución? Para nuestra lista de longitud 6, teníamos que hacer cinco comparaciones para el primer elemento, cuatro comparaciones para el segundo elemento, y así sucesivamente. Eso significa que el número total de pasos es la suma de los los números enteros de 1 a la longitud de la lista menos 1. Podemos representar esto con una suma. No vamos a entrar en sumas aquí. Pero resulta que esta suma es igual a n veces n menos 1 sobre 2. O de forma equivalente, n al cuadrado sobre 2 menos n sobre 2. Cuando se habla de tiempo de ejecución asintótico, este término al cuadrado n va a dominar este término n. Así tipo de selección es O de n al cuadrado. Recordemos que en nuestro ejemplo, clasificar selección sigue siendo necesario para comprobar si un número que ya se solucionó necesaria para ser movido. Así que eso significa que si nos encontramos con una especie de selección sobre ya lista ordenada, se requeriría el mismo número de pasos como se lo haría cuando se ejecuta sobre una lista completamente sin clasificar. Así que tipo de selección tiene un desempeño mejor de los casos cuadrado de n, que representamos con omega n al cuadrado. Y eso es todo por tipo de selección. Sólo uno de los muchos algoritmos que podamos utilizar para ordenar una lista. Mi nombre es Tommy, y esto es CS50.