[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.