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