Stepping Through Insertion Sort Function Khan Academy English Spanish

Stepping Through Insertion Sort FunctionYouTube↗ IA↗(long shot)
Education 32.8K views 124 likes 2 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 want to do in this video is step through the insertion_sort function

Lo que quiero hacer en este video es explicar paso a paso la función "ordenar"

that we wrote in the last video.

que escribimos en el video anterior

But before I do that, I actually want

Pero antes que lo haga, quiero de verdad enfocarme en una parte de la función

to just focus on one part of it, because I realize that I used something that you probably don't recognize,

debido a que me di cuenta que usé algo que ustedes probablemente no reconozcan

because we haven't used it before.

debido a que no lo hemos usado antes.

I used the keyword right over here.

yo usé...usé el término clave justo aquí. Escribí "BREAK"

I used break. And you might guess what break means,

y pueden imaginarse lo que hace "BREAK"

but now I'll explain it explicitly.

pero lo explicare de forma explicita.

What break means is break out of the smallest loop

El significado de "BREAK" es: salirse del bucle menor WHILE que estabas ejecutando

that you were doing. So we were taking our item, and we kept comparing it to the thing to the left of it.

asi que hemos estado tomando nuestro item y lo mantenemos comparandose con el de la izquierda

Or we were taking value and comparing things

Hemos tomado a "value" y lo mantenemos comparandose con el de la izquierda

to the left of it. And as soon as we found value not being less than the thing

en el momento en que encontremos que "value" no es menor que el de la izquierda, decimos:

to the left of it, we said, hey, we're done. We don't have to keep going to the left.

Epa, estamos listo, no tenemos que seguir hacia la izquierda

And in that situation, I want to break the loop. So we're breaking this while loop.

y en ese caso, quiero salir del bucle, asi que nos estaremos saliendo del bucle "WHILE"

And then we just continue in our next iteration of this for loop

y entonces simplemente continuamos con nuestra proxima interacción del bucle "FOR" aquí

over here. So that's what break did.

Asi que eso es lo que hace el "BREAK"

Now with that out of the way, let's actually step through this program on a simple example.

Aclarado esto, vamos ahora a explicar por paso este programa con un ejemplo sencillo.

So let's say that someone calls-- well, let's just

Asi que digamos que alguien llama... definamos

define a to be equal to-- let me think of a fairly simple list--

definamos que "a" sea igual a...dejenme crear una lista bastante sencilla...

2, 1, 2, 1, I don't know, 2, 1, 3-- 2, 1, 3, 2, I think,

2, 1...no creo... 2, 1, 3, 2

is a good list over there. And let's assume that we are calling insertion_sort on a.

Creo que esa lista es un buen ejemplo, y asumamos que llamamos la función "insertion_sort" "insertion<u>sort..." "insertion</u>sort" a ser aplicada en "a"

Let's think about what's going to happen.

Veamos que es lo que va a pasar.

Well, the first thing, of course, that list-- let's keep track of all of the variables here.

Bueno, lo primero por supuesto es el "list"...sigamosle la pista a todas las variables aca

So list is, right from the get-go, going to refer to 2, 1, 3, 2.

Así que uno de... así que "list" proveniente de lo solicitado, se va a referir a: [2, 1, 3, 2].

That's list right from the get-go.

ese "list" proveniente de lo solicitado, y luego entramos dentro de la función

And then we enter into the function, for index in range. And let's parse this part right over here.

"For index in range" y analicemos esa parte justo aquí.

So what is len of the list? So len of our list is the same thing as len of 2, 1, 3, 2.

Que significa el " len (list)." El "LEN" de nuestra lista es lo mismo que "len( [2, 1, 3, 2])"

And this is just really the number of elements. Len is short for length-- not that much shorter.

y lo que resulta es simplemente el número de elementos del "list". "LEN" es el diminutivo de "LENGHT". No tan corto,

But len of this is just going to be 1, 2, 3, 4.

pero el largo de esto será el largo de: uno, dos, tres, cuatro.

It's going to be equal to four elements.

Será igual a 4 elementos.

So this right over here is going to be 4. And then the call, range between 1 and len of list is 4.

Así que esto de aquí, va a ser 4, y en la parte: "range entre 1 y el largo del "list" que es 4

This will return the list starting at 1, up to, but not including 4, 1, 2, 3.

