[Powered by Google Translate] Tommy: Imos dar un ollo tipo de selección, un algoritmo para a toma de unha lista de números e clasificándose os. Un algoritmo, lembre, é simplemente un paso a paso procedemento para realizar unha tarefa. A idea básica detrás do tipo de selección é dividir nosa lista en dúas partes - unha parte ordenada e unha porción indiferenciados. En cada etapa do algoritmo, un número é movido a partir da parte indiferenciados para a porción clasificados ata, finalmente, o completa está clasificada. Entón aquí está a lista de seis números - 23, 42, 4, 16, 8, e 15. Agora toda a lista é considerada sen clasificación. Aínda que un número como 16 xa pode estar na súa correcta situación, o noso algoritmo ten ningunha forma de saber que ata o completa está clasificada. Entón, imos considerar cada número a ser triados ata clasificar nós mesmos. Nós sabemos que queremos a lista para estar en orde crecente. Entón, nós imos querer construír a parte ordenada da nosa lista de esquerda a dereita, a menor para o maior. Para iso, imos ter que atopar o elemento mínimo indiferenciados e poñelas no fin da porción clasificada. Como esta lista non está ordenada, a única forma de facelo é mirar para cada elemento na porción non separados, lembrando que elemento é a máis baixa e comparando Cada elemento que. Entón, imos ollar primeiro para o 23. Este é o primeiro elemento que temos visto, por iso imos lembrar como mínimo. A continuación, imos ollar para 42. 42 é maior que 23, entón 23 é aínda o mínimo. O seguinte é o 4, que é inferior a 23, así que imos lembrar 4 como o novo mínimo. A continuación é 16, que é maior que 4, entón 4 aínda é o mínimo. 8 é maior que 4 e 15 é maior que 4, entón 4 debe ser menor elemento indiferenciado. Así, aínda que, como seres humanos, podemos ver inmediatamente que 4 é o elemento mínimo, o algoritmo precisa de ollar para Cada elemento indiferenciado, mesmo despois de ter atopado a 4 - o elemento mínimo. Polo tanto, agora que atopamos o elemento mínimo, 4, imos querer para movela na porción da lista ordenada. Unha vez que este é o primeiro paso, isto significa que queren pór en 4 o inicio da lista. Nese momento 23 é, no inicio da lista, de modo Imos cambiar o 4 eo 23. Entón, agora a nosa lista parecida con esta. Sabemos que 4 ha de ser na súa posición final, xa que é tanto o elemento máis pequeno eo elemento no inicio da lista. Entón iso significa que non precisa moverse de novo. Entón, imos repetir este proceso para engadir un elemento para a parcela clasificada na lista. Nós sabemos que non precisamos de ollar para o 4, xa que é xa están clasificados. Así, podemos comezar no 42, que vai lembrar de como a elemento mínimo. Entón, a próxima imos ollar para o 23, que é menor que 42, entón nós lembrar 23 é o novo mínimo. A continuación, vemos a 16 que é inferior a 23, para 16 é o novo mínimo. Agora imos examinar o 8 que é menos do que 16, entón 8 é o novo mínimo. E finalmente 8 é inferior a 15, polo que sabemos que 8 é un mínimo elemento indiferenciado. Entón iso significa que debemos engadir 8 ao ordenadas porción da lista. Agora 4 é o único elemento clasificados, por iso queremos poñer o próximo día 8 para o 4. Unha vez que 42 é o primeiro elemento na porción non separados do lista, imos querer cambiar o 42 eo 8. Entón, agora a nosa lista parecida con esta. 4 e 8 representan a parcela clasificada da lista, eo números restantes representan a indiferenciados porción da lista. Entón, imos continuar con outro iteração. Comezamos con 23 desta vez, xa que non precisa de ollar para o 4 eo 8 máis, porque eles teñen xa foron clasificados. 16 é menor que 23, polo tanto, nós lembraremos 16, como o novo mínimo. 16 é menor que 42, pero 15 é menor que 16, entón debe ser 15 o elemento mínimo indiferenciados. Entón, agora queremos trocar os 15 e os 23 a dar esta lista. A porción da lista ordenada é constituída por 4, 8 e 15, e estes elementos están aínda sen clasificación. Pero acontece que o próximo elemento indiferenciado, 16, xa está clasificado. Con todo, non hai ningunha maneira para o noso algoritmo para saber que 16 xa está no seu lugar correcto, entón aínda necesitamos repetir exactamente o mesmo proceso. Polo tanto, vemos que 16 é menos de 42, e 16 é menor que 23, entón 16 debe ser o elemento mínimo. É imposible cambiar ese elemento con el mesmo, para que poidamos simplemente deixar lo no local. Entón necesitamos un paso máis do noso algoritmo. 42 é maior que 23, entón 23 debe ser o indiferenciados elemento mínimo. Unha vez que cambiar os 23 e os 42, imos acabar coa nosa final Lista de clasificados - 4, 8, 15, 16, 23, 42. Sabemos 42 debe estar no lugar correcto, xa que é o único elemento á esquerda, e que é unha especie de selección. Imos agora formalizar o noso algoritmo con algún pseudocódigo. Nunha liña, podemos ver que necesitamos integrar máis Cada elemento da lista. Excepto o último elemento, xa que o elemento 1 Lista xa está clasificado. Na liña dous, consideramos que o primeiro elemento da unsorted parte da lista para ser o mínimo, como fixemos coa nosa exemplo, de xeito que temos algo para comparar. Liña de tres comeza unha segunda volta na que iterar Cada elemento indiferenciado. Sabemos que, despois de iterações, a parte clasificada da nosa lista debe ter i elementos nel desde cada paso tipo dun elemento. Así, o primeiro elemento unsorted debe estar na posición i + 1. Na liña de catro, comparamos o elemento actual mínimo elemento que vimos ata agora. Se o elemento de corrente é menor que o mínimo elemento, entón lembre-se o elemento actual como a nova mínima na liña cinco. Finalmente, en liñas seis e sete, trocamos o mínimo elemento co primeiro elemento non separados, así engadindo-á porción da lista ordenada. Unha vez que temos un algoritmo, unha importante causa de pedir nós como programadores é canto tempo leva? Imos primeiro facer a pregunta canto tempo leva para esa algoritmo para realizar no peor caso? Recordo que representan esta carreira tempo con notación O grande. A fin de determinar o elemento mínimo indiferenciados, nós tiña esencialmente para comparar cada elemento da lista de todos os outros elementos da lista. Intuitivamente, isto soa como un O de n operación cadrado. Mirando para o noso pseudocódigo, tamén temos un loop aninhado outro ciclo, que en realidade soa como un O operación de n ao cadrado. Con todo, lembre que nós non precisamos de ollar sobre o completa para determinar o elemento mínimo indiferenciados? Unha vez que sabía que o 4 foi clasificada, por exemplo, non Debe ollar para el de novo. Así menor o tempo de execución? Para a nosa lista de lonxitude 6, é necesario facer cinco comparacións para o primeiro elemento, catro comparacións para o segundo elemento, e así por diante. Isto significa que o número total de pasos é igual á suma de os números enteiros de 1 ata a lonxitude da lista de menos 1. Podemos representar iso con un sumatorio. Non imos entrar en somatórios aquí. Pero acontece que esa suma é igual a n veces n menos 1 sobre 2. Ou equivalentemente, n ao cadrado máis 2 menos n máis de 2. Cando se fala en tempo de execución assintótico, este término n ao cadrado vai dominar este término n. Entón tipo de selección é o de n ao cadrado. Lembre que no noso exemplo, tipo de selección aínda precisaba comprobar se un número que xa foi clasificada necesaria para ser movido. Entón isto significa que, se correu tipo de selección sobre unha xa Lista clasificada, sería necesario o mesmo número de pasos, unha vez que faría ao atropelar unha lista completamente indiferenciado. Entón tipo de selección ten un rendemento mellor caso de n ao cadrado, que representamos con omega n ao cadrado. E é que polo tipo de selección. Só un dos moitos algoritmos que podemos usar para clasificar a lista. O meu nome é Tommy, e este é o CS50.