Insertion Sort AlgorithmYouTube↗  IA↗(long shot)
Education  156.1K views 542 likes 28 dislikes   01 Jul 2011
Khan Academy 9.4M subscribers United States YouTube↗


Please select the problem
You must specify your email and describe the problem in detail
Describe your problem in detail if it's not obvious

Contributed subtitles
Korean yk k
Click to Play Video Click to Play Video
What I want to do in this video is
Wat ik in deze video wil behandelen is naar mijn mening
go over what I think is one of the more intuitive ways
een van de meest intuïtieve manieren om een lijst te sorteren.
to sort a list. It's how I would probably sort it, if I had to do it manually.
Dit zou de meest voor de hand liggende manier zijn om het handmatig te doen.
But I want to make it clear, it is not the most efficient way
Maar ik wil wel duidelijk maken dat het niet de meest efficiente manier is om een lijst te sorteren.
to sort a list.
Maar laten we—
I think it's a good starting point to getting warmed up
Ik denk dat dit een goed beginpunt is
with sorting lists.
om meer te weten te komen over het sorteren van lijsten.
It's called insertion_sort.
Het staat bekend onder de naam "Insertion Sort"
And I'm going to give a graphical description
Ik zal een grafische weergave geven
of the algorithm for insertion_sort.
van het algoritme voor insertion sort.
And just so you know what, algorithm
En weet je wat
sounds like a very fancy word, but an algorithm
algoritme klinkt als een heel hip woord.
is really just a way of sorting it, or a process for doing it,
Maar een algoritme is niet meer dan een manier om te sorteren of een process om het te doen
or a method for doing it.
of een manier van doen.
A program is a specific implementation of an algorithm,
Een programma is een specifieke implementatie van een algoritme
or it can be a specific implementation of an algorithm.
of kan een specifieke implementatie van een algoritme zijn.
Once I have a general algorithm, I could implement it in Python.
Als ik eenmaal een algemeen algoritme heb kan ik het implementeren in bijvoorbeeld Python
I could implement it in C. I could implement it in Java.
kan ik het implementeren in bijvoorbeeld C of kan ik het implementeren in Java.
Those are specific programs.
Dat zijn allemaal specifieke programma's
But they'd all be implementing the same way of doing the sort.
maar ze hebben allemaal dezelfde implementatie van dezelfde manier om te sorteren.
And that's what I'm describing here,
En dat is alles wat ik beschrijf—
the insertion_sort algorithm.
het algoritme voor Insertion Sort.
So let's just start with a simple example.
Laten we beginnen met een simpel voorbeeld:
Let's say that I have a list.
Laten we zeggen dat ik een lijst heb—
Let's say I have a Python list, because we're
Laten we zeggen dat ik een Python lijst heb
going to be working in Python for this.
omdat we hiervoor zullen gaan werken met Python
And that list is, let's say, it is 7, 3, 1, 2, 4, 6.
en die lijst is— laten we zeggen dat het [7,3,1,2,4,6] is.
And so the way that we do insertion_sort
We passen Insertion Sort toe op de lijst
is you go element by element.
door element per element te bekijken
And then you compare it to the elements before it.
en deze te vergelijken met de elementen ervoor
And then you look for the first element before it
en dan bekijk je het 1ste element
that it is actually less than.
dat daadwerkelijk kleiner is het huidige element
And then you just stick it right over there.
en dan zet je het huidige element rechts naast het gevonden element.
So let me show you what I'm talking about.
Ik zal even laten zien wat ik bedoel:
So you could start with the 7, the 0-th element over here.
Je kunt dus beginnen met de 7 dat is het 0de element in de lijst
But when you start with a 0-th element,
maar als je daarnaar kijkt—
you're like, hey, wait, there's nothing
als je met het 0de element begint
before it to compare it to.
zal je wel denken "Hey wacht, er staat niets voor om 7 mee te vergelijken"
So it really doesn't make sense to start with the 0-th element.
dus het heeft niet veel zin om te beginnen met het 0de element.
So really, if you were to implement this algorithm,
Dus als je dit algoritme zou implementeren
you'll start it with the third element.
zal je moeten beginnen met het 1ste element—
Or sorry, you'll start it with-- if this is the 0-th element,
Oh, sorry! Je begint met—
you'd start it with the first element right over here.
als dit het 0de element is dan begin je met het 1ste element rechts daarvaan.
If this is 0-th, this is first.
Dit is de 0de, dit is de 1ste
I know this can be a little confusing when
Ik weet dat dit verwarrend kan zijn
you refer to this as the first element.
maar dit is het 0de element.
But this one's the 0-th. So you start with this 3 here.
Dus je begint met de 3 hier
And then you start comparing it to all of the elements
en vergelijkt deze met alle elementen ervoor
before it. And as soon as you find an element that 3 is less than,
totdat je een element hebt gevonden dat groter is dan 3
you stick it in that part of the list.
dan plaats je de 3 op die positie in de lijst.
So what you do is you say, OK, is 3 less than 7?
Wat je eigenlijk zegt is: "Ok, is 3 kleiner dan 7?"
Well, yeah, it is less than 7.
"Ja het is kleiner dan 7."
So what you want to do is you want to shift 7 where the 3 is.
Wat je nu wilt doen is— is dat je de 7 en de 3 omruilt.
So let me put it out here.
Laat me het hier opschrijven—
So we're trying to compare 3 to everything before it right now.
dus we gebruiken— we vergelijken 3 met alles ervoor.
we vergelijken 3 met alles ervoor.
So you say, OK, is 3 less than 7?
Dus we zeggen: "Ok, is 3 kleiner dan 7?"
Yeah, it is less than 7.
"Ja, hij is kleiner dan 7."
So let's put the 7 where the 3 is.
Dus we plaatsen de 7 op de plaats van de 3
And let's put the 3 where the 7 is, especially
en we plaatsen de 3 op de plaats van de 7.
because there's nothing left to compare the 3 to.
Juist omdat er niks over is om met 3 te vergelijken
There's no elements before the 0-th element,
er is geen lager element— er is geen element voor het 0de element
so let's just stick the 3 right over there.
dus we plaatsen de 3 op die positie.
And so our list now looks like this.
Voor zover ziet onze lijst er als volgt uit
Our list now looks like 3, 7, 1, 2, 4, and 6.
onze lijst ziet er als volgt uit: [3,7,1,2,4,6]
And one thing you'll find interesting,
En iets wat interessant is—
or something to pay attention to,
iets waar je op moet letten—
is as we build this list-- so the 0-th element is now
tijdens het bouwen van de lijst— het 0de element is nu hoe dan ook kleiner dan het 1ste element
definitely less than the first element. And everything up to and including the first element
en alle elementen tot en met het 1ste element
is now sorted.
zijn nu gesorteerd.
alle elementen tot en met het 1ste element
And that will be true, as we keep going through this.
zijn nu gesorteerd. En dat blijft gelden als we doorgaan met het sorteren
As we keep going through higher and higher indexes, up to
als we doorgaan met de rest van de elementen
and including that index after we've done
tot en met de huidige positie
that pass will be sorted.
en als we die gedaan hebben is alles daarvoor gesorteerd.
And I'll try to point that out as we go along.
Ik zal het aanwijzen naarmate we vorderen
So we did the first index.
Dus, we hebben de eerste positie gedaan
So we already did the first index. Now we can move on to the second element,
laten we nu verder gaan met het 2de element
which is this 1 over here.
dat is het element hier.
And so you take that 1.
Nu pakken we dit element—
I'll put it on the side right over here.
Ik schrijf het aan de zijkant hier—
You take that 1 and you compare it to each of the elements
je pakt dat element en vergelijkt het
before it.
met elk element dat ervoor staat:
OK, is 1 less than 7?
"Ok, is 1 kleiner dan 7?"
Sure, 1 is less than 7.
"Ja, 1 IS kleiner dan 7."
So let's stick the 7 where the 1 is.
dus laten we de 7 op de plaats van de 1 zetten.
And then you could just keep comparing,
Nu kan je of verder gaan met vergelijken
or you could just stick the 1 where the 7 is.
of je kan de 1 op de plaats van de 7 zetten.
And then you would say, OK, is 1 less than 3?
En dan vragen we ons af: "Ok, is 1 kleiner dan 3?"
Well, yeah, sure.
"Ja, natuurlijk is 1 kleiner dan 3."
It's less than 3. So let's stick the 3 where the 1 is.
Dus laten we de 3 op de plaats van de 1 zetten
And let's put the 1 where the 3 is.
en laten we de 1 op de plaats van de 3 zetten.
So what is our list now?
Dus hoe ziet onze lijst er nu uit?
Our list now is going to look like 1, 1, 3, 7, 2, 4, 6.
Onze lijst ziet er nu als volgt uit— ziet er nu als volgt uit [1,3,7,2,4,6]
So notice, after we've gotten to the n-th index-- so
Het valt op dat nadat we bij de nde positie zijn aangekomen—
in this case, this was the index of 2
dus in dit geval is dat de 2de positie
where that 1 was right over there-- everything up
waar de 1ste positie hier was—
to and including that index is sorted.
alles tot en met deze positie is nu gesorteerd.
This part right here is sorted.
De elementen hier zijn gesorteerd.
Other things are going to be thrown in here, probably,
Het is zo dat— dat andere dingen hierin
as we go on.
zullen worden gegooid naarmate we vorderen
But so far, this part is sorted.
maar tot nu toe zijn deze elementen gesorteerd.
So you can see by the time we get to the end of this list,
Dus je kan zien dat tegen de tijd we aan het einde van de lijst zijn
everything is going to be sorted.
de hele lijst gesorteerd is.
So let's now go to the next index,
Laten we nu verder gaan met de volgende positie
or the next item in the list.
of het volgende element in de lijst
And that is this 2 over here.
en dat is deze 2.
Dat is deze 2.
And so we compare the 2 to the 7.
Nu vergelijken we de 2 met de 7
2 is definitely less than the 7, so let's put
2 is natuurlijk kleiner dan 7
the 7 where the 2 is, and let's put the 2 where the 7 is.
dus plaatsen we de 7 waar de 2 is en plaatsen we de 2 waar de 7 is.
Now you compare the 2 to the 3.
Nu vergelijken we de 2 met de 3
2 is less than 3.
2 is kleiner dan 3
So let's put the 3 where the 2 is, and let's
dus plaatsen we de 3 waar de 2 is
put the 2 where the 3 is.
en plaatsen we de 2 waar de 3 is.
Then compare 2 to 1.
Nu vergelijken we 2 met 1
Is 2 less than 1?
"Is 2 kleiner dan 1?"
No, it is not less than 1, so we don't have to do anything else.
"Nee, 2 is niet kleiner dan 1." Dus we hoeven niks meer te doen.
We don't have to keep going to the left.
We hoeven niet verder naar links te kijken
And so now, after this pass-- in this pass,
Dus na deze ronde—
we were comparing this 2 item to everything before that.
in deze ronden vergeleken we het element 2 met alles wat ervoor stond—
So after this pass, our list looks like this.
dus na deze ronde ziet onze lijst er als volgt uit:
Our list looks like 1, 2, 3, 7, 4, 6.
Onze lijst ziet er als volgt uit: [1,2,3,7,4,6].
And notice everything up to and including the third item,
Nu is alles tot en met het 3de element—
so 0-th 1 2, third item, is now sorted.
de 0de, 1ste, 2de en 3de elementen— zijn nu gesorteerd.
And now we're ready to look at the next element in the list.
Nu kunnen we naar de volgende kijken— het volgende element in de lijst.
And one thing I want to make clear,
Ik wil één ding duidelijk maken:
when you actually implement it, there's
als je het daadwerkelijk implementeert,
a couple of ways to do it.
zijn er verschillende manieren om het te doen.
So in this example, we said, hey, 2 is less than 7.
Je hoeft niet altijd— in dit voorbeeld zeiden we:
We had the 7 replace where the 2 is, which you should do.
"Hey, is 2 kleiner dan 7?" De 7 vervangt de plaats waar de 2 is
And then we had the 2 replace where the 7 is.
wat ook moet werken. En dan hadden we de 2 vervangen door een 7.
But the reality is you can keep going down,
Maar daadwerkelijk
until you find a good place to put the 2,
kan je eigen doorgaan totdat je een juiste plaats vind voor de 2
and shifting everything to the right as you do it,
en terwijl je dit doet alles een positie naar rechts te schuiven
and then putting the 2 in.
en dan de 2 ertussen te voegen.
Although this way, it's a little bit easier to keep track of.
Ondanks dat deze manier iets makkelijker is om bij te houden.
And well, maybe we'll explore different ways
En wow, misschien zien we wel verschillende manieren om het te doen
to do it when we actually implement the algorithm.
als we het algoritme daadwerkelijk gaan implementeren.
Anyway, let's look at this 4.
Hoe dan ook, laten we naar deze 4 kijken.
Same exact idea.
Het is weer hetzelfde idee:
4 is less than 7, so let's put the 7
4 is kleiner dan 7
where the 4 is and put the 4 where the 7 is.
dus plaatsen we de 7 waar de 4 is en plaatsen we de 4 waar de 7 is.
Is 4 less than 3?
"Is 4 kleiner dan 3?"
No, it's not less than 3, so we stop.
"Nee, het is niet kleiner dan 3."
We're done.
Dus nu kunnen we stoppen, we zijn klaar.
Now everything up to and including the fourth item
Nu is alles tot en met het 4de element gesorteerd.
in this list, 0, 1, 2, 3, 4, is now sorted.
in de lijst is —01234— nu gesorteerd.
And now our list looks like-- let
En nu ziet onze lijst er als volgt uit—
me scroll down a little bit-- now our list looks like this.
even een stukje naar beneden scrollen— Nu ziet onze lijst er als volgt uit—
Let me write it down.
je schrijft het op als
It is 1, 2, 3, 4, 7, and then 6.
[1,2,3,4,7,6]
And now we can go to this last element in the list.
En nu kunnen we verder gaan met het laatste element in de lijst—
This is the 6 that we're now comparing.
Het is deze 6 die we nu gaan vergelijken—
Actually, the last time we did this,
en het is weer hetzelfde als de laatste keer dat we dit deden
it was a 4 that we cared about.
toen we ons concentreerde op de 4
But now we care about the 6.
maar nu concentreren we ons op de 6
Is 6 less than 7?
"Is 6 kleiner dan 7?" "Ja, dat is hij zeker."
Sure, it is. So let's put 7 where the 6 is.
dus plaatsen we de 7 waar de 6 is
Let's put a 6 where the 7 is.
en plaatsen we de 6 waar de 7 is.
Is 6 less than 4?
"Is 6 kleiner dan 4?" "Nee, dat is hij niet"
No, it's not.
Ok, dus nu kunnen we stoppen.
And so we stop, because we know that this
Omdat we weten dat dit gesorteerd zal zijn.
is going to be sorted. If we went any further, we're just
Als we verder zouden gaan, zouden we alleen maar
going to get elements that are less than or equal to 4.
elementen krijgen die kleiner of gelijk zijn aan 4.
So we are done. We have sorted this list.
Dus nu zijn we klaar, we hebben de lijst gesorteerd.
The sorted list is now 1, 2, 3, 4, 6, and 7.
De gesorteerde lijst is nu: [1,2,3,4,6,7]
In the next video, I'm actually going
In de volgende video
to try to implement this algorithm that I just
zullen we proberen het algoritme te gaan
described.
implementeren dat ik zojuist heb beschreven.
And I'm going to implement it in a simple Python function.
En ik ga het implementeren in een simpele Python functie.
Similar videos:

