1 00:00:00,000 --> 00:00:02,826 >> [Speel van musiek] 2 00:00:02,826 --> 00:00:05,660 3 00:00:05,660 --> 00:00:09,370 >> DOUG LLOYD: So invoeging soort is 'n ander algoritme wat ons kan gebruik om 'n verskeidenheid te sorteer. 4 00:00:09,370 --> 00:00:12,350 Die idee agter hierdie algoritme is om jou gesorteerde skikking te bou 5 00:00:12,350 --> 00:00:19,670 in plek is, die verskuiwing van elemente uit die pad as jy gaan, om plek te maak. 6 00:00:19,670 --> 00:00:22,240 Dit is effens anders van seleksie soort of borrel 7 00:00:22,240 --> 00:00:25,460 sorteer, byvoorbeeld, waar ons die aanpassing van die plekke, 8 00:00:25,460 --> 00:00:26,910 waar ons maak swaps. 9 00:00:26,910 --> 00:00:29,760 >> In hierdie geval wat ons eintlik doen, is gly elemente 10 00:00:29,760 --> 00:00:31,390 oor, uit die weg geruim. 11 00:00:31,390 --> 00:00:34,030 Hoe hierdie algoritme werk in pseudokode? 12 00:00:34,030 --> 00:00:37,646 Wel, laat ons net sê dat die arbitrêr eerste element van die skikking is gesorteer. 13 00:00:37,646 --> 00:00:38,770 Ons bou dit in die plek. 14 00:00:38,770 --> 00:00:42,660 >> Ons gaan gaan 'n element op 'n slag en bou dit, en so die eerste ding wat ons sien 15 00:00:42,660 --> 00:00:43,890 is 'n een element skikking. 16 00:00:43,890 --> 00:00:47,720 En per definisie, 'n een element skikking gesorteer. 17 00:00:47,720 --> 00:00:50,850 >> Dan sal ons hierdie proses herhaal until-- ons sal die volgende proses herhaal 18 00:00:50,850 --> 00:00:52,900 totdat al van die elemente is gesorteer. 19 00:00:52,900 --> 00:00:57,770 Kyk na die volgende ongesorteerde element en plaas dit in die gesorteerde gedeelte, 20 00:00:57,770 --> 00:01:01,209 deur die verskuiwing van die vereiste aantal elemente uit die pad. 21 00:01:01,209 --> 00:01:03,750 Hopelik sal hierdie visualisering sal jou help om te sien presies wat 22 00:01:03,750 --> 00:01:05,980 gaan aan met invoeging soort. 23 00:01:05,980 --> 00:01:08,010 >> So weer, hier is ons hele ongesorteerde skikking, 24 00:01:08,010 --> 00:01:10,970 al die elemente in rooi. 25 00:01:10,970 --> 00:01:13,320 En laat ons volg die stappe van ons pseudokode. 26 00:01:13,320 --> 00:01:16,970 Die eerste ding wat ons doen, is ons noem die eerste element van die skikking, gesorteer. 27 00:01:16,970 --> 00:01:20,920 So ons is net gaan sê vyf, jy nou gesorteer. 28 00:01:20,920 --> 00:01:24,570 >> Dan kyk ons ​​na die volgende ongesorteerde element van die skikking 29 00:01:24,570 --> 00:01:27,610 en ons wil voeg dat in die gedeelte gesorteer, 30 00:01:27,610 --> 00:01:29,750 deur die verskuiwing elemente verby. 31 00:01:29,750 --> 00:01:33,470 So twee is die volgende ongesorteerde element van die skikking. 32 00:01:33,470 --> 00:01:36,250 Duidelik is dit voor die behoort vyf, so wat ons gaan doen 33 00:01:36,250 --> 00:01:41,580 is 'n soort van hou twee opsy vir 'n tweede, skuif vyf oor, en dan voeg twee 34 00:01:41,580 --> 00:01:43,210 voor vyf, waar om te gaan. 35 00:01:43,210 --> 00:01:45,280 En nou kan ons sê dat twee gesorteer. 36 00:01:45,280 --> 00:01:48,400 >> So soos jy kan sien, het ons net so ver gekyk na twee elemente van die skikking. 37 00:01:48,400 --> 00:01:50,600 Ons het nog nie gekyk na die rus nie, maar ons het 38 00:01:50,600 --> 00:01:54,582 het dié twee elemente gesorteer volgens weg van die verskuiwing meganisme. 39 00:01:54,582 --> 00:01:56,410 >> Sodat ons die proses weer te herhaal. 40 00:01:56,410 --> 00:01:58,850 Kyk na die volgende ongesorteerde element, dit is een. 41 00:01:58,850 --> 00:02:04,010 Kom ons hou dit eenkant vir 'n tweede, skuif alles oor, en sit een 42 00:02:04,010 --> 00:02:05,570 waar dit moet gaan. 43 00:02:05,570 --> 00:02:08,110 >> Weer, nog steeds, het ons net ooit gekyk na een, twee en vyf. 44 00:02:08,110 --> 00:02:12,480 Ons weet nie wat anders kom, maar ons het die drie elemente gesorteer. 45 00:02:12,480 --> 00:02:16,030 >> Volgende ongesorteerde element is drie, so ons sal dit ter syde te stel. 46 00:02:16,030 --> 00:02:18,200 Ons sal skuif oor wat ons moet wat, hierdie keer 47 00:02:18,200 --> 00:02:21,820 is nie alles nie soos in die vorige twee gevalle, is dit net die vyf. 48 00:02:21,820 --> 00:02:25,440 En dan sal ons drie in hou, tussen die twee en vyf. 49 00:02:25,440 --> 00:02:27,849 >> Ses is die volgende ongesorteerde element van die skikking. 50 00:02:27,849 --> 00:02:31,140 En in die feit ses is groter as vyf, so Ons het nie eens nodig om enige uitruiling te doen. 51 00:02:31,140 --> 00:02:35,710 Ons kan net ryg ses reg op die einde van die gedeelte gesorteer. 52 00:02:35,710 --> 00:02:38,270 >> Laastens, is die vier laaste ongesorteerde element. 53 00:02:38,270 --> 00:02:42,060 So sal ons dit ter syde te stel, skuif oor die elemente moet ons oor te skuif, 54 00:02:42,060 --> 00:02:43,780 en dan sit vier waar dit hoort. 55 00:02:43,780 --> 00:02:46,400 En kyk nou, ons het soort van al die elemente. 56 00:02:46,400 --> 00:02:48,150 Kennisgewing by te voeg sorteer, het ons nie 57 00:02:48,150 --> 00:02:50,240 om heen en weer oor die skikking gaan. 58 00:02:50,240 --> 00:02:54,720 Ons het net oor die skikking 'n tyd, en ons verskuif dinge 59 00:02:54,720 --> 00:02:59,870 wat ons reeds het teëgekom, ten einde ruimte vir die nuwe elemente te maak. 60 00:02:59,870 --> 00:03:02,820 >> So, wat is die ergste geval scenario met invoeging soort? 61 00:03:02,820 --> 00:03:05,090 In die ergste geval, die skikking is in omgekeerde volgorde. 62 00:03:05,090 --> 00:03:11,180 Jy moet elk van die elemente skuif N tot N posisies, elke enkele keer wat ons 63 00:03:11,180 --> 00:03:12,880 Maak 'n inplanting. 64 00:03:12,880 --> 00:03:15,720 Dit is 'n baie van die verskuiwing. 65 00:03:15,720 --> 00:03:18,014 >> In die beste geval, die skikking perfek gesorteer. 66 00:03:18,014 --> 00:03:20,680 En soort van soos wat gebeur het met vyf en ses in die voorbeeld, 67 00:03:20,680 --> 00:03:23,779 waar ons kon net ryg dit op sonder om enige verskuiwing te doen, 68 00:03:23,779 --> 00:03:24,820 ons wil in wese dit te doen. 69 00:03:24,820 --> 00:03:27,560 >> As jy dink dat ons array was een deur middel van ses, 70 00:03:27,560 --> 00:03:29,900 ons af wil begin deur verklaar een gesorteer. 71 00:03:29,900 --> 00:03:33,300 Twee kom na een so ons kan net sê, OK, goed een en twee is gesorteer. 72 00:03:33,300 --> 00:03:36,190 Drie kom nadat twee so, OK, een en twee en drie is gesorteer. 73 00:03:36,190 --> 00:03:39,590 >> Ons is nie die maak van enige swaps, ons is net die beweging van hierdie arbitrêre reël 74 00:03:39,590 --> 00:03:42,460 tussen gesorteer en ongesorteerde as ons gaan. 75 00:03:42,460 --> 00:03:46,646 So effektief as wat ons gedoen het in die voorbeeld, draai elemente blou, soos ons voortgaan. 76 00:03:46,646 --> 00:03:48,270 So, wat is die ergste geval runtime, dan? 77 00:03:48,270 --> 00:03:51,854 Onthou, as ons moet elkeen van skuif die N elemente moontlik N posisies, 78 00:03:51,854 --> 00:03:54,020 hopelik wat gee jou 'n idee wat die ergste geval 79 00:03:54,020 --> 00:03:57,770 runtime is Big O van n vierkant. 80 00:03:57,770 --> 00:04:00,220 >> As die skikking is perfek gesorteer, al wat ons hoef te doen 81 00:04:00,220 --> 00:04:04,480 is kyk na elke enkele element een keer, en dan ons klaar. 82 00:04:04,480 --> 00:04:08,440 So in die beste geval, dit is omega van n. 83 00:04:08,440 --> 00:04:09,490 >> Ek is Doug Lloyd. 84 00:04:09,490 --> 00:04:11,760 Dit is CS50. 85 00:04:11,760 --> 00:04:13,119