Bubble sort algorithm
Вставка
- Опубліковано 6 вер 2024
- See complete series on sorting algorithms here:
• Sorting Algorithms
This series is in progress, we will be adding lessons into this series every week.
In this lesson, we have described Bubble sort algorithm and analyzed its time complexity.
Series on Time Complexity:
• Time Complexity Analysis
Subscribe to our channel to get updates on new lessons.
You may also like us on Facebook:
/ mycodeschool
Finally, a tutorial explaining not only the logic of the algorithm, but the logic behind it's iteration. Thanks a bunch!
The outer loop must execute from 0 t0 n-1, otherwise last element will not be sorted.
code:
for(int k=0;k
This is what we need in youtube. Great lecture with great timing.Good job.
Dude this 10 mins video is worth my uni's multiple hour lectures. Very helpful! Thanks!
i swear this is way better than some of the professors video in schools
on the gang!
I think I have a short attention span and I can get tired very quickly. And direct teaching in school is just too slow for me as teachers just try to explain every single detail. Most UA-cam videos are just short and have enough information so I understand them almost immediately.
Mine just straight up doesn't teach anything
100% true.❤❤❤
The video is perfect. Thanks for the ultimate collection. One check is that outer loop runs n-1 times and inner loop is an arithmetic progression n*(n-1)/2 instead of n-1. The total being n+ (n*(n-1)/2= O(n^2). Just wanted to point out. Let me know if my consideration is wrong.
This channel is a true Gem For Students. Got an exam tomorrow. Would have been really difficult without You. Thank You so much for this!!!!!
Thanks so much! subscribed! This is so much more helpful than my text book :D
thatswhatsup0493 You are most welcome :)
Thanks Bro! Nice efforts.. and I like the variations you explained how we improve with flag...etc../\
boss i feel like dumb dumb dumb when u talk about big(o).I need more help with it.Any suggestions?
Hi Ravi,
I guess you are talking about 6:03. Outer loop is running from 1 to n-1 (we could have run from 0 till n-2 also) which is n-1 times. If you bubble up n-1 elements, last one - nth one will automatically be in place. So, no need to run n time. Inner loop is running from 0 till n-2. It's again n-1 times. So, it looks correct to me.
O
Line where first for is will be executed n times,not n-1
back when youtube didn't have the reply feature huh
May is confusion with looping where less than symbol. < n- 1 is nothing but up to n-2 inclusive
int[] arr = {0, 2, 1, 2, 0};
int n = arr.length, temp;
for(int k=0; k< n - 1; k++ ) {
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i+1] = temp;
}
System.out.println(Arrays.toString(arr));
}
}
@Ganesh K in ur prgm second loop can be optimised like: for(int i=0;i
Thank you so much for the series of sorting algorithms.
I request you to give explanation on heap sort.
You have to learn tree chapter first if you want to learn heap sort
Search for "udiprod" on UA-cam, they have a great explanation.
I think outer loop shouldn't start with one because if k won't be starting at zero then the inner loop will go only n-k-1 i.e if k = 1 it'll go up to n-2 times if there's a small variable at the end of the array then it won't be able to reach the end to compare as it'll end one before the last one. For example this below code :
// bubble - sort
class BubSort{
void sorting(int A[],int n){
for(int k = 1 ; k < n - 1 ; k + + ) {
boolean flag = false;
for (int i = 0 ; i < n - k - 1 ; i + + ) {
if (A [ i ] > A [ i + 1 ] ) {
int temp = A [ i + 1 ] ;
A [ i + 1 ] = A [ i ] ;
A [ i ] = temp;
flag = true;
}
}
if (flag == false) break;
}
for ( int i = 0 ; i < n ; i + + ) {
System.out.println(A [ i ] ) ;
}
}
public static void main(String...ssg){
int A[] = {42,23,54,76,23,6,34,8,4,2,3,1};
BubSort b1 = new BubSort();
b1.sorting(A,A.length);
}
}
output - 2 3 4 6 8 23 23 34 42 54 76 1
right also flag variable when included and unsorted array is passed the output obtained is not correct
This is simplified enough for a comprehension, Thanks !!!!!!!
your explanation is perfectly clear and the coding is really simple. Thank you so much!
I can not even fathom how much effort would be needed to make something like this, and it is freely available!
I don't know if any of you have noticed, but he is using MS Paint. And I didn't know it could ever be used to make something useful, let alone this.
I always used to undermine myself, considering that I am not a 'programmer'(never really understood these simple concepts, due to shitty teachers), but in the last few weeks, I've learnt so much only because of you and other good content on the internet. And now I proudly say I enjoy programming and I am a programmer!
very helpful thank you so much. this is honestly the most clear cut explanation on youtube
You are the best explainer I have ever seen
When you reach for O(n), i'm shocked because I had never seen this version of bubble sort .. hatsoff to you.
@9:19 i think the inner loop will be executed n-1 times when there is an already sorted array as input
question in 9:05(I feel it should be like this ): if(flag == 1) break ;
not even one swap if flag ==0; then doesn't that mean we need to swap?
This is the best channel for learning algorithm and data structure. I am coming back here after 5 years
Brilliant explanation !! Need teachers and mentors like you , that will change the whole learning process !!
Thanks 😀✌️
You are the best presenter i have ever seen. Very much useful. This kind of tutorials what we expect. Great job bro.
i think u made mistake... A[0,1,2,....n-1]
for i
Actually, if you start from 0 and your size of the array is n. Then n-1 will allow you to go to a[i+1]. You're missing an element if you only go to n-2.
No
Your explanation is by far the best. I wish I could explain to my students in a similar fashion. Keep posting. Good work.
maybe i'll teach my prof tomorrow , thank you bro , it was really clear. :)
Even it is 9 year old . This video was very helpful.
Thanks for sharing you've got a new subscriber :)
In all of the videos the voice and the language is pretty clear and sharp so there's no need for sub-titles.
Great explanation..... Exactly what tiny brains like me required :)
The first loop should be from k= 0 to (n-1) right??
I feel like being back in school reading stuff on the almighty overhead projector
Best explanation on bubble sort. I have checked out lot of videos but, I was still not clear about the concept. Finally, this video helped me. Thank you so much. Excellent work.
Really smart to focus on constructing the inner-loop first. It really makes everything more clear.
Much better than my prof's lecture! Thanks!
nice explamnation
I am taking Master in Computer Science
I will have a course Advance Alogrithms
so I am reviewing some sort algorithms
For people wondering why n-2 and not n-1 -----
Explaination - In an array, "n" typically represents the total number of elements in the array. So, "n-1" would refer to the index of the last element in the array since array indexing usually starts from 0.
For example, let's say we have an array with 5 elements. "n" would be 5, and "n-1" would be 4, representing the index of the last element in the array. So if we have an array called `arr`, `arr[4]` would be the last element.
Your Chanel Is Best For Pograming
Best big o notation explanation I've seen so far and its not even a big o analysis video
Nice presentation. Thanks a lot. Seems like, learned bubble sort newly after completing graduation about 10 years ago.
One thing, at 9:45 will it break the inner loop or outer? Sorry for my ignorance.
The outer loop. That if condition should be placed after the inner loop.
Thank you sir for explanation ❤️
But what made me comment here is
You sound exactly like a krsn katha vachak (i don't remember his name)
Brilliant explanation of BUBBLE SORT so far!
Thank you very much....this code I was trying to mug up ..now you made it's concept really simple and understandable
You explain it sooo much better than my professor, I don't know how my professor became a professor. OMG thank you
this videos are much more better than the paid ones thank you sir you are really doing great work
thankyou so much my code school, it helped me a lot... it is much better than hand books... and through these videos it is easier to understand and remember all the things..
Thank you
Great viddeo.
A minor note that the loops look like this:
for(int k = 1; k < size; k++)
for(int i = 0; i < size - k; i++){
pseudocode and C++ are 2 diff things ;) so his loops are fine, because the title is bubble sort algorithm, not C++ program. No offense :D
Thanks man for the c++ for loop
watch till the end, he mentioned that.
U r ri8 I also noticed in b/w...there is a minor mistake (n-k-1) must bi replaced with (n-k) in the 2nd for loop..!!
@@emi.grigore any programming code is a sort of replica to their pseudo code, so we should not do logical error in writing pseudo code or it can hamper the chance of writing the correct code. No offence to any one.
Hi Animesh Sir,
You are doing tremendous work.You explain very well, so far I have seen many videos in Algos & DS but these vids are the best one, small compact and fully explained !!
All the very best for your mission, to literate the illiterate Engineering students.
If im not wrong sir, I believe you are trying to call an external swap() function in this code, and in that case a default call by value does not work, I think you should pass the values by reference, for the actual array to be sorted within the main() function. Hence it should be swap(&a[I],&a[I+1]).
Thanks, this tutorial is realy good. but i think there is a little mistake in first loop where the value of 'k' will be 0 (zero). plz check this input : 1 3 2 5 4
This would easily qualify for priced courses. Very good presentations.
What an incredible explanation
Great explanation. Crisp, simple and to the point!!
best videos i have ever found for dsa
in our language "Supiriiiii.....!!! "Great tutorial ... I've cleared many things............
best video on bubble sort ,concise and clear
Thanks a lot man i tried a lot pf vidoes to understand it and this is what helped me understand how it really works
Remember this obsession
Selection sort and bubble sort requires same no of comparisons n(n-1)/2
But in worst case bubble requires n(n-1)/2 swap rather Selection required n-1 swap
..... in my one interview question was asked Like which Sorting Algorithm is best If we consider only Swapping in complexity?
Thanks 🙏
you are great you make me feel not just to understand rather to feel.
I want solutions for below given problem, kindly help:
1- Why are we interested in worst case analysis?
2- What do you understand by rate of growth or order of growth? Why it is important in analysis of an algorithm?
3- For following set of functions, indicate whether f = O(g), f = Ω(g), or both.
1) f(n) = n − 10, g(n) = n + 10
2) f(n) = 10n^2, g(n) = 3n^3 + n^2
4- For f(n) = n^2 + 2n^3 − 100nlogn + 10, provide the simplest possible function g(n) such that f(n) = Θ(g(n)).
5- Show that n log n is O(n^2) but that n^2 is not O(nlogn).
6- Prove or disprove the following: √n = O(logn)
7- Use a recursion tree to determine a good asymptotic upper bound on the following recurrences.
1) T(n) = 2T(n − 1) + 1
2) T(n) = 4T(n/2) + cn
8- Consider the recursive binary search algorithm for finding a number in a sorted array.
(a) Give recurrence for the worst-case running times of binary search algorithm.
(b) Use a recursion tree to determine a good asymptotic bound for the recurrence tree.
9- The ternary search algorithm locates an element in a list of increasing integers by successively splitting the list into three sub lists of equal (or as close to equal as possible) size, and restricting the search to the appropriate piece.
(a) Give recurrence for the worst-case running time of the algorithm.
(b) Use a recursion tree to determine a good asymptotic bound for the recurrence tree.
10- Provide recurrence relation and a tight asymptotic bound for the following code.
long power ( long x , long n )
if ( n == 0 )
return 1;
else
return x * power ( x , n−1);
Best channel for computer science student. Thanks for sharing knowledge to us🙏🙏
ddf
hi, just one small mistake: in 6:12 the T(n) = (n-1) * (n-2) * C ； I think that's your meaning there.
Very good explanation and tutorial on time efficiency.
According to views of this playlist seems like merge sort is a hot topic.
Best explanation.... I am looking for such tutorial.... Thanks :) and keep it up...
The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array?
***How the answer comes out to be 4.***
Detailed explanation would be appreciated.
thank you so much for this series
I think 6:14 should be cn^2 - 2cn + 1c. i.e., the last part is not 1, but 1c.
I was thinking so too
for inner loop t(n) should be C*(n)*(n-1) where n-1 is from outer loop and n is from inner loop itself?
Hi ! Shouldn't the bubble sort algo in C look like this:
void bubblesort(int A[], int n)
{
int k, i, flag, temp;
for (k = 1; k < n; ++k)
{
flag = 0;
for (i = 0; i < (n - k); ++i)
{
if (A[i] > A[i + 1])
{
temp = A[i + 1];
A[i + 1] = A[i];
A[i] = temp;
flag = 1;
}
}
if(flag == 0)
break;
}
}
k in the video ran till n - 1, but it should run till nth element if the last element is the lowest.
Thanks for such depth explaination
Best presentation I have ever seen
How to count primitive operations in the coding? Where to add the counter to count the primitive
operations?
There's a clear explanation to your question on my video here! ua-cam.com/video/D4eQtG6U21E/v-deo.html. If you want a detailed explanation, here's another video I made:ua-cam.com/video/8sVVBaF99Ho/v-deo.html
Oneth. Dayumm
Lol Haha I paused the video to see if anyone else noticed Haha
It's actually the correct term. Harvard teaches it.
@@madebyibrahim This isn't the proper context oneth is used though. Oneth on its own isn't a word, it's a suffix.
*A ray*
@@planesairbornebymalikclark2806 lmao me toooo
if a already sorted array is given, then time complexity will be O(1) ryt, why O(n)
Subscribed after looking only one video.
Awesome explanations.
Why two loops? The upper one
awesome tutorial sir, thank you 👍👍
This is very useful video and easy to understand
Nice explanation but one request it would be better if you give some more knowledge about the algorithm for example which one is best in this case, which is best of all, less time taken increasing order algo etc please tell about all this things as well thank you
This is an amazing video. Bravo.
The way u explain the algo is awsm!
Indexes counter in the for loop should all start from 0 and both should use n - 1.
yes...u are right
Thank you for the efficient lecture.
Nice explanation!ur voice is osm😅
BEST EXPLAINATION !
Thank you for your nice explanation
Great implementation of the flag. It makes a major difference.
Hi Rakesh,
You can choose to start with whatever. In the end, your code should not be buggy. The pseudo-code in this lesson is good. You can try it out in a real program.
very simple and abstracted, thank you
What if the number in the first position is higher than the second position?
Why have you taken n-2 as last step?
how multiple passes are happening when for loop is made only for 1?!
Hello ,
Thank you soo much for creating this video!!
It makes sorting algorithms seem soo easy and very understanding .i subscribed !!!
Thank you !!!
Feeling lucky to have found your channel!!!! Subscribed :D
Sir, in best case analysis, the inner for loop runs (n-1 ) time and outer pass loop runs only 1 time. But you said inner loop runs once?
Big O(n-1 + n-1) => big O(2n-2) => big O(2n) => big O(n) for best case
I have a doubt at 6:55
(n-1) *(n-1)*c=cn2+2cn+1 or cn2+2cn+c
Excellent explanation ♥️♥️
Thanks for the simple explanation.
Excellent explanation!
very clear, thank you