Esto originará el "list"...esto originará un "list", comenzando con 1 y terminando en 4, sin incluir el 4. 1, 2, 3.

And so these are the indices we want to use,

Así que estos son los indices que queremos usar, porque este...

because the first index is this right over here. Second index is this right over here.

el primer indice es este de aquí, el segundo indice este de aca

And the third index is that over here.

y el tercer indice este de aquí.

Remember, this is the 0-th index. So index is going to keep incrementing between these two.

Recuerda, este es el indice cero. Así que los indices se incrementan entre estos dos.

It's going to be 1 first, then 3, then 2.

Primero será 1, luego 3, luego 2.

So let me just create our variable index whose scope is inside of the for loop.

Así que solo... vamos a crear nuestra variable "index" que va a ser aquella cuyo ámbito está dentro del bucle FOR

So let's say we have index.

Digamos que tenemos "index".

Index is going to start off being the first item in this list right here, the list generated by range, 1 comma len of list.

"index" comenzara siendo el primer ítem. El primer ítem en este lista de aquí. La lista generada por el range (1 , LEN ( list.))

So index is going to start off being 1.

Así que "index" comenzará siendo 1

And then over here, we say value is equal to the index element in list.

y luego aquí, decimos que "value" es igual al elemento "index" de "list".

So let me define our variable value. So what is list of 1?

Definamos nuestra variable "value". ¿Que es list [ 1 ]?

So what is the first element in the list? It's the 0-th element. This is the first element.

¿Cual es el primer elemento de "list"? Este es el elemento cero, este es el primer elemento.

So we're looking at this right over here.

Estamos buscando a esto de aquí.

It is the first element, so that's fair enough. And then we define i to be index minus 1.

Esto es... es el primer elemento. Eso es bastante cierto, y luego definimos "i" que sea "index" menos 1

So let me put i over here.

Pongamos "i" aquí y le ponemos otro color.

Do a new color. So now let's do i. It is index minus 1. Index is 1, so index minus 1 is 0.

Ahora resolvemos "i". Es "index" menos 1. "index" vale 1 por lo que 1 menos 1 es igual a cero.

So it's the index of the item to the left of value. So that is going to be 0.

Así que es el indice del ítem a la izquierdo de "value" (indice1). Por lo que será igual a cero, indice cero.

This index is 1, this is 0.

Este indice es 1, esto es indice cero

And then we're saying, while i is greater than or equal to 0, do all of this business over here.

y luego estamos diciendo: Mientras "i" es mayor o igual a cero que haga todo esto de aquí.

And the first thing that we do over here is we compare value to the object that is at the i-th element in the list.

y lo primero que hacemos aquí es comparar "value"... comparamos "value" al objeto que es el "i'n" elemento de "list".

So let me write that over here. So list at i.

Lo escribo aquí. Asi que el "list"... "list" en "i"

So that is going to be the 0-th element in the list, so that is 2.

Eso será el elemento cero de "list". Eso es 2.

So we're comparing value.

Estamos comparando "value". Estamos comparando 1.

We're comparing 1. We're saying if 1 is less than the i-th element in list,

Estamos diciendo: Si 1 es menor que el elemento "i´n" de "list".

if 1 is less than 2, then do this. Well, 1 is definitely less than 2.

Si 1 es menor que 2, hacer esto. Bien, 1 es definitivamente menor que 2.

We're essentially taking 1 and comparing it to the thing to the left and saying, hey,

Basicamente tomamos 1 y lo comparamos con lo que esta a su izquierda (2), y decimos:

it's less than that.

Epa, es menor que esto, por lo que es menor que esto.

So it's less than that. So let's shift this 2 to the right, and let's shift 1 to the left.

Mudemos este 2 a la derecha y mudemos el 1 a la izquierda

And so we go into here and we say, list i plus 1.

y vamos aquí y decimos "list" de ("i" + 1).

So what's i plus 1? i plus 1 is 1. So this is list of 1, so this slot right over here.

Entonces, ¿Que es es ("i" + 1)? (0 + 1) es igual a 1. Asi que esto es "list [1]. Por lo que este posición de aquí.

So this, in yellow that I just underlined, that's this slot right over here. i is 0.

Así que esto... en amarillo que no se... este posición de aquí.

i plus 1 is 1. So the first item, or the first slot,

El valor de "i" es cero. "i" mas 1 es igual a 1, por lo que "i'n"... el primer ítem o la primera posición es este de aquí.

