Algorithms Lesson 2: Insertion Sort

[Listn2CKY]

I like the music :). Very relaxing and helps learning.

[DivjotBogas]

The animation helps so much!! It clears the idea so well , i bet in my exam i would be seeing a brown background with white spots dancing :P

[rtcvb32]

Perhaps it may modify the actual algorithm's second half (but not how it works), I would recommend a brief explanation of the binary search and how that works. Then using the already sorted elements to find where to insert the number in question. Although in it's simplicity, there's nothing wrong with the explanation.

[LibelCase]

it helps me a lot! thanks man!

[TheRAVIKELAKAM]

good !



[316lga]

this concl-

[rampage241]

blew my mind!

[rhlkiller420]

awesome!!



[bhanwar04]

Thanks a lot!!

[ShivMan007]

I wanna make love to this. great music!

[thaibui01]

I like the examples and it clearly illustrates the concept.

[Bunfire123]

Im starting Computing soon..this was useful and was straightforward.

[musikajhen14]

can you post the exact code ?



[Cory123125]

music i putting me to sleep

[DigiTan000]

Great supplement to the C++ tutorials!

[axeld93]

SO CLEAR NOW. Wish I'd seen this before I started my assignment haha.

[ArunPotti]

good example.



[janidhyan]

thank u?

[Alexplus20]

heres hoping it will help me with my test next week ha.

[sk8rboi7566]

so is this teaching you how to use faster algorithms that will help your scripts run faster?

[malakov5]

@sk8rboi7566 This is a slow sort. Think of all the comparisons you have to do to get each element sorted. Sure its fast for an array of small size, but imagine an array with 9001 elements. once you get up there the number of swaps you have to do to sort. Yes, to answer your question; it is teaching you sorting methods, but wikipedia it. This is a slow one. This can be made to be fast with a hash table or memorization though.

[sk8rboi7566]

is this teaching you faster ways to use algorithms so your programs will fun faster with programming script?

[gnarula]

for all those confused abt the loop being till n-1 rather than till n, here's the explanation..

In the prototype, it mentions for i = 1 to n-1 now n should be interpreted as size of the array and n-1 the last index.. So the loop becomes for(int i = 1; i <= n-1; i++) Thus the loop will continue till the last index of the array

[2667931]

wrong algorithm see for i=1 to n not n-1 check this according to ur algo if i sort 24 13 9 2 then first is 13 24 9 2 for j=1 and for j=2 it will 13 9 24 2, + 9 13 24 2, now what about j=3 my elements in array are 4 and i can loop upto 3 times so algo fails so right programe is from i=1 to n then its gonna work and ignore my poor english

[Jackpotur]

@2667931 the implementation is actually correct check your logic you are doing it wrong

[highvltg1122]

You forgot to give the time complexity...

[bigphatkdawg]

you actually don't have to do all these swaps at all

[cckate321]

that's good ,thank you

[ictTrendsVideo]

Its a great video and clearly explains the idea in discussion. A big thumb up for XoaX.net

Hey! I jumped ot xoax.com at first without noticing that .net. I liked the website, it has great potentials but you need to add some more content yet.

[321noone]

Just to explain a bit further:

i is the INDEX, and J is the actual value of that index.

for i=1 to n-1 not i=0, since i=0 is considered sorted. n-1 refers to array length

j=i focus on the value for that index, is that correct??

while j>0 and A[j]<A[j-1] while number at position 3(for example) is less than number at position 2, not sure why j is more than 0?

swap

and then j is now reduced? j=j-1, so if we were at j=1, j is now 0, algorithm jumps back up to i, i is now 2.

[gognaIT]

well done



[kairen5443]

please make any of your new or old video last for 5minutes or update which video are necessary to be updated

[sim0332]

awsum. . .

[ondrasubs]

nicely done

[harashin0000]

thanks a lot!

[jpabloariasa]

thanks dude ^^

[dfom78]

really good explanation

[nados1977]

Realy it is great effort thanks very much

[Lovel123]

awsome sweet n simple !!!

[tetsuo8484]

Great, I understood the algorithm perfectly with your video. By the way, the music helps. Thanks!

[exotic1406]

I think, a more efficient variant is that we swap only once (when we reach the place of insertion) but while searching for it, we just shift the elements to the right (swap is more expensive the shift).

[WannaBeiDev]

i like bubble sort cuz i like the word buubbble

[milohoff88]

@WannaBeiDev yeah but your computer may not like it :)

[pigpigpigwwf]

this really saved my day!

[kertaspaper94]

Hmm, I think I prefer this over bubblesort.

[eksman187]

best video for Insertion Sort !

[mohitsingh009]

thanks\m/

[LiquidXTC]

what does the j=j-1 do?

The algorithm already swaps them so whats the point in the j=j-1?

Need some help here =/

[AComputerScientist]

