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