is this slot right over here. Let's replace it with whatever is at list

Lo reemplazamos por lo que sea que este en "list [ i ]".

and whatever is in the i-th element, or whatever is in the 0 slot, I guess I should call it.

Cual sea el valor de "i'n" o cual sea el valor de la posición cero como creo que debo llamarlo.

So let's replace it with this 2. Right?

Lo reemplazamos con este 2. Ok, voy a aclarar esto.

Let me make it clear. And this time around, this is 2, and this is the slot where the 1 was.

Esta vez, por aca esto es 2 y esto es la posición donde era 1

So we're going to put this-- we're going to replace that with 2.

Vamos a poner esto... Vamos a reemplazar esto con 2

And then in the place where the 2 was, we're going to replace it with value.

y luego en el lugar donde estaba el 2 lo vamos a reemplazar con "value"

And remember, value was set to 1.

y recuerden que "value" fue establecido en 1.

So value is set to 1. And so our list now looks like 1, 2, 3, 2.

Así que "value" es 1, por lo que nuestro "list" ahora se ve asi: 1, 2, 3, 2

And hopefully, this looks familiar, if you remember when we first described the insertion_sort algorithm.

espero que esto te sea familiar si recuerdas cuando antes describimos el algoritmo de la función "insertion_sort"

So we go through there. And now we want to decrement i.

Así que avanzamos y no... y luego nosotros... y ahora queremos disminuir "i".

We say whatever i was-- it's 1-- we subtract 1. So now it's 0.

Decimos que cual sea era el valor de "i", que es 1, le restamos 1, por lo que ahora es cero.

So the new value for i is 0.

Asi que el nuevo valor para "i" es cero. El nuevo valor para "i" es cero.

Actually, no, no. Sorry. Whatever i was. i was 0.

En verdad... no, disculpen. Cual sea era el valor de "i". Era cero, "i" era cero

You subtract 1 from that, and now i is going to be negative 1.

Se le resta 1 de eso, y ahora "i" sera -1

Ahora será... ahora "i" sera (-1)

And then we go to the while loop. It says while i is greater than or equal to 0.

Luego vamos al bucle WHILE y dice: cuando "i" es mayor o igual a cero.

Well, i is now negative 1, so the while loop no longer

Bueno, "i" es ahora negativo (-1) así que el bucle WHILE ya no aplica.

applies. This will return false. i is not greater than or equal to 0, so it won't perform any of this anymore.

Esto resultara ser falso. "i" no es mayor ni igual a cero por lo que ya no realizará nada de esto.

And so we'll now go to the next iteration of the for loop.

Y ahora vamos a la nueva iteracción del bucle FOR

And essentially, what that's signifying is that we were done with that element.

y así nos vamos ahora al... y básicamente lo que esto significa es que ya terminamos con ese elemento.

We compared all the way to everything to the left of it,

Siempre lo comparamos con lo situado a su izquierda y encuentra su lugar

and it found its place, or it just found its place in general.

o simplemente encontramos su lugar en general.

Now let's go to the next iteration of the for loop.

Vamos ahora al... próxima iteracción del bucle FOR.

Now index is going to be the next element.

Ahora "index" va a ser el próximo elemento.

Now index, instead of being 1, is

Ahora "index", en vez de ser 1, va a ser el próximo elemento

going to be the next element in the list generated by this expression here.

en la lista generada por esta expresión aquí.

So index is now going to be 2.

Así que "index" va a ser 2... "index" va a ser 2

And now list value is what's ever at the second index. So it's this item right over here.

y ahora el valor de "list" es lo que sea que este en el segundo indice por lo que es este ítem de aquí.

Notice, we were at the second to the left.

Vean. Estábamos del segundo hacia la izquierda ahora estamos en...

Now we're at the-- or we were at the first to the left, or one right to the left of it. Now we're one space more to the right.

estábamos en el primero de la la izquierda o uno a la derecha del de la izquierda de... ahora o una mas a la derecha.

So value now is going to be 3.

por lo que ahora "value" va a ser 3. Ahora "value" va a ser 3

i is going to be index minus 1.

"i" va a ser "index" menos 1.

Index is 2. 2 minus 1 is 1.

"index" es 2. Dos menos 1 es...2 menos 1 es 1. Por lo que esto es ...

So this is now 1. And we say, while i is greater than or equal to 0.

