Tip:
Highlight text to annotate it
X
>> [Música tocando]
Doug LLOYD: Selección é unha especie algoritmo que, como podería esperar,
Clasifica un conxunto de elementos.
E algoritmo recordo é un conxunto paso a paso
de instrucións para completar unha tarefa.
>> Na selección clasificar a idea básica é esta:
atopar o menor elemento sen clasificar e engadir lo ao final da lista ordenada.
Efectivamente o que iso fai é construír unha lista clasificada, un elemento de cada vez.
Rompe-lo para abaixo para pseudocódigo podemos afirmar este algoritmo
deste xeito, repita iso ata non hai elementos non ordenados permanecen.
Busca a través da indiferenciados datos para atopar o menor valor,
a continuación, cambiar o menor valor co primeiro elemento da parte indiferenciados.
>> Ela pode axudar a ver isto, así que imos dar un ollo niso.
Entón iso, eu afirmo, é unha matriz sen clasificar e eu teño
indicou que, indicando que todo dos elementos son de cor vermella,
eles non son clasificadas.
Este é o enteiro indiferenciados parte da matriz.
>> Entón, imos percorrer os pasos de selección clasificación para clasificar esta matriz.
Entón, de novo, nós imos repeat ata que non haxa elementos non ordenados permanecen.
Nós imos busca a través da datos para atopar o menor valor,
e despois cambiar ese valor co primeiro elemento da parte indiferenciados.
>> Agora, unha vez máis, a toda matriz é a parte indiferenciados.
Todos os elementos vermellos son indiferenciados.
Por iso, buscar e atopamos o menor valor.
Comezamos en principio, nós imos ata o final,
atopamos o menor valor, un.
Entón esta é unha parte.
E, a continuación, a parte dous, intercambiar ese valor con o primeiro elemento da parte non clasificado,
ou o primeiro elemento vermello.
>> Neste caso que sería cinco, polo tanto, cambiar un e cinco.
Cando facemos iso, podemos visualmente ver que temos
moveu o elemento máis pequeno valorado da matriz, para o inicio.
En efecto selección ese elemento.
>> E así podemos efectivamente confirmar e afirman que un, está clasificada.
E así imos indicar a porción clasificada da nosa matriz, colorido o azul.
>> Agora é só repetir o proceso de novo.
Buscamos a través da parte sen clasificar de a matriz para atopar o elemento máis pequeno.
Neste caso, é dous.
>> Nós que cambiar coa primeira elemento da parte indiferenciados.
Neste caso, dous tamén pasa a ser o primeiro elemento da parte indiferenciados.
Entón nós trocamos dous con si mesmo, o que realmente deixa só dous
onde está, e está clasificado.
Continuando, nós buscar para atopar o elemento máis pequeno.
É tres.
Nós troca-lo o primeiro elemento, que é de cinco.
E agora tres está clasificada.
>> Nós investigación a través de novo, e nós atopar o menor elemento é catro.
Nós troca-lo o primeiro elemento da parte sen clasificar, e agora catro está clasificada.
>> Nós cremos que é cinco o elemento máis pequeno.
Nós troca-lo o primeiro elemento da parte indiferenciados.
E agora cinco está clasificada.
>> E entón, finalmente, o noso parte consiste sen clasificar
de só un único elemento, por iso, buscar
e nós cremos que seis é o menor, e de feito, único elemento.
E entón podemos afirmar que é clasificado.
E agora cambiamos nosa matriz de ser completamente non separados
en vermello, completamente clasificadas en azul, a través da selección de clasificación.
>> Entón, cal é o peor escenario aquí?
Ben no peor absoluta caso, temos que mirar por riba
todos os elementos da matriz para atopar o menor elemento non clasificado,
e temos que repetir este proceso n veces.
Xa que para cada elemento do array porque só neste algoritmo,
tipo un elemento de cada vez.
>> Cal é o mellor escenario?
Ben, é exactamente o mesmo, non?
En realidade, hai que seguir a percorrer cada elemento da matriz
a fin de confirmar que é, En realidade, o elemento máis pequeno.
>> Entón, o peor caso de tempo de execución, que ten que repetir un proceso n veces,
unha vez para cada un dos n elementos.
E no mellor dos casos, temos que facer o mesmo.
>> Entón, pensando de volta ao noso Toolbox complexidade computacional,
o que pensas que é o peor caso de tempo de execución para a selección tipo?
¿Que pensas que é o mellor caso de tempo de execución para a selección tipo?
>> Será que adiviña Big O n ao cadrado, e Big Omega n ao cadrado?
Estaría ben.
Estes son, en realidade, o peor caso e mellor caso de execución
veces, para a selección de tipo.
>> Eu son Doug Lloyd.
Este é CS50.