The beauty of algebra | Introduction to algebra | Algebra I | Khan Academy
Khan Academy
3.7M views 11.7K likes 790 dislikes 09 Feb 201264% match







BALI, Indonesia: kopi Luwak, waterfall and rice terrace near Ubud
Renata Pereira
417.8K views 12.4K likes 146 dislikes 22 May 202064% match








What kids can teach adults about asking for help | YeYoon Kim
TED
34.1K views 1.3K likes 47 dislikes 28 Oct 202063% match



Intuition on static and kinetic friction comparisons | Physics | Khan Academy
Khan Academy
298K views 641 likes 28 dislikes 20 Jun 201163% match

Ljubljana, Slovenia: City of Dragons | What to See and Do in a Day
Eileen Aldis
7.9K views 329 likes 7 dislikes 05 Dec 202063% match











How to find meaning when reality hits you | Manisha Koirala | TEDxJaipur
TEDx Talks
2.5M views 61.1K likes 1K dislikes 23 Mar 201762% match

Is it time for Joanne's Foot Care? How does lymphoma start? Dr Nail Nipper makes a Visit (2021)
Dr Nail Nipper
33.2K views 1.1K likes 36 dislikes 12 Feb 202162% match






Introduction to Programs Data Types and Variables
Khan Academy
965.6K views 3K likes 70 dislikes 30 Jun 201162% match