Esto ahora es 1. Esto es ahora 1 y decimos: Mientras que "i" sea mayor o igual a cero.

Well, it's clearly greater than or equal to 0 now.

Ok. Es obviamente mayor que o igual a cero... ahora es mayor o igual a cero.

So if value is less than list, the i-th element

Si decimos que "value" es menor que "list", the "i'n" elemento de "list"

in list, so the value is 3. And is that less than-- well, what's at list i

Asi que "value" es 3 y es eso menor que... Ok, lo que está en "list" ya no vale 2.

is no longer 2-- so what's in the first element? Well, actually, it is still a 2.

Así que, ¿Cual es el primer elemento? Bien, en realidad todavía es 2. Así que todavía es 2

So if we look at the first element-- list the i-th element in list, i is 1, 0, 1. It is still 2, so I actually didn't have to cross that out.

Así que si miramos al primer elemento, el "list"... el primer... el "i´n" elemento de "list". El valor de "i" es 1. Cero, uno. Aun es 2. Así que en verdad no teníamos que tachar eso.

It is still going to be 2 right over there.

Aun va ser igual a... Aun vale 2 justo aquí.

And so if 3 is less than 2, do this. Well, 3 isn't less than 2, so you're going to do the else clause.

Por lo que... si 3 es menor que 2, que haga esto. Bien, 3 no es menor que 2 por lo que va a realizar el apartado "else"

And you're just going to break out of this while loop.

y tu vas simplemente a salirte del bucle WHILE

And that made sense, because you said, look,

y es lógico ya que dices, epa, mira.

we compared 3 immediately to the thing right before it, to the left of it.

Comparamos el 3 con lo que está inmediatamente antes que el, a la izquierda de el, decimos, epa

And we said, hey, 3 is in the right place. 3 is greater than 2. It's not less than 2, so I'm not going

El 3 está a la derecha. 3 es mayor que 2. No es menor que 2

to do all the shifting business. I don't have to shift 2 to the right and 3 to the left

Por lo que no voy a realizar todos estos cambios. no voy a mover el 2 a la derecha y el 3 a la izquierda

and then look at the next item.

y luego ver el el próximo ítem.

I know that everything to the left of 3 is already sorted. So if 3 is not less than 2, it's definitely not

Yo sé que todo lo que esta a la izquierda de 3 ya está ordenado así que 3 no es menor que 2.

going to be less than anything to the left of it.

Definitivamente no va ser menor que nada que este a la izquierda de el, por lo que terminamos.

And so we're done. We leave it the way it is.

Lo dejamos como está.

And so then we break out. And then we go to the next iteration of the for loop.

Y luego salimos y nos vamos a la próxima iteracción del bucle FOR.

So now index is going to be the next item here. It is now going to be equal to 3,

Así que "index" va a ser igual al próximo ítem de aquí. Ahora va a ser igual a 3.

the next item in this list generated by this expression.

El próximo ítem en esta lista generada por esta expresión

So it's now going to be 3. Index is now going to be 3.

Ahora va a ser 3. Ahora "index" va a ser 3.

Value is now going to be 0, 1, 2, 3.

Ahora "value" va a ser... va a ser 0, 1, 2,

Value is now going to be this item right over here.

Ahora "value" va a ser este ítem de aquí.

That is going to be value, because our index is now 3. So our value is now 2.

Este va a ser el valor de "value", porque nuestro "index" es ahora 3 nuestro "value" es ahora 2.

Let me cross these guys out.

Amigos, voy a tachar esto.

Let me save some space.

Déjenme ahorrar algo de espacio.

Value is now 2. And now i is 2. i is index minus 1, so 3 minus 1.

Ahora "value" es 2 y ahora... y ahora "i" es 2.. "i" es... un momento..."i" es "index" menos 1.

Por lo que 3 menos 1 , eso es 2.

So i is now going to be 2.

Entonces "i" ahora va ser 2

And the object that is at the second element of the list, 0, 1, 2 is now going to be 3.

y el objeto que está en el segundo lugar de "list" 0, 1, 2 ahora va a ser... ahora va a ser 3.

And so the first thing we do while i is greater than or equal to 0-- well, i is clearly greater than or equal to 0.

Y entonces lo primero que hacemos mientras "i" es mayor o igual a cero. Obviamente "i" es mayor o igual a cero.

It's 2 right now.

