Insertion Sort in Python Khan Academy English Czech

Insertion Sort in PythonYouTube↗ IA↗(long shot)
Education 104.7K views 451 likes 20 dislikes 01 Jul 2011 Show Contributors 1

Khan Academy 9.4M subscribers United States YouTube↗

Contributed subtitles

Korean yk k

Click to Play Video

What I'm going to do in this video

is attempt to create an implementation of the insertion

se pokusím vytvořit implementaci

sort algorithm that we talked about in the last video,

"insertion sort" algoritmu (řazení vkládáním) o kterém jsme mluvili v posledním videu.

and I'll do it as a Python function.

Udělám to jako funkci v Pythonu.

So I'll call the Python function insertion sort,

Tuto funkci nazvu "insertion_sort()"...

and it will take in a list.

a bude brát seznam...

So the list is its parameter in the function definition.

takže "list" je její parametr v definici funkce

Someone would have to pass list as an argument.

a my jí budeme muset předávat seznam jako argument.

And let's-- what we're going to do is we're going to step

A co teď uděláme je,

through each of these slots in the list.

projdeme všechny pozice v seznamu.

I guess we could call it that way.

Tak by se tomu dalo říkat.

So let's say 4 index in and range.

Řekneme "for index in range():".

We could start at the leftmost slot in the list.

Můžeme začít na levém konci seznamu.

So we could just say len-- len just

Můžeme říct "len(list)"...

means it's short for length-- so length of the list.

"len" prostě znamená "délka" [zkratka pro "length"], délka seznamu.

So what this would do, this would start index.

Toto tedy začne "index"...

So let's say the list has four elements in it.

řekněme, že seznam "list" má čtyři prvky,

Then len list, this right here would be 4,

potom "len(list)", tady,

would evaluate to 4.

by bylo 4, vyhodnotilo by se jako 4.

Range of 4 would produce a list that

"range(4)" by vyrobilo seznam,

has the elements 0, 1, 2, 3 in it.

který má prvky [0, 1, 2, 3].

And so index would be able to step

Proměnná "index" by procházela přes

through the different indices for this list right over here.

různé indexy prvků v tomto seznamu přímo tady.

And we could do it that way, but you

A tak bychom to mohli udělat,

might remember from the previous video

ale z předcházejícího videa si možná vzpomínáte,

that when you're doing the insertion sort,

že když provádíte "insertion sort",

it doesn't actually make sense to start

tak vlastně nedává smysl

at the very leftmost element, because there's

začínat na levém konci,

nothing to compare it to to the left.

protože nalevo od něj není nic, z čím ho porovnat.

So we can actually just start at the second to the leftmost

Takže vlastně můžeme prostě začít na druhém prvku zleva.

element. And the leftmost element is the 0-th item,

A nejlevější prvek je 0. prvek,

so we can start at the first item.

takže můžeme začít na 1. prvku.

So now if the list has a length of 4,

Nyní tedy, pokud je seznam délky 4,

this right here will produce 1, 2, 3.

tohle vyrobí [1, 2, 3].

So it would-- 1 would be the second to the leftmost element,

Tudíž 1 je druhý prvek zleva.

2 would be the next one to the right, 3 would be the last one.

2 je další prvek na pravo.

Remember, we always start our indices at 0.

3 je poslední prvek. Pamatujte si, indexy vždycky začínají od 0...

The 0-th term is the leftmost element in a list.

0. prvek je nejlevější prvek v seznamu.

Dobře, můžeme přes to projít.

We can step through that. And let's get the value of right--

Získejme hodnotu - v daném okamžiku -

at that point in time of the element that is at that index.

prvku, který je na tomto indexu.

So that way we don't have to keep finding it.

Takhle ho nemusíme pokaždé znovu hledat,

Value is equal to list index.

"value" se rovná "list[index]".

And this, by no means, is going to be

Tohle rozhodně nebude

the most efficient implementation of even

nejefektivnější možná implementace

insertion sort.

"insertion sortu".

It's just going to be my best try writing it in real time

Bude to můj nejlepší pokus,

and in a way that hopefully you might be able to understand it.

když to píšu v "naživo", a snad způsobem, kterému budete schopni porozumět.

So value is just the item in the list at each of those indexes

"value" je tedy prostě prvek v seznamu na každém z těchto indexů,

that we're now going to compare to all of the items

který teď budeme porovnávat

to the left of it.

se všemi prvky nalevo od něj.

And what I want to do is compare value to each item

Co chci udělat je... porovnat hodnotu... chci porovnat hodnotu

to the left of it.

s každým prvkem nalevo od ní.

So let's define a variable i.

Tak si zadefinujme proměnnou "i",

Let's let this be the index of the things

která bude idexem prvků,

that I want to compare value to.

se kterými chci "value" porovnávat.

And right from the get-go, I want

to compare value to the thing that is left of it.

chci porovnávat "value" s prvkem, který je nalevo od ní.

So i should have one lower of an index than index,

