After looking through many tutorials, both videos and articles, i can safely say that this is the best one. This helped me more than the school books, and i was able to really understand what's happening. Just know you saved me i have a test tomorrow hahah Thanks man keep up the great work!
Thank you for sharing the positive feedback Mandeep! 🙂 I'm really glad to hear the videos are helping you out. If you ever have any topic suggestions, please feel free to share them too.
Hi Ravi, j = j -1 in the inside/inner while loop is to make sure we keep shifting the element over to the left in the array until it reaches either the correct position in the array OR it reaches the front of the array. So before the inner loop runes we have that: int key = a[i]; int j = i - 1; So the key, the element we are shifting over is set to a[i], where i is the 'current element' that we're going to sort. And j = i - 1, which means it's the index one to the left of that 'current element'. This loop is trying to find the "right spot" to place that element in the array: while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j = j - 1; } It keeps moving over the values in the array using a[j + 1] = a[j]. If j is the element this loop is currently looking at, which is one to the left of the key initially, what we're doing is moving the value stored at the index one to the right with: a[j + 1] = a[j] (i.e. j +1 is one to the right of a[j], and we move a[j] there). We decrement j with each loop iteration so this loop keeps looking at the next element over to the left. Until *eventually* we stop the loop when either j < 0 (i.e. we have reached the front of the array, and the key value needs to go here) OR a[j]
You're welcome, and that's a good question! :-) We use a temp variable when we swap variables. We normally use a temp variable because it's tricky to swap variables otherwise... we could set "x = y" but then we would lose what 'x' is originally set to because we 'overwrite it' with y's value! In the inner loop of this algorithm we're shifting values in the array down by one until we find the right spot for the key. We overwrite a[j + 1] with a[j] each time, and the first time the loop body runs we overwrite a[i] which is where the key was pulled from... but we have this value stored into the key variable so it's OK if we overwrite it. So 'key' is a bit like 'temp' in the sense that eventually when we find the "right spot" for the key, we'll store this value into that index. Now as the loop runs we'll be overwriting a[j + 1] with a[j] with each iteration, but that's OK, the only value "lost" is during that first loop iteration when we set a[i] (i.e. a[j + 1]) to a[j], and we have that stored/saved in 'key'. It might be helpful to output all the values in the array *inside* the the inner loop (using another loop) along with the values of i,j,j+1, etc to help see what is going on. :-) It's definitely a tricky algorithm to visualize and warp our heads around.
So if you're trying to do something like this: int key = a[i]; int j = i - 1; while (j >= 0 && a[j] > a[i]) { a[j + 1] = a[j]; j = j - 1; } a[j + 1] = a[i]; instead of using key like this: int key = a[i]; int j = i - 1; while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j = j - 1; } a[j + 1] = key; then that won't work because remember 'i' is ultimately an index in the array. And we set j = i - 1. We then have code in the loop: a[j + 1] = a[j] And the code is modifying the element in the index of i! :-) Because j = i - 1. That means if i is let's say 4, j = 3. But then we modify the element at the index j + 1 which is 3 + 1 which is 4, which was the index of i! So we can't use a[i] in the loop, we need to save the value of a[i] as a key, because we're going to potentially *overwrite* a[i] as part of the loop. We then move that key value to a[j + 1] when the loop is over. So even if it is "overwritten" it is not lost, it is just shifted to another index in the array as part of the sorting algorithm. Hopefully this helps! :-)
Hello thank you again for another great explanation, im curious; i tried coming up with a solution before watchign the explanation and here is what i got: int i, j, temp; for(i = 0; i < length - 1; i++){ for(j = i + 1; j > 0; j--){ if(arr[j] > arr[j - 1]){ break; } else if(arr[j] < arr[j - 1]){ temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } } } would this still be considered insertion but with a different algo? or would it be something else? thank you in advance!
That's a good question... you could use a similar technique to sort a 2D array, but you would need to modify the algorithm to sort across rows and columns, so it would involve changing how indexing and the loops work. That said, there are several ways to sort 2D arrays, so it would also depend on 'how' you want to sort the 2D array: www.geeksforgeeks.org/sort-matrix-row-wise-column-wise/?ref=lbp.
After looking through many tutorials, both videos and articles, i can safely say that this is the best one. This helped me more than the school books, and i was able to really understand what's happening. Just know you saved me i have a test tomorrow hahah
Thanks man keep up the great work!
You're very welcome! :-) I'm so glad to hear this video was able to help you after trying other resources, that's great!
you are so underrated man. Thank you so much, I really appreciate your work and time
Thank you so much for the kind words. :-)
your videos are just amazing , i am able to understand the concepts very well , please do not stop making videos like these .
Thank you for sharing the positive feedback Mandeep! 🙂 I'm really glad to hear the videos are helping you out. If you ever have any topic suggestions, please feel free to share them too.
OH MY GOD, thank you so much! I was struggling to understand why people started the int i at 1.
You’re very welcome Marco! I’m glad to hear the video helped you out. :-)
Best channel for learning, straight to the point.
I'm glad you're enjoying the content! :-)
fantastic and clear explaination. thank you!
Thank you very much Jasper, and you’re welcome! :-D
Thanks for you work, it is very helpfull
Yeap
very clear way of explanation. extremely helpful.
Thank you very much for the positive feedback raman, I'm so glad to hear this video was helpful for you! :-)
Best channel ever, no doubt on that.
Aww thank you very much! 🙂
Great explanation...best wishes
Thank you! :-)
Great video, thank you so much! I took so many notes!
That's awesome to hear that Jordan, you're very welcome! 😀
Can any body explain why he wrote j=j-1 inside while
Hi Ravi, j = j -1 in the inside/inner while loop is to make sure we keep shifting the element over to the left in the array until it reaches either the correct position in the array OR it reaches the front of the array. So before the inner loop runes we have that:
int key = a[i];
int j = i - 1;
So the key, the element we are shifting over is set to a[i], where i is the 'current element' that we're going to sort. And j = i - 1, which means it's the index one to the left of that 'current element'. This loop is trying to find the "right spot" to place that element in the array:
while (j >= 0 && a[j] > key)
{
a[j + 1] = a[j];
j = j - 1;
}
It keeps moving over the values in the array using a[j + 1] = a[j]. If j is the element this loop is currently looking at, which is one to the left of the key initially, what we're doing is moving the value stored at the index one to the right with: a[j + 1] = a[j] (i.e. j +1 is one to the right of a[j], and we move a[j] there). We decrement j with each loop iteration so this loop keeps looking at the next element over to the left. Until *eventually* we stop the loop when either j < 0 (i.e. we have reached the front of the array, and the key value needs to go here) OR a[j]
@@PortfolioCourses thank you very much sir, for this explanation ,it helped me a lot 🙏🙏
Clear explanation! Thanks
You're welcome Camila I'm glad you enjoyed it! :-)
Thank you for all efforts :) keep going.
Q: why we don't use temp in while when we replace values.
You're welcome, and that's a good question! :-) We use a temp variable when we swap variables. We normally use a temp variable because it's tricky to swap variables otherwise... we could set "x = y" but then we would lose what 'x' is originally set to because we 'overwrite it' with y's value! In the inner loop of this algorithm we're shifting values in the array down by one until we find the right spot for the key. We overwrite a[j + 1] with a[j] each time, and the first time the loop body runs we overwrite a[i] which is where the key was pulled from... but we have this value stored into the key variable so it's OK if we overwrite it. So 'key' is a bit like 'temp' in the sense that eventually when we find the "right spot" for the key, we'll store this value into that index. Now as the loop runs we'll be overwriting a[j + 1] with a[j] with each iteration, but that's OK, the only value "lost" is during that first loop iteration when we set a[i] (i.e. a[j + 1]) to a[j], and we have that stored/saved in 'key'. It might be helpful to output all the values in the array *inside* the the inner loop (using another loop) along with the values of i,j,j+1, etc to help see what is going on. :-) It's definitely a tricky algorithm to visualize and warp our heads around.
@@PortfolioCourses Thanks again 🤗
Excelente, muito obrigado!
You’re welcome Felipe! :-)
why is it not working when I use a[i] directly instead of using the variable " key " ? can somebody help me please
So if you're trying to do something like this:
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > a[i])
{
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = a[i];
instead of using key like this:
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key)
{
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = key;
then that won't work because remember 'i' is ultimately an index in the array. And we set j = i - 1. We then have code in the loop:
a[j + 1] = a[j]
And the code is modifying the element in the index of i! :-) Because j = i - 1. That means if i is let's say 4, j = 3. But then we modify the element at the index j + 1 which is 3 + 1 which is 4, which was the index of i! So we can't use a[i] in the loop, we need to save the value of a[i] as a key, because we're going to potentially *overwrite* a[i] as part of the loop. We then move that key value to a[j + 1] when the loop is over. So even if it is "overwritten" it is not lost, it is just shifted to another index in the array as part of the sorting algorithm.
Hopefully this helps! :-)
Hello thank you again for another great explanation, im curious;
i tried coming up with a solution before watchign the explanation and here is what i got:
int i, j, temp;
for(i = 0; i < length - 1; i++){
for(j = i + 1; j > 0; j--){
if(arr[j] > arr[j - 1]){
break;
} else if(arr[j] < arr[j - 1]){
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
would this still be considered insertion but with a different algo? or would it be something else?
thank you in advance!
Very nice
Thank you very much! :-)
Is it the same concept when you try to sort 2D arrays?
I have grasped the concept of sorting in 1D arrays. Idk with 2D arrays tho.
That's a good question... you could use a similar technique to sort a 2D array, but you would need to modify the algorithm to sort across rows and columns, so it would involve changing how indexing and the loops work. That said, there are several ways to sort 2D arrays, so it would also depend on 'how' you want to sort the 2D array: www.geeksforgeeks.org/sort-matrix-row-wise-column-wise/?ref=lbp.
Can you please make a video on sorting a doubly linked list of integers using insertion sort?
Thank you for the video suggestion. :-) That topic might be too big for a video as I would also need to cover doubly linked lists, but maybe one day.
@@PortfolioCourses No worries.
Thank you for your quick response
You're welcome! :-)
great!
Thanks! 😀
Why we write a[j+1]=key?