How I beat stage fright | Joe Kowan
TED
532.3K views 5K likes 303 dislikes 24 Jan 201462% match






Give yourself permission to be creative | Ethan Hawke | TED
TED
2.9M views 175.3K likes -1 dislikes 11 Aug 202062% match




Trying Indian Food in Tokyo, Japan!
Samuel and Audrey - Travel and Food Videos
974.7K views 12.3K likes 544 dislikes 28 Nov 201861% match







A promising test for pancreatic cancer ... from a teenager | Jack Andraka
TED
416K views 5K likes 91 dislikes 11 Jul 201361% match





Be humble -- and other lessons from the philosophy of water | Raymond Tang
TED
370.1K views 11.3K likes 204 dislikes 20 Mar 201861% match




Sarah Bergbreiter: Why I make robots the size of a grain of rice
TED
266K views 4K likes 267 dislikes 21 Jan 201561% match





All it takes is 10 mindful minutes | Andy Puddicombe
TED
4.2M views 71.2K likes 1.4K dislikes 11 Jan 201361% match






Introduction to light | Electronic structure of atoms | Chemistry | Khan Academy
Khan Academy
804.8K views 2.5K likes 101 dislikes 12 Jul 201161% match



Math isn't hard, it's a language | Randy Palisoc | TEDxManhattanBeach
TEDx Talks
2.6M views 71.3K likes 2.1K dislikes 05 Dec 201461% match



