[Powered by Google Translate] Tommy: Kom ons neem 'n blik op die seleksie soort, 'n algoritme vir die neem van 'n lys van getalle en sorteer hulle. 'N algoritme, onthou, is eenvoudig 'n stap-vir-stap prosedure vir die totstandbrenging van 'n taak. Die basiese idee agter die seleksie soort is te verdeel ons lys in twee gedeeltes 'n gesorteer gedeelte en 'n ongesorteerde gedeelte. By elke stap van die algoritme, is 'n aantal verskuif vanaf die ongesorteerde gedeelte na die gesorteerde gedeelte totdat uiteindelik die hele lys is gesorteer. So hier is 'n lys van ses nommers - 23, 42, 4, 16, 8, en 15. Nou die hele lys word beskou as ongesorteerde data. Selfs al is 'n aantal soos 16 kan reeds in die korrekte plek, ons algoritme het geen manier om te weet dat, totdat die hele lys is gesorteer. So ons sal elke nommer ongesorteerde oorweeg word totdat ons sorteer dit self. Ons weet dat ons wil die lys te wees in stygende orde. So ons sal wil bou aan die gesorteerde gedeelte van ons lys van links na regs, die kleinste tot die grootste. Om dit te doen, moet ons die minimum ongesorteerde element te vind en sit dit aan die einde van die gesorteerde gedeelte. Aangesien hierdie lys nie gesorteer, die enigste manier om dit te doen is om te kyk na elke element in die ongesorteerde gedeelte, onthou Watter element is die laagste en vergelyk elke element dat. So sal ons eers kyk na die 23. Dit is die eerste element wat ons gesien het, so sal ons onthou dit as die minimum. Volgende sal ons kyk na 42. 42 is groter as 23, so 23 is nog steeds die minimum. Volgende is die 4 wat is minder as 23, so ons sal onthou 4 as die nuwe minimum. Volgende is 16 wat is groter as 4, so 4 is nog steeds die minimum. 8 is groter as 4 en 15 is groter as 4, so 4 moet die kleinste ongesorteerde element. So selfs al is ons as mense kan onmiddellik sien dat 4 is die minimum element, ons algoritme nodig het om na te kyk elke ongesorteerde element, selfs nadat ons die 4 gevind het - die minimum element. So nou dat ons die minimum element, 4 gevind het, sal ons wil om dit te skuif in die gesorteerde gedeelte van die lys. Want dit is die eerste stap, dit beteken dat ons wil 4 te stel die begin van die lys. Reg nou 23 is aan die begin van die lys, so Kom ons ruil die 4 en die 23. So nou is ons lys lyk. Ons weet dat 4 moet in sy finale plek, want dit is beide die kleinste element en die element aan die begin van die lys. Dit beteken dus dat ons nooit nodig om dit weer te beweeg. So laat ons herhaal hierdie proses om 'n ander element te voeg aan die gesorteer gedeelte van die lys. Ons weet dat ons nie nodig het om te kyk na die 4, want dit is reeds gesorteer. Sodat ons kan begin by die 42, wat ons sal onthou as die minimum element. So, volgende sal ons kyk na die 23 wat minder as 42, so ons Onthou 23 is die nuwe minimum. Volgende sien ons die 16 wat minder is as 23, so 16 is die nuwe minimum. Nou kyk ons ​​by die 8 wat minder is as 16, so 8 is die nuwe minimum. En laastens 8 is minder as 15, so ons weet dat die 8 is 'n minimum ongesorteerde element. So dit beteken dat ons 8 voeg aan die gesorteerde gedeelte van die lys. Reg nou 4 is die enigste gesorteer element, so ons wil te plaas die 8 volgende aan die 4. Sedert 42 is die eerste element in die ongesorteerde gedeelte van die lys, sal ons wil die 42 en die 8 te ruil. So nou is ons lys lyk. 4 en 8 verteenwoordig die gesorteerde gedeelte van die lys, en die oorblywende getalle verteenwoordig die ongesorteerde gedeelte van die lys. So laat ons voortgaan met 'n ander iterasie. Ons begin met 23 hierdie tyd, want ons hoef nie te kyk na die 4 en die 8 nie, want hulle het reeds gesorteer. 16 is minder as 23, so ons sal onthou 16 as die nuwe minimum. 16 is minder as 42, maar 15 is minder as 16, so 15 moet die minimum ongesorteerde element. So nou het ons wil die 15 en die 23 tot te ruil gee ons hierdie lys. Die gesorteer gedeelte van die lys bestaan ​​uit 4, 8 en 15, en hierdie elemente is nog steeds ongesorteerde data. Maar dit gebeur net so dat die volgende ongesorteerde element, 16, is reeds gesorteer. Daar is egter geen manier vir ons algoritme om te weet dat 16 is reeds in sy regte plek, so het ons nog nodig het om te presies dieselfde proses herhaal. So sien ons dat 16 is minder as 42, en 16 is minder as 23, so 16 moet die minimum element. Dit is onmoontlik om hierdie element te ruil met homself, sodat ons kan laat dit eenvoudig in hierdie plek. So ons moet een meer slaag van ons algoritme. 42 is meer as 23, so 23 moet wees om die minimum ongesorteerde element. Sodra ons ruil die 23 en die 42, eindig ons met ons finale gesorteerde lys - 4, 8, 15, 16, 23, 42. Ons weet 42 moet in die korrekte plek, want dit is die enigste element is links, en dit is 'n seleksie soort. Kom ons kyk nou formaliseer ons algoritme met 'n paar pseudokode. On line een, kan ons sien dat ons nodig het om te integreer oor elke element van die lys. Behalwe die laaste element, want die 1 element lys is reeds gesorteer. On line twee, ons kyk na die eerste element van die unsorted gedeelte van die lys te wees van die minimum, soos ons gedoen het met ons byvoorbeeld, so ons het iets om te vergelyk. Lyn drie begin 'n tweede rondte wat ons itereer oor elke ongesorteerde element. Ons weet dat na i iterasies, die gesorteerde gedeelte van ons lys moet ek elemente in dit sedert elke stap vorme een element. Dus is die eerste ongesorteerde element moet in posisie i plus 1. On line vier ons dit vergelyk met die huidige element tot die minimum element wat ons tot dusver gesien het. Indien die huidige element is kleiner as die minimum element, dan onthou ons die huidige element as die nuwe minimum on line vyf. Ten slotte, op die lyne ses en sewe, ruil ons die minimum element met die eerste ongesorteerde element, en daardeur toe te voeg aan die gesorteerde gedeelte van die lys. Sodra ons 'n algoritme, 'n belangrike vraag te vra onsself as programmeerders hoe lank het dit neem? Ons sal eers die vraag vra hoe lank neem dit vir hierdie algoritme uit te voer in die ergste geval? Onthou ons verteenwoordig die verloop tyd met die groot O notasie. Ten einde die minimum ongesorteerde element te bepaal, het ons wese het elke element in die lys te vergelyk elke ander element in die lys. Intuïtief, dit klink soos 'n O van n kwadraat werking. Op soek na ons pseudokode, ons het ook 'n lus geneste binne nog 'n lus, wat inderdaad klink soos 'n O van n kwadraat werking. Egter onthou dat ons nie nodig het om te kyk oor die volledige lys by die bepaling van die minimum ongesorteerde element? Sodra ons het geweet dat die 4 gesorteer, byvoorbeeld, ons het nie nodig het om te kyk na dit weer. So doen dit laer die loop van die tyd? Vir 'n lys van lengte 6, ons nodig het vyf te maak vergelykings vir die eerste element, vier vergelykings vir die tweede element, en so aan. Dit beteken dat die totale aantal van die stappe is die som van die heelgetalle van 1 tot die lengte van die lys minus 1. Ons kan verteenwoordig hierdie met 'n opsomming. Ons sal nie gaan in die opsommings hier. Maar dit blyk dat hierdie opsomming is gelyk aan n keer n minus 1 oor 2. Of gelykerwys, n oor 2 vierkant minus n oor 2. Wanneer praat oor die asimptotiese runtime, n kwadraat term gaan hierdie n term te oorheers. So seleksie soort van n kwadraat O is. Onthou dat in ons voorbeeld, seleksie soort nog nodig om te Kontroleer of die nommer wat reeds gesorteer wat nodig is om te verskuif word. So dit beteken dat as ons seleksie soort gehardloop oor 'n reeds gesorteerde lys, sou dit dieselfde aantal stappe soos dit vereis sou wanneer jy loop oor 'n heeltemal ongesorteerde lys. So seleksie soort het 'n beste geval prestasie van n kwadraat, wat ons met omega n kwadraat. En dit is dit vir keuring soort. Net een van die vele algoritmes wat ons kan gebruik om 'n lys te sorteer. My naam is Tommy, en dit is cs50.