[Powered by Google Translate] TOMMY: Laten we een kijkje nemen op selectie sorteren, een algoritme voor het nemen van een lijst van nummers en ze te sorteren. Een algoritme onthouden is gewoon een stap-voor-stap procedure voor het uitvoeren van een taak. Het basisidee achter selection sort is te verdelen naar onze lijst in twee delen - een gesorteerd deel en een ongesorteerd deel. Bij elke stap van het algoritme wordt een aantal verplaatst van de ongesorteerde deel aan de gesorteerde gedeelte totdat uiteindelijk de hele lijst is gesorteerd. Dus hier is een lijst van zes cijfers - 23, 42, 4, 16, 8 en 15. Op dit moment de hele lijst wordt beschouwd als ongesorteerd. Hoewel een aantal als 16 mogelijk al in de juiste locatie, ons algoritme heeft geen manier om te weten dat tot de hele lijst is gesorteerd. Dus we zullen beschouwen elk nummer worden ongesorteerde totdat we sorteren het zelf. We weten dat we de lijst moet worden in oplopende volgorde. Dus we willen de opbouw van het gesorteerd deel van onze lijst van links naar rechts, van klein naar groot. Om dat te doen, moeten we tot het minimum ongesorteerde element te vinden en het voor het einde van het gedeelte gesorteerd. Aangezien deze lijst niet gesorteerd, de enige manier om dat te doen is kijken naar elk element in de ongesorteerde deel, herinneren welk element de laagste en vergelijken elk element dat. Dus we zullen eerst eens kijken naar de 23. Dit is het eerste element die we hebben gezien, dus we herinneren zullen als het minimum. Vervolgens zullen we kijken naar 42. 42 is groter dan 23, dus 23 is nog minimum. Vervolgens is de 4 die kleiner is dan 23, dus we zullen herinneren 4 als nieuwe minimum. Vervolgens is 16 die groter is dan 4, dus 4 blijft het minimum. 8 is groter dan 4 en 15 groter is dan 4, dus 4 moet de kleinste ongesorteerde element. Dus ook al als mensen kunnen we direct zien dat 4 is de minimale element, ons algoritme moet om naar te kijken elke ongesorteerd element, zelfs nadat we de 4 gevonden - de minimum element. Dus nu dat we de minimale element, 4 gevonden, dan willen we te verplaatsen naar de gesorteerd deel van de lijst. Aangezien dit de eerste stap betekent willen we vier geschat op het begin van de lijst. 23 is nu aan het begin van de lijst zodat Laten we ruilen de 4 en de 23. Dus nu onze lijst ziet er als volgt. We weten dat 4 moet in zijn definitieve plaats, omdat het zowel de kleinste element en het element aan het begin van de lijst. Dit betekent dus dat we niet ooit nog een keer verplaatsen. Dus laten we dit proces herhalen om een ​​ander element toe te voegen aan de gesorteerd deel van de lijst. We weten dat we niet moeten kijken naar de 4, want het is al gesorteerd. Dus we kunnen beginnen bij de 42, die we zullen herinneren als de minimum element. Dus de volgende zullen we kijken naar de 23 die kleiner is dan 42, dus we herinner me 23 is het nieuwe minimum. Vervolgens geschikte 16 die kleiner is dan 23, zodat 16 is het nieuwe minimum. Nu kijken we naar de 8 die kleiner is dan 16, zodat 8 is het nieuwe minimum. En tenslotte 8 is minder dan 15, dus we weten dat 8 een minimum ongesorteerde element. Dus dat betekent dat we moeten 8 toe te voegen aan de gesorteerde deel van de lijst. Op dit moment 4 is het enige gesorteerd element, dus we willen plaatsen de 8 naast het 4. Aangezien 42 het eerste element in de ongesorteerde deel van de lijst, we willen de 42 en de 8 om te wisselen. Dus nu onze lijst ziet er als volgt. 4 en 8 stellen de gesorteerde deel van de lijst en de resterende cijfers vertegenwoordigen de ongesorteerde deel van de lijst. Dus laten we verder gaan met een andere iteratie. We beginnen met 23 dit keer, omdat we niet moeten kijken naar de 4 en de 8 meer omdat ze hebben al gesorteerd. 16 is minder dan 23, dus we herinneren zullen 16 als de nieuwe minimum. 16 is minder dan 42, maar 15 is minder dan 16, dus 15 te zijn moet de minimum ongesorteerde element. Dus nu willen we de 15 en de 23 om te ruilen geef ons deze lijst. De gesorteerd deel van de lijst bevat 4, 8 en 15, en deze elementen zijn nog steeds gesorteerd. Maar het gewoon zo gebeurt het dat de volgende ongesorteerde element, 16, al gesorteerd. Echter, er is geen manier voor ons algoritme om te weten dat 16 is al in de juiste locatie, dus we moeten nog steeds zeg precies hetzelfde proces. We zien dus dat 16 is minder dan 42, en 16 is minder dan 23, dus 16 moet de minimale element. Het is onmogelijk om dit element te wisselen met zichzelf, dus we kunnen gewoon laten op deze locatie. Dus we moeten nog een pas van ons algoritme. 42 is groter dan 23, dus 23 moet de minimum ongesorteerde element. Zodra we ruilen de 23 en de 42, we eindigen met onze laatste gesorteerde lijst - 4, 8, 15, 16, 23, 42. We weten dat 42 moeten op de juiste plaats, want het is de enige element links, en dat is selectie sorteren. Laten we nu formaliseren ons algoritme met een aantal pseudocode. Op lijn een, kunnen we zien dat we nodig hebben om te integreren dan elk element van de lijst. Behalve het laatste element, omdat het een element lijst is al gesorteerd. Op lijn twee, beschouwen we het eerste element van het ongesorteerde deel van de lijst tot het minimum te zijn, zoals wij deden met onze Zo, dus we hebben iets te vergelijken. Lijn drie begint een tweede lus waarin we itereren over elk ongesorteerde element. We weten dat nadat ik iteraties, de gesorteerde gedeelte van onze lijst moet ik elementen in het sinds elke stap soorten een element. Dus de eerste ongesorteerde element moet in stand i plus 1. Op lijn vier, vergelijken we het huidige element tot het minimum element dat we tot nu toe hebben gezien. Als de huidige element kleiner is dan de minimum element, dan kunnen we denken aan de huidige element als de nieuwe minimum op lijn vijf. Tot slot, op de lijnen zes en zeven, wisselen we de minimale element met het eerste element ongesorteerde, waardoor toe te voegen aan de gesorteerde deel van de lijst. Zodra we een algoritme, een belangrijke vraag te stellen onszelf als programmeurs is hoe lang duurde dat duren? We zullen eerst de vraag stellen hoe lang duurt het voor deze algoritme om te draaien in het ergste geval? Recall wij vertegenwoordigen deze werking tijd met grote O notatie. Om het minimum ongesorteerde element bepalen we had in wezen elk element vergelijken de lijst elk ander element in de lijst. Intuïtief, dit klinkt als een O van n kwadraat werking. Kijkend naar onze pseudocode, hebben we ook een lus genest binnen een andere lus, die inderdaad klinkt als een O n kwadraat van werking. Vergeet echter niet dat we hebben geen behoefte om te kijken over de hele lijst bij het bepalen van de minimale ongesorteerde element? Zodra we wisten dat de 4 werd gesorteerd, bijvoorbeeld, hebben we niet nog een keer naar kijken. Dus betekent dit lager de looptijd? Voor onze lijst met lengte 6, moesten we om vijf te maken vergelijkingen voor het eerste element, vier vergelijkingen voor het tweede element, enzovoort. Dat betekent dat het totale aantal stappen is de som van de getallen van 1 tot de lengte van de lijst minus 1. We kunnen vertegenwoordigen dit met een sommatie. We zullen hier niet ingaan op sommaties. Maar het blijkt dat deze optelling is gelijk aan n maal n minus 1 over 2. Of gelijkwaardig, n kwadraat meer dan 2 min n meer dan 2. Wanneer we spreken over asymptotische runtime, deze n kwadraat term gaat dit n termijn domineren. Dus selection sort is O van n in het kwadraat. Bedenk dat in ons voorbeeld, nog steeds selectie sorteren die nodig zijn om controleren of een nummer dat al werd gesorteerd moest worden verplaatst. Dus dat betekent dat als we liepen selection sort over een reeds gesorteerde lijst, zou het nodig hetzelfde aantal stappen als het zou bij het berijden van een volledig gesorteerde lijst. Dus selectie sorteren heeft een best case prestaties van n kwadraat, die wij vertegenwoordigen met omega n kwadraat. En dat is het voor selectie sorteren. Slechts een van de vele algoritmen kunnen we gebruiken om een ​​lijst te sorteren. Mijn naam is Tommy, en dit is CS50.