Bill Gates: Teachers need real feedback
TED
2.3M views 48.7K likes 1.1K dislikes 08 May 201360% match






Autofocusing reading glasses of the future | Nitish Padmanaban
TED
243.1K views 8.9K likes 177 dislikes 18 Jun 202060% match




What reality are you creating for yourself? | Isaac Lidsky
TED
554.4K views 17.8K likes 181 dislikes 27 Oct 201660% match






Gever Tulley: 5 dangerous things you should let your kids do
TED
285.5K views 1.7K likes 65 dislikes 09 Jan 200860% match






Deuil : Comment Ils Ont Surmonté La Perte de Leurs Proches Morts Au Feu
Vincent Firelife
3.1K views 241 likes 1 dislikes 10 Mar 202160% match















Scale of earth and sun | Scale of the universe | Cosmology & Astronomy | Khan Academy
Khan Academy
746.3K views 2.7K likes 137 dislikes 16 Nov 201060% match






Vipassana Meditation and Body Sensation: Eilona Ariel at TEDxJaffa 2013
TEDx Talks
1.1M views 19.9K likes 368 dislikes 15 Nov 201360% match

Avi Reichental: What’s next in 3D printing
TED
252.5K views 3.1K likes 116 dislikes 18 Sep 201460% match




Is life really that complex? | Hannah Fry | TEDxUCL
TEDx Talks
565K views 4.9K likes 194 dislikes 02 Jul 201260% match





BALI, Indonesia: an active volcano and the most famous temple 😮
Renata Pereira
718K views 17.9K likes -1 dislikes 16 May 202060% match








A simple way to break a bad habit | Judson Brewer
TED
10.7M views 201.8K likes 0 dislikes 24 Feb 201660% match







Our campaign to ban plastic bags in Bali | Melati and Isabel Wijsen
TED
272.1K views 4.3K likes 386 dislikes 19 Feb 201660% match





SAPATINHO DE TRICÔ PASSO A PASSO PARA INICIANTES
Knitting Art of Loving
903.2K views 22.4K likes -1 dislikes 24 Aug 202060% match










Settings Privacy About Contact Donate