Vale 2 en estos momentos.

If value-- if 2 is less than what's in the i-th slot of list, so 2 is less than 3, so we do perform this right over here.

Si "value". Si 2 es menor que lo que está en el "i´n"... el "i´n"... que es lo que está en el "i´n" posición de "list" Como 2 es menor que 3, entonces realizamos esto de aquí.

And so what we do is, whatever is at list of i plus 1.

luego lo que hacemos es que lo que este en el ("i" + 1) del "list" entonces ("i" + 1) del "list."

I is 2. i plus 1 is 3. So whatever is at this slot, which is the third slot where the 2 was, replace it with whatever

"i" vale 2. "i" mas 1 es 3. Así que todo lo que esté en esa posición, el cual es la tercera posición de donde el segundo estaba.

is to the left of it.

Reemplazarlo con lo que esté a la izquierda de el.

So replace it with the 3.

Por lo que lo reemplazamos con el 3.

So we're going to replace this with the 3.

Entonces vamos a reemplazar esto con el 3 y el próximo elemento...

And in the next element, take whatever was that slot to the left where i is, and replace it

toma lo que esté... esa posición a la izquierda de donde está "i" y lo reemplazamos... y lo reemplazamos con... ."y lo reemplazamos con "value"

with value. So then we replaced it with value. So this thing is now going to be a 2 again.

Y lo reemplazamos con "value", asíi que lo reemplazamos con "value" así que esto va a ser igual a 2 nuevamente y así... y entonces nosotros... y ahora disminuimos "i" nuevamente.

And now we decrement i again.

So now i is equal to 1. And we go through the while loop again.

Ahora "i" es igual a 1 y nos vamos nuevamente al bucle WHILE.

I is clearly greater than or equal to 0.

Es obvio que "i" es mayor o igual a cero. Es 1.

It is 1. Value is still 2. Remember 2, is what we're comparing

Aun "value" vale 2. Recuerden que 2 es lo que estamos comparando.

while we go through this while loop, but we're comparing to each of the items to the left.

y mientras pasamos por el bucle WHILE estamos comparando con cada uno de los ítems de la izquierda.

If 2 is less than whatever is at the i-th slot in the list.

Si 2 es menor que lo que esté en el "i´n" posición de "list".

So the first slot in the list is a 2.

La primera posición de "list" es 2.

Well, 2 is equal to that, but it's not less than that, so we don't have to do anything more.

Bien, 2 es igual a esto, pero no es menor que esto, así que no hay nada más que hacer.

The thing is sorted. 2 is in the right place.

la cuestión esta ordenada. Los 2 están en el lugar correcto.

If it's equal to the thing to the left of it, we don't have to shift anything.

Si es igual a lo que está a la izquierda de él, no tenemos que cambiar nada

And that means it's at least equal or greater than everything to the left of that,

y eso es lo que quiere decir con "por lo menos igual o mayor" que todo lo que esté a la izquierda de aquello

since everything is sorted already.

debido a que todo está ordenado. Ya todo está ordenado.

So then we're done.

así que terminamos.

Since 2 is not less than 2, we break out. And we break out in the for loop.

Si... Debido a que 2 no es menos que 2, nos salimos y nos adentramos en el bucle FOR que dice...

It says, OK, let me see if there's anything left in this list to apply index to.

Okay dejame ver si falta algo de este "list" a ser aplicado al "index"

There isn't. We've used everything in that list. And so we break out of the for loop.

No hay más. Hemos usado todo del "list" y entonces nos salimos del bucle FOR

And we're done. And the list should be sorted.

y terminamos y la lista debería estar ordenada.

And we see right here, the list is sorted.

vemos aquí, la lista está ordenada.

Our final sorted list is 1, 2, 2, and 3.

nuestro lista final ordenada es: 1, 2, 2, 3.

Similar videos:

Insertion Sort in Python
Khan Academy
104.7K views 451 likes 20 dislikes 01 Jul 201137% match

Stepping Through Iterative Fibonacci Function
Khan Academy
35.7K views 110 likes 3 dislikes 30 Jun 201130% match

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

Desigualdades compuestas
KhanAcademyEspañol
16.2K views 56 likes 4 dislikes 01 Sep 201325% match

Python Lists
Khan Academy
353.3K views 1.3K likes 29 dislikes 30 Jun 201125% match

Settings Privacy About Contact Donate