Tudíž "i" by měl být o 1 menší, než index, na kterém je "value".

so index minus 1.

So this is the index of the item that is directly left to it.

Toto bude index prvku, který přímo nalevo od "value".

But we're going to keep taking i lower and lower,

Ale budeme "i" snižovat dále a dále.

so we can keep comparing value to things further and further

Abychom mohli pokračovat v porovnávání hodnoty s věcmi dále a dále nalevo.

Co tedy chceme udělat je...

And so what we want to do is we're going to want to keep comparing further and further

chceme porovnávat dále a dále nalevo

left until i has gotten all the way to the beginning of the list.

dokud "i" se nedostane až na začátek seznamu.

And i has gotten all the way to the beginning

A když se "i" dostane až na začátek seznamu,

of the list when it is equal to 0.

tak bude rovné 0.

So what we want to do is we want to perform this

Co tedy chceme udělat je,

while i is greater than or equal to 0,

chceme udělat tohle dokud je "i" větší nebo rovno 0.

because if we keep taking i lower and lower and lower--

Protože pokud budeme "i" snižovat dále a dále,

we're going further and further to the left in the list--

budeme se v seznamu pohybovat dále a dále

we don't want to try to perform it when i is further,

nalevo. To nechceme udělat

is a negative number.

pokud je "i" - víte co - dále - je negativní -

That'll just start doing crazy things.

To by prostě začalo dělat divoké věci.

So while i is greater than or equal to 0,

Takže dokud je "i" větší nebo rovno 0...

what I'm going to do is I'm going

co udělám je,

to keep pushing i further and further to the left.

budu tlačit "i" dále a dále doleva.

So let's try it this way.

Zkusme me to takto, první věc, kterou chci udělat...

So the first thing I want to do-- we've already pushed it to the left once.

už jsme to dotlačili o jednu doleva,

So let's compare.

tak porovnáme,

So if value is less than the-- this thing

jestli je "value" menší, než...

keeps saying syntax error, because it's

tahle věc pořád říká "syntax error",

waiting for me to keep typing.

protože čeká, že to dopíšu...

If value is less than the item that is now at index i,

pokude je "value" menší, než prvek, který je teď na indexu "i".

so the item at index i, list, the item at index i

Tudíž prvek, který je na indexu "i" (list[i]), prvek na indexu "i" je tento přímo tady.

is this right here. So if it is less than that, let's

Pokud je tedy menší než toto,

shift the item that's over here.

posuňme prvek, který je tamhle...

Let's shift it one to the right.

posuňme ho o jedno doprava.

So the right slot is i plus 1.

Index napravo je tedy "i + 1"

And I can't just say it's index, because remember,

a nemůžu jednoduše říct, že je to "index",

I'm going to keep pulling i in lower and lower and lower.

protože si pamatujte, že budu "i" tahat níže a níže.

Because right now, index is i.

Protože právě teď má "i" hodnotu "index - 1"

Right now i is index minus 1 in the first pass

v prvním průchodu touto "while" smyčkou,

through this while loop, but I'm going

ale já - jak uvidíte za sekundu -

to-- as you'll see in a second, I'm going to keep lowering i.

budu "i" snižovat,

So it'll always won't be one left of index.

takže vždycky nebude o jedna nalevo od "index".

So I'm going to say wherever i is, let's take the spot

Říkám tedy ať už je "i" kdekoliv,

one to the right of i.

vezměme pozici o jednu napravo od "i"...

o jednu napravo od toho...

So that's i plus 1 as its index.

takže "i + 1" je její index.

And let's replace that with whatever's at list,

A nahradmě to tím, co je v "list[i]",

or whatever is at i, at slot i.

tím, co je na pozici "i", ať už je to cokoliv.

So we have essentially taken this thing right over here,

Takže jsme v podstatě vzali tuhle věc tady napravo

whatever number was there, and we are putting it

ať už tam bylo jakékoliv číslo,

in the slot that is one to the right of it.

a dáváme ho do pozice, která je o jednu napravo od toho. A potom,

And then-- and actually the way we're setting up

a způsob, jakým vlastně stavíme tento algoritmus.

that algorithm, whatever's there is actually going to be-- well,

Ať už tam bude cokoliv...

I won't talk about that.

No... o tom nebudu mluvit.

We'll step through it and see how it all plays out.

Projdeme si tím a uvidíme, jak to bude fungovat.

And then we can shift value to the left.

A potom můžeme posunout "value" doleva.

So whatever was in this slot right over here

Cokoliv, co bylo v této pozici tady

will be replaced by value.

bude nahrazeno "value".

So list i will equal value.

"list[i]" bude tedy rovný "value".

So one way to think about it-- let me write a comment here.

Jeden způsob, jak se o tom dá přemýšlet...

Shift what was-- shift number in slot i to slot i plus 1.

...nechtě mě tady dopsat komentář... posuň to, co bylo... posuň číslo z pozice "i" do pozice "i + 1",

Or you can say bucket i plus 1, I

