Tip:
Highlight text to annotate it
X
Wat ik in deze video wil behandelen is naar mijn mening
een van de meest intuïtieve manieren om een lijst te sorteren.
Dit zou de meest voor de hand liggende manier zijn om het handmatig te doen.
Maar ik wil wel duidelijk maken dat het niet
de meest efficiente manier is om een lijst te sorteren.
Maar laten we—
Ik denk dat dit een goed beginpunt is
om meer te weten te komen over het sorteren van lijsten.
Het staat bekend onder de naam "Insertion Sort"
Ik zal een grafische weergave geven
van het algoritme voor insertion sort.
En weet je wat
algoritme klinkt als een heel hip woord.
Maar een algoritme is niet meer dan een manier om te sorteren
of een process om het te doen
of een manier van doen.
Een programma is een specifieke implementatie van een algoritme
of kan een specifieke implementatie van een algoritme zijn.
Als ik eenmaal een algemeen algoritme heb
kan ik het implementeren in bijvoorbeeld Python
kan ik het implementeren in bijvoorbeeld C
of kan ik het implementeren in Java.
Dat zijn allemaal specifieke programma's
maar ze hebben allemaal dezelfde implementatie
van dezelfde manier om te sorteren.
En dat is alles wat ik beschrijf—
het algoritme voor Insertion Sort.
Laten we beginnen met een simpel voorbeeld:
Laten we zeggen dat ik een lijst heb—
Laten we zeggen dat ik een Python lijst heb
omdat we hiervoor zullen gaan werken met Python
en die lijst is—
laten we zeggen dat het [7,3,1,2,4,6] is.
We passen Insertion Sort toe op de lijst
door element per element te bekijken
en deze te vergelijken met de elementen ervoor
en dan bekijk je het 1ste element
dat daadwerkelijk kleiner is het huidige element
en dan zet je het huidige element rechts naast het gevonden element.
Ik zal even laten zien wat ik bedoel:
Je kunt dus beginnen met de 7
dat is het 0de element in de lijst
maar als je daarnaar kijkt—
als je met het 0de element begint
zal je wel denken "Hey wacht, er staat niets voor om 7 mee te vergelijken"
dus het heeft niet veel zin om te beginnen met het 0de element.
Dus als je dit algoritme zou implementeren
zal je moeten beginnen met het 1ste element—
Oh, sorry! Je begint met—
als dit het 0de element is
dan begin je met het 1ste element rechts daarvaan.
Dit is de 0de, dit is de 1ste
Ik weet dat dit verwarrend kan zijn
maar dit is het 0de element.
Dus je begint met de 3 hier
en vergelijkt deze met alle elementen ervoor
totdat je een element hebt gevonden dat groter is dan 3
dan plaats je de 3 op die positie in de lijst.
Wat je eigenlijk zegt is:
"Ok, is 3 kleiner dan 7?"
"Ja het is kleiner dan 7."
Wat je nu wilt doen is—
is dat je de 7 en de 3 omruilt.
Laat me het hier opschrijven—
dus we gebruiken—
we vergelijken 3 met alles ervoor.
we vergelijken 3 met alles ervoor.
Dus we zeggen: "Ok, is 3 kleiner dan 7?"
"Ja, hij is kleiner dan 7."
Dus we plaatsen de 7 op de plaats van de 3
en we plaatsen de 3 op de plaats van de 7.
Juist omdat er niks over is om met 3 te vergelijken
er is geen lager element—
er is geen element voor het 0de element
dus we plaatsen de 3 op die positie.
Voor zover ziet onze lijst er als volgt uit
onze lijst ziet er als volgt uit: [3,7,1,2,4,6]
En iets wat interessant is—
iets waar je op moet letten—
tijdens het bouwen van de lijst—
het 0de element is nu hoe dan ook kleiner dan het 1ste element
en alle elementen tot en met het 1ste element
zijn nu gesorteerd.
alle elementen tot en met het 1ste element
zijn nu gesorteerd.
En dat blijft gelden als we doorgaan met het sorteren
als we doorgaan met de rest van de elementen
tot en met de huidige positie
en als we die gedaan hebben is alles daarvoor gesorteerd.
Ik zal het aanwijzen naarmate we vorderen
Dus, we hebben de eerste positie gedaan
laten we nu verder gaan met het 2de element
dat is het element hier.
Nu pakken we dit element—
Ik schrijf het aan de zijkant hier—
je pakt dat element en vergelijkt het
met elk element dat ervoor staat:
"Ok, is 1 kleiner dan 7?"
"Ja, 1 IS kleiner dan 7."
dus laten we de 7 op de plaats van de 1 zetten.
Nu kan je of verder gaan met vergelijken
of je kan de 1 op de plaats van de 7 zetten.
En dan vragen we ons af: "Ok, is 1 kleiner dan 3?"
"Ja, natuurlijk is 1 kleiner dan 3."
Dus laten we de 3 op de plaats van de 1 zetten
en laten we de 1 op de plaats van de 3 zetten.
Dus hoe ziet onze lijst er nu uit?
Onze lijst ziet er nu als volgt uit—
ziet er nu als volgt uit [1,3,7,2,4,6]
Het valt op dat nadat we bij de nde positie zijn aangekomen—
dus in dit geval is dat de 2de positie
waar de 1ste positie hier was—
alles tot en met deze positie is nu gesorteerd.
De elementen hier zijn gesorteerd.
Het is zo dat—
dat andere dingen hierin
zullen worden gegooid naarmate we vorderen
maar tot nu toe zijn deze elementen gesorteerd.
Dus je kan zien dat
tegen de tijd we aan het einde van de lijst zijn
de hele lijst gesorteerd is.
Laten we nu verder gaan met de volgende positie
of het volgende element in de lijst
en dat is deze 2.
Dat is deze 2.
Nu vergelijken we de 2 met de 7
2 is natuurlijk kleiner dan 7
dus plaatsen we de 7 waar de 2 is
en plaatsen we de 2 waar de 7 is.
Nu vergelijken we de 2 met de 3
2 is kleiner dan 3
dus plaatsen we de 3 waar de 2 is
en plaatsen we de 2 waar de 3 is.
Nu vergelijken we 2 met 1
"Is 2 kleiner dan 1?"
"Nee, 2 is niet kleiner dan 1."
Dus we hoeven niks meer te doen.
We hoeven niet verder naar links te kijken
Dus na deze ronde—
in deze ronden vergeleken we het element 2
met alles wat ervoor stond—
dus na deze ronde ziet onze lijst er als volgt uit:
Onze lijst ziet er als volgt uit: [1,2,3,7,4,6].
Nu is alles tot en met het 3de element—
de 0de, 1ste, 2de en 3de elementen—
zijn nu gesorteerd.
Nu kunnen we naar de volgende kijken—
het volgende element in de lijst.
Ik wil één ding duidelijk maken:
als je het daadwerkelijk implementeert,
zijn er verschillende manieren om het te doen.
Je hoeft niet altijd—
in dit voorbeeld zeiden we:
"Hey, is 2 kleiner dan 7?"
De 7 vervangt de plaats waar de 2 is
wat ook moet werken.
En dan hadden we de 2 vervangen door een 7.
Maar daadwerkelijk
kan je eigen doorgaan
totdat je een juiste plaats vind voor de 2
en terwijl je dit doet alles een positie naar rechts te schuiven
en dan de 2 ertussen te voegen.
Ondanks dat deze manier iets makkelijker is om bij te houden.
En wow, misschien zien we wel verschillende manieren om het te doen
als we het algoritme daadwerkelijk gaan implementeren.
Hoe dan ook, laten we naar deze 4 kijken.
Het is weer hetzelfde idee:
4 is kleiner dan 7
dus plaatsen we de 7 waar de 4 is
en plaatsen we de 4 waar de 7 is.
"Is 4 kleiner dan 3?"
"Nee, het is niet kleiner dan 3."
Dus nu kunnen we stoppen, we zijn klaar.
Nu is alles tot en met het 4de element gesorteerd.
in de lijst is —01234—
nu gesorteerd.
En nu ziet onze lijst er als volgt uit—
even een stukje naar beneden scrollen—
Nu ziet onze lijst er als volgt uit—
je schrijft het op als
[1,2,3,4,7,6]
En nu kunnen we verder gaan met het laatste element in de lijst—
Het is deze 6 die we nu gaan vergelijken—
en het is weer hetzelfde als de laatste keer dat we dit deden
toen we ons concentreerde op de 4
maar nu concentreren we ons op de 6
"Is 6 kleiner dan 7?" "Ja, dat is hij zeker."
dus plaatsen we de 7 waar de 6 is
en plaatsen we de 6 waar de 7 is.
"Is 6 kleiner dan 4?" "Nee, dat is hij niet"
Ok, dus nu kunnen we stoppen.
Omdat we weten dat dit gesorteerd zal zijn.
Als we verder zouden gaan, zouden we alleen maar
elementen krijgen die kleiner of gelijk zijn aan 4.
Dus nu zijn we klaar, we hebben de lijst gesorteerd.
De gesorteerde lijst is nu: [1,2,3,4,6,7]
In de volgende video
zullen we proberen het algoritme te gaan
implementeren dat ik zojuist heb beschreven.
En ik ga het implementeren in een simpele Python functie.