[Speel van musiek] 

DOUG LLOYD: So invoeging soort is 'n ander algoritme wat ons kan gebruik om 'n verskeidenheid te sorteer. Die idee agter hierdie algoritme is om jou gesorteerde skikking te bou in plek is, die verskuiwing van elemente uit die pad as jy gaan, om plek te maak. Dit is effens anders van seleksie soort of borrel sorteer, byvoorbeeld, waar ons die aanpassing van die plekke, waar ons maak swaps. 

In hierdie geval wat ons eintlik doen, is gly elemente oor, uit die weg geruim. Hoe hierdie algoritme werk in pseudokode? Wel, laat ons net sê dat die arbitrêr eerste element van die skikking is gesorteer. Ons bou dit in die plek. 

Ons gaan gaan 'n element op 'n slag en bou dit, en so die eerste ding wat ons sien is 'n een element skikking. En per definisie, 'n een element skikking gesorteer. 

Dan sal ons hierdie proses herhaal until-- ons sal die volgende proses herhaal totdat al van die elemente is gesorteer. Kyk na die volgende ongesorteerde element en plaas dit in die gesorteerde gedeelte, deur die verskuiwing van die vereiste aantal elemente uit die pad. Hopelik sal hierdie visualisering sal jou help om te sien presies wat gaan aan met invoeging soort. 

So weer, hier is ons hele ongesorteerde skikking, al die elemente in rooi. En laat ons volg die stappe van ons pseudokode. Die eerste ding wat ons doen, is ons noem die eerste element van die skikking, gesorteer. So ons is net gaan sê vyf, jy nou gesorteer. 

Dan kyk ons ​​na die volgende ongesorteerde element van die skikking en ons wil voeg dat in die gedeelte gesorteer, deur die verskuiwing elemente verby. So twee is die volgende ongesorteerde element van die skikking. Duidelik is dit voor die behoort vyf, so wat ons gaan doen is 'n soort van hou twee opsy vir 'n tweede, skuif vyf oor, en dan voeg twee voor vyf, waar om te gaan. En nou kan ons sê dat twee gesorteer. 

So soos jy kan sien, het ons net so ver gekyk na twee elemente van die skikking. Ons het nog nie gekyk na die rus nie, maar ons het het dié twee elemente gesorteer volgens weg van die verskuiwing meganisme. 

Sodat ons die proses weer te herhaal. Kyk na die volgende ongesorteerde element, dit is een. Kom ons hou dit eenkant vir 'n tweede, skuif alles oor, en sit een waar dit moet gaan. 

Weer, nog steeds, het ons net ooit gekyk na een, twee en vyf. Ons weet nie wat anders kom, maar ons het die drie elemente gesorteer. 

Volgende ongesorteerde element is drie, so ons sal dit ter syde te stel. Ons sal skuif oor wat ons moet wat, hierdie keer is nie alles nie soos in die vorige twee gevalle, is dit net die vyf. En dan sal ons drie in hou, tussen die twee en vyf. 

Ses is die volgende ongesorteerde element van die skikking. En in die feit ses is groter as vyf, so Ons het nie eens nodig om enige uitruiling te doen. Ons kan net ryg ses reg op die einde van die gedeelte gesorteer. 

Laastens, is die vier laaste ongesorteerde element. So sal ons dit ter syde te stel, skuif oor die elemente moet ons oor te skuif, en dan sit vier waar dit hoort. En kyk nou, ons het soort van al die elemente. Kennisgewing by te voeg sorteer, het ons nie om heen en weer oor die skikking gaan. Ons het net oor die skikking 'n tyd, en ons verskuif dinge wat ons reeds het teëgekom, ten einde ruimte vir die nuwe elemente te maak. 

So, wat is die ergste geval scenario met invoeging soort? In die ergste geval, die skikking is in omgekeerde volgorde. Jy moet elk van die elemente skuif N tot N posisies, elke enkele keer wat ons Maak 'n inplanting. Dit is 'n baie van die verskuiwing. 

In die beste geval, die skikking perfek gesorteer. En soort van soos wat gebeur het met vyf en ses in die voorbeeld, waar ons kon net ryg dit op sonder om enige verskuiwing te doen, ons wil in wese dit te doen. 

As jy dink dat ons array was een deur middel van ses, ons af wil begin deur verklaar een gesorteer. Twee kom na een so ons kan net sê, OK, goed een en twee is gesorteer. Drie kom nadat twee so, OK, een en twee en drie is gesorteer. 

Ons is nie die maak van enige swaps, ons is net die beweging van hierdie arbitrêre reël tussen gesorteer en ongesorteerde as ons gaan. So effektief as wat ons gedoen het in die voorbeeld, draai elemente blou, soos ons voortgaan. So, wat is die ergste geval runtime, dan? Onthou, as ons moet elkeen van skuif die N elemente moontlik N posisies, hopelik wat gee jou 'n idee wat die ergste geval runtime is Big O van n vierkant. 

As die skikking is perfek gesorteer, al wat ons hoef te doen is kyk na elke enkele element een keer, en dan ons klaar. So in die beste geval, dit is omega van n. 

Ek is Doug Lloyd. Dit is CS50.