Bubble Sort Algorithm Tutorial in Java - How Fast Is It?
Vložit
- čas přidán 1. 04. 2021
- Complete Java course: codingwithjohn.thinkific.com/...
Full source code available HERE: codingwithjohn.com/bubble-source
Coding the Bubble Sort algorithm in Java!
This is a very beginner friendly beginner's Java coding lesson tutorial, where we'll write our own implementation of the Bubble Sort sorting algorithm.
Bubble Sort isn't the fastest sorting algorithm, but it's a great algorithm for beginners to learn.
Learn or improve your Java by watching it being coded live!
Hey, I'm John! I'm a Lead Java Software Engineer who has been in the industry for more than a decade. I love sharing what I've learned over the years in a way that's understandable for all levels of Java developers.
Let me know what else you'd like to see!
Links to any stuff in this description are affiliate links, so if you buy a product through those links I may earn a small commission.
📕 THE best book to learn Java, Effective Java by Joshua Bloch
amzn.to/36AfdUu
📕 One of my favorite programming books, Clean Code by Robert Martin
amzn.to/3GTPVhf
🎧 Or get the audio version of Clean Code for FREE here with an Audible free trial
www.audibletrial.com/johnclean...
🖥️Standing desk brand I use for recording (get a code for $30 off through this link!)
bit.ly/3QPNGko
📹Phone I use for recording:
amzn.to/3HepYJu
🎙️Microphone I use (classy, I know):
amzn.to/3AYGdbz
Donate with PayPal (Thank you so much!)
www.paypal.com/donate/?hosted...
☕Complete Java course:
codingwithjohn.thinkific.com/...
codingwithjohn.com - Věda a technologie
I’ve been writing blogs to explain to my friends some programming topics myself so I totally understand the amount of work one have to put in to explain a topic so well and still keep it concise. Keep up the great job mate!
Thanks, I appreciate the kind words! It certainly does take a while. By the time I'm done planning, writing, recording, editing, and uploading, it's sometimes surprising how long it takes to make a decent 10-minute video. But that's the idea, spend the time on my end to deliver a clear message so viewers don't have to!
I love your video style! bite size videos that really tackle the nitty gritty of the topic, not just being vague / bridging gaps with your own knowledge. You make learning these topics a lot easer! thank u!
I hadn't seen this approach to the Bubble Sort. We did it as a loop inside of another loop.
This one seems cleaner.
Almost perfect. This is one of the many sorting algorithms that is mandatory in German higher education computer science classes. We also evaluate the complexity by measuring the time and we talk about the mathematical representation of the complexity.
I said almost perfect because we try to optimize the algorithm, e.g. by reducing the length of the array that must be checked after each cycle. As you explained, the last and last but one element don't have to be checked. The question also arises whether using two for loops and a boolean is faster.
Here's a little improvement to the Bubble Sort implementation:
For every loop, there will be one highest element put to the rightmost of the array. So instead of hardcoding the numbers.length, put it in some variable before for-loop (ex: index = numbers.length). At the end of the for-loop block, decrease the index by one (index--). Because, you don't need in anyway checking the rightmost elements that have been checked in the previous loop. Those elements are already sorted.
Here's the implementation:
public static String bubbleSort(int[] numbers) {
boolean swappedSomething = true;
while(swappedSomething ) {
swappedSomething = false;
int index = numbers.length-1;
for (int i = 0; i < index; i++) {
if(numbers[i] > numbers[i+1]) {
swappedSomething = true;
int temp= numbers[i];
numbers[i] = numbers[i+1];
numbers[i+1] = temp;
index--;
}
}
}
the line "int index = numbers.length-1;" need to be placed outside of the While block. If you placed it like this, everytime the first loop starts, it will set default index to a fixed length in which the second loop will always check the whole array.
the idea of this video is not how to improve bubble sort. i have tons ideas, but it doesn't matter, and it is not needed.
This *improvement is worse in therms of speed because with every swapp , the index will be lesser and lesser . Suppose your minimum number is the last one , so your method will ignore that number untill all numbers before are sorted (checked with debuger). So , the method will do even more iterations to replace that number because it every time will set index for n-1. To improve your ideea, i set index before While and index-- after looping , so when the iterations stops, the index will be the maximum number compare to the left side so it will be unnecessary to check the right side of index (this method will sort the maximum number in each iteration). I hardly recommend to use Debuger to check each iteration and each variable at each iteration.
Anyway, thanks for your ideea!
Here is my improvement :
public static String bubbleSort(int[] numbers) {
boolean swappedSomething = true;
int index = numbers.length-1;
while(swappedSomething ) {
swappedSomething = false;
for (int i = 0; i < index; i++) {
if(numbers[i] > numbers[i+1]) {
swappedSomething = true;
int temp= numbers[i];
numbers[i] = numbers[i+1];
numbers[i+1] = temp;
}
}
index--;
}
}
@@kafkahesse2606 what are you man he is just trying to help if you don't want it just ignore it
I can't belive you don't have more subs, ur videos are great
Thanks, of course I'm doing what I can to keep it growing! The liking/commenting/subscribing are very all much appreciated. Feel free to share with anyone you think may be interested as well. I try not to spam my own stuff everywhere 🙂
This guy knows his stuff.
Love watching your videos to learn Java. Keep it up John. Best tutorial on CZcams. And hey can you tell us how to develop logic i mean after i see a video then only i understand the logic and i can code before that i don't have an idea.
Thank you for sharing with us this tutorial. Really helpful.
Thank you John! Your work is much appreciated, you're an excellent teacher. Hats off!
Very nice. One of the best java teacher on the CZcams. Nice explanation. Thanks ❤
going to pass my Algos class because of this channel! Love your channel my friend.
Clearly amazing, wow, while loop was clearly making sense! Thank you for explaining this sorting algorithm
You could also just use another int to declare the last switched index, so you can just leave the rest, sorted array untouched, this should safe you a lot of time with big arrays, because it just gets at least one iteration smaller each round.
Ooh i was doing it the wrong way, but happily i can do it nicely thanks to you John, the way you did it, is pretty clean and understandable. I was doing it with the explicit 2 loops, the old way haha, still cannot improve the performance but at least the code is easy to understand
Very carefully explained. Thank you very much for the video
Very clear explanation i even enjoyed learning by watching it..
You jst got urself a new sub, thanks a lot for nice content.
Man definitely something I have been looking for
That's the best implementation of bubble sort I have ever seen
this is the best solution to understand, thank you very much!
we need to address the elephant in the room -> Kramer painting :) Your channel is pure gold, keep up the good work!
This visual representation is the best thing ever
Very instructive video thx a lot!!!
very vivid, thank you ,John
Fantastic! Fantastic!! Fantastic video John!!!
omg, you explained this very good. I subscribed to you now
a beautiful piece of code ! 😍
Great explanation, great video!
Honestly this made more sense than when my professor briefly explained how it worked then left it at that.
Thanks, you’re great!
Pretty cool,
I like it!
👍
Great explanation...
Just something to think about. Since every time you go through the for statement, the last number is in the correct place, you only have to go through it to "length -1" once and the next time is "length - 2" and you'd be doing one less comparison and loop each time, so wouldn't the complexity be less?
If you still have the source code, would you make the change and let me know if it makes a difference? Obviously with the way you have it set up, you'd have to generate a "permanent" array and copy it to sort it both ways.
Just a thought - and it's easy for me to hand out assignments to someone who's just trying to advance knowledge on the internet.
Thanks for the tutorial.
Bro we need a lesson on selection sort,
And another on comparision between selection and insertion sort,
And lastly overall comparison between all other sorting algorithm (insertion, selection, bubble, quick, merge, heap) in terms of time, space complexity and when to use
I've question about this algorithm. When we do first loop the max element will be at the end of array. Can we decrement loop by 1 on every while loop. Shortly, I want to say that we can neglect the last element and in every while loop we can write loop like :
int length = list.length;
while (sorted!= true)
for(int i = 0;i < length-1;i++){
do something();
length -= 1;
}
please correct me if i've mistaken
can also use while (!swappedSomething) { ...} like that you can set the boolean to false to start
it was interesting, thanks
Do you have playlist for sorting algorithms?
Could you explain why there are no pointers in Java? I’m learning java and c++ and the different types of variables in c++ confused me for a while.
Thank you
Can you do a video about MergeSort?? thank you
I'll see what I can do!
FYI, I'm in the process of making the merge sort video right now! It's much more complicated for a beginner than bogosort or bubble sort, and tougher to explain clearly so it's taking a while, but I hope I do it justice. Should be uploaded in the next day or two.
I would make a community post about this instead of replying to a comment, but apparently CZcams doesn't allow community posts with less than 1,000 subs. Lame.
Here you go! czcams.com/video/bOk35XmHPKs/video.html
@@CodingWithJohn Thank you!!!
Is that Kramer's photo on the bottom right ?
John the man !
thank you.
in inner for loop we can put an `i< numbers.length -1 - iteration_count`.
there is no need to compare already bubbled element in previous iteration, that are already in right place.
```
private static void bubbleSort(int[] numbers) {
boolean swappedSomething = true;
int iter_count = 0;
while (swappedSomething) {
swappedSomething = false;
for (int i = 0; i < numbers.length - 1 - iter_count; i++) {
if (numbers[i] > numbers[i + 1]) {
swappedSomething = true;
int temp = numbers[i];
numbers[i] = numbers[i + 1];
numbers[i + 1] = temp;
}
}
iter_count++;
}
}
```
Good work. There is a subsumed version that can be found in Wikipedia. The comparison count is reduced by 50%. It has no boolean variable. Instead it keeps track of the last item swapped and enforces a new upper limit.
Does anyone know how bubble sort would work for a string data type??
ty
In java it takes time to even print on stdout...program will run faster without print
Bubble soft is usually better than bogo short, but not always.
bogo sort sounds like it has the potential to swap in one interation lol (probably never going to happen)
Bogo sort could theoretically outperform any sorting algorithm in the world
It is also likely to realistically never sort :,(
Or instead of creating another loop to go through the array over and over again, one can simply reset i to - 1 in the if statement. Great video!
Could you please provide some pseudo-code demonstrating this?
@@Tidbit0123 sure. the goal is to get rid of the while loop at 7:36
//Initial array
int[] numbers = {5,3,4,7,2};
//Iterator
for (int i = 0; i < numbers.length - 1; i++) {
//Sorting algorithm
if (numbers[i] > numbers[i + 1]) {
int temp = numbers[i];
numbers[i] = numbers[i + 1];
numbers[i +1] = temp;
//The magic reset
i = -1;
}
}
//Output using Arrays wrapper class
System.out.println(Arrays.toString(numbers));
@@troeteimarsch that is very interesting! I just did a small set of testing and it seems for an array of size 100, the while - for approach runs at 400000~ nanoseconds (0.0004 seconds) while the single loop seems to run in 2000000~ nanoseconds (0.002) seconds.
Any idea why that might be? My algorithm analysis skills are not so hot at the moment hahah still learning
@@Tidbit0123 I can only guess. Even when the array is completely sorted the iterator will still go over it one more time instead of breaking out the while loop. Furthermore I guess it has something to do with branch prediction and other optimizations.
You're into that - that's great! Keep it up, you're asking the right questions.
Do your results change when the iterator variable counts down instead of up?
Like this:
for (int i = numbers.length - 1; i > 0 ; i--) {
//Sorting algorithm
if (numbers[i] < numbers[i - 1]) {
int temp = numbers[i];
numbers[i] = numbers[i - 1];
numbers[i - 1] = temp;
//The magic reset
i = numbers.length - 1;
}
}
@@troeteimarsch So I changed up my testing quite a bit, I created a count variable and added 1 to count on each iteration for every loop.
The while/for and for/for approaches both take in 10-15,000 iterations to complete the operation.
The single loop method is taking 100,000-130,000 depending on the array generated, while I know an array of 100 fixed numbers would give better results it feels pretty clear even with a random list.
So when we reset the value of i each loop, it means we just compare a shorter set of numbers per loop, so it makes sense that the count variable is high, but I don't really understand the massive gap in performance being that it is 4x slower.
Is it because we have to compare the same numbers again as we progress along the array? Because it's possible we have one element stop before making it to its correct position in the array, so basically just multiple interation phases for singular elements. Correct my if I am wrong with my understanding of how this operation works.
I think you should not print the elements of the array if you want to check the running time for the algorithm
most of the time is in writhing the elements to the screen
I noticed that you used length - 1 as the index for the second to last element of the array. But array[length] should be out of bounds. Only 0 to length -1 are valid. I'm guessing that java doesn't throw an out of bounds error since the sort worked regardless. But I think the slightly more efficient method would be length - 2. Also, first pass through forces the highest number to the end, so there's no need to check the last number in the second pass. So, the range could be decremented by 1 with each iteration through the bubblesort. While still O(n^2) the actual time is cut in half.
Oh wait. I just rewatched. The for loop was using the less than symbol, not
No worries! Yeah Java would have thrown an IndexOutOfBoundsException if the actual length was used as the array index.
You're absolutely right - because you know the largest value bubbles to the end each time, you can absolutely decrement the range each iteration like you're saying to cut back on all those extra unnecessary comparisons.
Great example.
I don't know if the following "improvements" help much. On my ancient Dell-M4800 using Amazon Corretto 17 JDK I'm getting a touch under 30 seconds for 100,000 records.
The fewer additions we can do, I assume the better, but at the expense of more memory. Also note we can reduce N by one every time through the loop since after every time, the greatest number is at the bottom, then bottom-1, then bottom-2, etc. Maybe after a few thousand iterations, we're just "spinning our wheels" at the last few thousand iterations as they've already been sorted.
Likewise every array "lookup" I like to do once, assign it to a variable (numsI, and numsIP1 --> versus repeating nums[i] and nums[i + 1]).
Once again I can't say how much time all these "improvements" buy us.
int n = nums.length - 1;
while (swap) {
swap = false;
for (int i = 0; i < n; i++) {
int ip1 = i+1;
int numsI = nums[i];
int numsIP1 = nums[ip1];
if (numsI > numsIP1) {
int hold = numsI;
nums[i] = numsIP1;
nums[ip1] = hold;
swap = true;
}
}
n -= 1;
}
}
Pls tell me a good book for java for beginners
Hi genuine question
when you set the swappedSomething = false;
would that mean it will break through the while loop and never go to the for loop, Im fairly new to programming so im a lil bit confuse abt it
So when we set swappedSomething = false, the while condition has already been evaluated to true in order to run, so it will continue until the end of the while loops code block before evauluating the condition again. If something was swapped in the for loop, the condition of swappedSomething = true again, and the while loop will repeat. If nothing was swapped, the value of swappedSomething will remain as false so the while loop will evaluate the condition as false, and thats when the looping will end.
The behaviour you're referring to would be a break; or return ;statement, which would break the while loop no matter the conition
i love you man
Aaaah the K man painting!
I've been making videos for almost a year, and you're the first one to notice it!
I think bubble sort is efficient in terms of memory since it does require extra memory
what about from highest to lowest? badly need :(
private static void printArray(int[] numbers){
for (int i = 0; i < numbers.length; i++) {
System.out.println(numbers[i]);
}
} How to print the elements of the array in the same line with a semicolon seperator?
Thank you :)
I don't know how it happened, but I sorted a million-element int array with bubble sort in under 200 ms. It seems it's not that slow after all 🤔
If don't undertand something I don't give up, I just find another source of the same information. That's how I found your channel.
From a non native speaker that's sick of indians
Thank you!
Make a video to generate random numbers without using Randam class
Can I ask for thread sort next
I'm actually not familiar with thread sort, do you have a link? All I can find are multi-threaded versions of other sorting algorithms.
@@CodingWithJohn actually it requires other algorithms
may god bless you
🖤
Mujhe pta hi nhi tha johney sins programming bhi janta hoga 😮
At first I didn't want to care abt this BIG O of N² mentions
But now... 😐 I'm thinking it's kind of important
I can do it 🙂Copium
wooow
Your java course is forbidden please check
i believe bubblesort is either bad explained or bad animated, actually compares first element to all, then second element to all from second element, then third element from all from third element and so on... not in pairs.
oh i see gets implemented as the explanation and animation, i stand corrected
is this a late april fools? you know that after each 'bubble' there will be one more ordered element? instead of a while just use 2 for loops, the first one moves the end point back and the second one moves the 'bubble'