The "j=j-1" is so the loop doesn't go on infinitely. If the condition is met, then you swap elements j and j-1, then go on with the next lower index, which is j-1 (so in the next loop iteration, you'll be comparing elements j-1 and j-2, and so on).

[psychofish25]

decrements j

[myjunno]

hi ... it is really helpful but i wanna know why for loop is till n-1 only? and not n?

[Givicencio]

Because the first element is already in the right relative order

[AComputerScientist]

Array indices sometimes range from 0 to n-1 (for size n arrays; not from 1 to n), and this is the convention here. So the loop only goes till n-1. It does not start with i=0 but from i=1, because in the first loop there would be nothing to do (the first element is always in the right relative order with itself)

[TafTaf4Life]

n will work if the array size is larger than the number of items in the array you are sorting. but if the array size is the same number as the number of items, n will cause you to go out of bounds.

[Conan4372]

@myjunno Because you don't compare an element to itself. That is why is it n-1 and not n

[0lsi]

It can't be n, because if it is n and not n-1, then j=i=n which means A[j]=A[n] which is not possible, because A[j] is equal from A[0] to A[n-1]. A[n] is not a value itself. A[n] is n times A, from A[0] to A[n-1]. And all A[0] to A[n-1] are values. I hope I was clear

[fibrosport]

@myjunno

think about it:

the reason it is n-1 rather than n

is that each element is compared to the next one

but if you go to the very last one - n - what will you compare it to? there is no n+1 to do a comparison

that's why the last element to be processed is n-1, it will be compared to the next and final one - n - n is only processed and swapped if it is out of place

[mila88323]

@fibrosport is it not because it's done on the example of an array and array has n number of slots but the first slot is always numbered 0 so the last slot would be number of slots minus one. if u have 3 slots they are numbered 0 1 2 so last slot is slot number 2. if the for loop would stop at slot n you'd have a runtime error because you'd fall off the edge of the array (move to the slot that doesnt exist)... I think so ?

[bakkecske91]

@myjunno

because in array the first element is in the 0 space array[ ]={1,2,3,4,5,6,7}

array[ 0 ]=1

array [ 5] = 6

so if n=30

array[29]= the last number in that array

:)

[Jackpotur]

@myjunno n = size of array, n - 1 = last index

[Mainelcc]

@myjunno because the index usually starts at cero.

[ya6655]

@myjunno Because you should find a more suitable job for a moron like you..

[jonathananorman]

@myjunno It is because the array is indexed from 0 up to n -1 where n is the number of elements. Treat the first element as index 0 and so on up until the final element which is n-1.

[claudinegladue]

@myjunno the first element is already sorted, so you don't have to sort it, and can skip to the next element, because you skipped the first one, its n-1

[Darkness2288]

@myjunno

I assume that n in this case is the length of the array, and the length of the array is 1 more than the index of the last item in the array. which means the last item in the array would be array[n-1]. If we were to do array[n] then we would get an OutOfBound Error

[youwouldbetterfuckme]

@myjunno Cause array which has n element has indexes between 0 and n-1, so the last element is "n-1".

First loop begins from one, but it's not because an array has only positive indexes (like in Pascal), but because element A[0] is always sorted.

[axeld93]

@myjunno Because in languages like C, arrays are indexed from 0 up, not 1 up. So the last element is indexed n-1, not n. If you used n, you would be accessing elements not in the array.

[fahadkhan2]

@axeld93 : Then why does the indexing in the pseudocode mention starts from 1 not 0?

[axeld93]

@fahadkhan2 Pseudocode is intended to be read by humans, and is not in any particular programming language. Hence the pseudocode is indexed from 1 up, since that is how humans count.

[Freedom1987ify]

@myjunno Because the index of array is from 0 to n-1, so there are n elements in the array. Remember the last index is n-1, not n, or the system will occur IndexoOutOfArray exception.

[goodmorning20986]

@myjunno Because in an array, the counting starts from zero.

[Astrosisphere]

Thank you! Much better than that idiot with the deck of cards!

[neolegionar]

lol

[elobato]

@Astrosisphere Haha no offence to that guy (he explains heap&quick sort pretty well) but true!

[Edange]

@Astrosisphere haha i watched that one too xD. You deserve a thumb up!

[Astrosisphere]

@Edange haha, it seems like quite a few people agree with my statement!

[28haricharan]

@Astrosisphere

[28haricharan]

@Astrosisphere

:P

[SteveThePCGamer]

@Astrosisphere lol that's a bit harsh. 

[fuzwire]

@Astrosisphere it may be better but that so called idiot is also trying there to teach you and you should appreciate his efforts as well

[Astrosisphere]

@fuzwire I know, I know; that was written right before an assignment deadline!

[MasterAchilles]

Great explanation.

[sikkin]

I like the way you explain it, it is helpful.

thank you