[Powered by Google Translate] [Ordenar Inserción] [Tommy MacWilliam] [Harvard University] [Esta é CS50.TV] Imos dar un ollo ao tipo de inserción, un algoritmo para a toma de unha lista de números e clasificándose os. Un algoritmo, lembre, é simplemente un procedemento paso a paso para a realización dunha tarefa. A idea básica por tras do tipo de inserció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 porción non triados para a porción clasificada ata que finalmente a listaxe e ordenada. Aquí está a lista de seis números indiferenciados - 23, 42, 4, 16, 8 e 15. Unha vez que estes números non son todo en orde ascendente, están sen clasificación. Dende que non comezou aínda a clasificación, imos considerar os seis elementos a nosa parte indiferenciados. 

Así que comezar a clasificación, imos poñer estes números clasificados para a esquerda destes. Entón, imos comezar con 23, o primeiro elemento na nosa lista. Nós non temos todos os elementos da nosa parte clasificada aínda, entón imos simplemente considerar 23 sexa o inicio eo fin da nosa parte clasificados. Agora, a nosa parte ordenada ten un número, 23, ea nosa porción indiferenciados ten eses cinco números. Imos agora introducir o seguinte número na nosa porción indiferenciados, 42, na porción clasificados. 

Para iso, imos ter que comparar a 42 para o 23 - o único elemento na nosa parcela clasificada ata agora. Corenta e dous é maior que 23, entón podemos simplemente engadir 42 ata o final da porción da lista ordenada. Gran! Agora a nosa parte ordenada posúe dous elementos, ea nosa porción indiferenciados ten catro elementos. Entón, imos agora pasar a 4, o elemento seguinte na parte indiferenciados. Así, onde debe estar ser colocada na parte clasificada? 

Lembre, queremos poñer este número na orde de clasificación por iso a nosa parte permanece clasificada correctamente clasificados en todos os momentos. Se colocarmos a 4 a dereita dos 42, entón a nosa lista vai ser fóra de orde. Entón, imos continuar a moverse de dereita a esquerda na nosa porción tipo. A medida que avanzamos, imos cambiar cada número baixo de un lugar para dar espazo para o novo número. Ok, 4 tamén é menor que 23, por tanto, non podemos colocar-lo aquí tamén. Imos pasar a 23 nun lugar seguro. 

Isto significa que nós queremos poñer o 4 no primeiro burato na parte de clasificados. Observe como ese espazo na lista xa estaba baleiro, porque estamos movendo elementos clasificados para abaixo como atopamos eles. Todo ben. Entón, nós estamos no medio do camiño. Imos continuar o noso algoritmo, inserindo a 16 na porción clasificados. Dezaseis é menor que 42, entón imos cambiar o 42 para a dereita. Dezaseis tamén é menor que 23, entón imos tamén cambiar ese elemento. 

Agora, 16 é maior que 4. Entón, parece que quere inserir a 16 entre o 4 eo 23. Mentres se move a través da parte clasificada na lista da dereita para a esquerda, 4 é o primeiro número que vimos que é menor que o número estamos intentando introducir. Entón, agora podemos inserir o 16 neste slot baleiro, que, lembre, creamos por elementos móbiles na parte de tipo máis como atopamos eles. 

Todo ben. Agora, temos catro elementos clasificados e dous elementos non ordenados. Entón, imos pasar a 8 na porción clasificados. Oito é inferior a 42. Oito é inferior a 23. E 8 é menor que 16. Pero 8 é maior que 4. Entón, nós queremos introducir a 8 entre o 4 eo 16. E agora só temos un elemento cara á esquerda para clasificar - o 15. Quince é inferior a 42, Quince é inferior a 23. E 15 é menor que 16. Pero 15 é maior que 8. 

Entón, aquí é onde queremos facer a nosa inserción final. E estamos a facer. Nós non temos máis elementos na parte indiferenciados, ea nosa parte está clasificada na orde correcta. Os números son ordenadas de menor a maior. Entón, imos dar un ollo a algúns pseudocódigo que describe os pasos que acaba de realizar. 

Na liña 1, podemos ver que imos ter iterar sobre cada elemento da lista exceptuando o primeiro, unha vez que o primeiro elemento na porción non triados será simplemente o primeiro elemento na porción clasificada. Nas liñas 2 e 3, estamos mantendo o control do noso sitio actual na parte indiferenciados. Elemento representa o número que estamos actualmente a pasar á parte de clasificados, e j representa o índice para a parte indiferenciados. 

Na liña 4, estamos interactuar a través da parte ordenada da dereita para a esquerda. Queremos deixar a iteração xa que o elemento á esquerda da nosa posición actual é menor que o elemento que estamos intentando introducir. Na liña 5, nós estamos cambiando cada elemento que atopamos un espazo para a dereita. Desta forma, imos ter un espazo libre para introducir en cando atopamos o primeiro elemento menos que o elemento que nos movemos. Na liña 6, estamos a actualizar o noso contador para continuar a moverse cara á esquerda a través da parte clasificados. Finalmente, na liña 7, que está introducindo o elemento dentro da porción da lista ordenada. 

Sabemos que non hai problema en introducir en posición j, porque xa cambiou o elemento que adoitaba ser hai un espazo para a dereita. Lembre, estamos movendo a través da parte ordenada da dereita para a esquerda, pero estamos movendo a través da parte indiferenciados de esquerda a dereita. Todo ben. Imos agora dar un ollo a como o algoritmo de longa duración que tomou. Imos primeiro facer a pregunta canto tempo leva para este algoritmo para realizar no peor caso. Lembre que nós representamos esta vez correndo con notación Big. Co fin de resolver a nosa lista, tivemos que iterar sobre os elementos na parte indiferenciados, e para cada un deses elementos, potencialmente máis de todos os elementos na porción clasificada. Intuitivamente, isto soa como unha operación de O (n ^ 2). 

Mirando para o noso pseudocódigo, temos un loop aninhado dentro doutro loop, que, en realidade, soa como unha operación de O (n ^ 2). Con todo, a parte ordenada de lista non contiña toda a lista ata o final. Aínda así, poderiamos potencialmente inserir un novo elemento no inicio da porción clasificada cada iteração do algoritmo, o que significa que teriamos que mirar para cada elemento actualmente na parte clasificados. Entón, isto significa que podería, potencialmente, facer unha comparación para o segundo elemento, dúas comparacións para o terceiro elemento, e así por diante. Así, o número total de pasos é a suma dos números enteiros de 1 ata a lonxitude da lista menos 1. Podemos representar iso con un sumatorio. 

Non imos entrar en somatórios aquí, pero acontece que esta suma é igual a n (n - 1) ao longo de 2, o que é equivalente n ^ 2/2 - n / 2. Cando se fala en tempo de execución assintótico, iso n ^ 2 termo vai dominar este término n. Entón, tipo de inserción é Big O (n ^ 2). E se corremos tipo de inserción nunha lista xa clasificada. Neste caso, nós simplemente construír a porción ordenadas de esquerda a dereita. Entón, a xente só precisa da orde de n pasos. 

Isto significa que este tipo de inserción ten un rendemento mellor caso de n, que representamos con Ω (n). E é que polo tipo de inserción, só un dos moitos algoritmos que poden ser usados ​​para clasificar a lista. O meu nome é Tommy, e este é o CS50. [CS50.TV] Oh, non pode impedir que unha vez iniciado. Oh, nós fixemos iso - Boom! >>