nebo "kyblík" "i + 1"

guess is one way to think about it.

...tak se o tom také dá přemýšlet...

And then you could say shift number right.

A potom můžete říct, posuň číslo doprava... takhle to nazvu...

Let me call it this way. Shift number right in slot.

posuň číslo doprava... v pozici...

Let me write it this way.

napíšeme to takhle...

Shift number in slot i right to slot i plus 1.

posuň číslo na pozici "i" doprava na pozici "i + 1"

And then over here, we are shifting--

A potom tady, posunujeme...

shift value left into slot i.

posuň "value" doleva do pozice "i".

And so if you remember what we did in the last video,

A pokud si pamatujete co jsme dělali v posledním videu,

this is exactly describing it.

tak to přesně popisuje.

We're comparing value to the thing to the left of it.

Porovnáváme "value" s číslem, které je nalevo od ní.

If it's less than it, then whatever number was in that box

Pokud je to méně, pak číslo nalevo, ať je jakékoli,

to the left of it, the slot to the left, shift it to the right, and then shift value to the left.

posuneme doprava a pak "value" doleva.

And now compare value to something 1 lower than that.

Nyní porovnáme "value" s nižším číslem.

So we want to decrement i.

Chceme dekrementovat "i", chceme snížit "i",

We want to lower i. Decrement is just increment down.

dekrementování je prostě inkrementování směrem dolů.

So i is equal to i minus 1.

Do "i" dosadíme "i-1",

And then we'll perform the loop over again.

a pak provedeme smyčku znovu.

And now value will be compared-- now

Teď bude "value" porovnána...

i is two to the left of index.

teď je "i" o dvě pozice nalevo od "index"

Compare it to that.

... porovnána s ním.

If it is less than it, shift that to the right

Pokud je nižší než "value", posuneme číslo doprava

and shift value again to the left.

a "value" posuneme znovu doleva.

Now, what if we have the situation where value is not

Co když nastane situace kdy "value" není nižší, než

less than the item that you're comparing it to?

číslo se kterým ji porovnáváme?

Well, if it's not less than the item

Pokud není nižší,

that you're comparing it to and that that means that value is already going to be in the right place,

znamená to, že "value" už je na správném místě.

it also means that you're done, that you don't

A to znamená, že jsem hotoví,

need to shift value any more to the left,

a nemusíme "value" posouvat dál doleva.

and you don't have to shift any of the stuff

Nemusíme posouvat čísla doleva

to the left any more to the right.

So then we are done.

And I think this could work unless I've

Myslím, že by to mohlo fungovat,

made some silly mistake.

pokud jsem neudělal nějakou hloupou chybu.

So let's try to see if I can get this--

Podívejme se, jestli se mi povede...

if this actually works as a sorting algorithm.

jestli to funguje jako třídící algoritmus.

So let me save it-- insertion sort-- and let me run it.

Uložím program "insertion_sort", a spustím ho.

All right. So I didn't have any at least syntax mistakes.

Nemám tam žádné syntaktické chyby.

Syntax just means the actual characters I use.

Syntaxe znamená, jaké jsem použil znaky...

I didn't forget to put a colon here or a greater than sign.

Nezapomněl jsem na čárku, anebo znak "větší než".

It was actually able to process this, interpret this right over

Interpret dokáže kód přečíst,

But let's see if it actually works.

Ale podívejme se, jestli to skutečně funguje.

So let me define a list.

Definujeme seznam "a".

Let's say it is 7, 1, 3, 5, 9, 2.

Řekněme [7,1,3,5,9,2]

And let me put another 3 in there.

přidám do něj ještě číslo 3.

So that is a, and then let me see.

To je seznam "a".

This is the moment of truth.

Podívejme se... tohle je okamžik pravdy,

Insertion sort of a-- let's see what happens.

insertion_sort(a), podívejme se, co se stane.

So remember, we're sorting it in place.

Pamatujte, třídíme přímo v seznamu,

This function doesn't return anything,

tato funkce nemá návratovou hodnotu.

but it should take whatever list that was and had changed up

Měla by vzít jakýkoli seznam,

all of the elements so that now they are in order.

a uspořádat jeho prvky tak,

So this is the moment of truth.

aby byly seřazené. Tohle je okamžik pravdy.

Let's see what a looks like.

Podívejme se, jak "a" vypadá.

Seznam je seřazený!

It is sorted. So I don't think I made any major mistakes.

Myslím, že jsem neudělal žádnou velkou chybu.

So there you go.

You have insertion-- a version of insertion sort.

varianta algoritmu třídění vkládáním.

Similar videos:

Stepping Through Insertion Sort Function
Khan Academy
32.8K views 124 likes 2 dislikes 01 Jul 201137% match

Insertion Sort Algorithm
Khan Academy
156.1K views 542 likes 28 dislikes 01 Jul 201127% match

Insertion Sort
CS50
526K views 0 likes 0 dislikes 26 Sep 201225% match

Settings Privacy About Contact Donate