Bubble Sort - CS50 Shorts

***

This is CS50, Harvard University's introduction to the intellectual enterprises of computer science and the art of programming.

***

HOW TO SUBSCRIBE

HOW TO TAKE CS50

HOW TO JOIN CS50 COMMUNITIES

HOW TO FOLLOW DAVID J. MALAN

***

CS50 SHOP

***

LICENSE

CC BY-NC-SA 4.0
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International Public License

David J. Malan

[FroZenLQud]

Thank god (or rather Doug) that I found these videos. they don't really show up in the youtube search so had to dig them up. I'm from Finland but these explanations really clear a lot of things up for my uni algorithms course.

[coffeeisthepathtovictory]

// Translating this into code, was a heavy, painful, anxiety inducing, lost in the woods kind of experience.
// More please

[coldwinter]

This really helps to visualize the scope of difference between a number and a number squared. Thank you for this and also reinforcing bubble sorting.

[arielspalter]

Where are all the likes? There's no way there aren't any.... This series is absorbed fantastic.

[chiefmiester]

i first saw this video in high school 6 years ago, I've specially searched for this now in my final year of cs engineering. appreciate your work. i wonder why the original videos were deleted

[stackflowovercuckoosnest]

There was no pseudocode step for checking that the largest number was at the end of the array described at 2:49

[davidkorn]

There is no need for a swap "counter" as nothing really gets counted. Two states like, "true" or "false" values would be sufficient. e.g. swapped = "false"

[VKWiCK]

def bubble_sort(list):
swap = 1
while (swap != 0):
swap = 0
for i in range(len(list) - 1):
if list[i] > list[i+1]:
list[i], list[i+1] = list[i+1], list[i]
swap += 1
return list
print(bubble_sort([13, 27, 25, 65, 45, 78, 32, 31, 42]))

[meepable]

Beautiful explanation. Super easy to read and implement this "version" of the bubble sort.

[ColabGuy]

I'm learning algorithms and data structures and this kind of content is very helpful for reach my goal
Thank you!

[sadekomar]

For anyone wondering, here's my C code for bubble sort. Since the largest number always gets bubbled to the right most position, we shouldn't check it again in subsequent passes. That's why my for loop takes into account the number of passes. This code could be dynamic if we check for the array size in lieu of the number 4.

int elements[5] = {2, 9, 4, 5, 1};
int swap_counter = -1;
int passes = 0;


// Bubble sort
while(swap_counter != 0)
{
swap_counter = 0;
for (int i = 0; i < 4 - passes; i++)
{
if (elements[i] > elements[i+1])
{
int temp = elements[i];
elements[i] = elements[i+1];
elements[i+1] = temp;
swap_counter++;
}
}
passes++;
}

[danielkeehl]

It is N * (N - 1) rather than N^2. You should count condition checks, not elements.
It also requires explaining what exactly is counted. The amount of swaps will be completely different for the described worst scenario.

[louiversal_]

Why do you need to set the swap counter to a non-zero value initially?

[xrolediamond]

Nice one. Simple and straight to the point. This really helped alot. Thanks

[crististaci]

Y'al nerd! Thanks dad Doug. Verry informative, and i apprciate your winks and nods to the problems <3.

[aminekidane]

I didn't got O(n^2) but i rather found O(0.5(n^2 - n )). But I don't know why.

[dg-gaming]

wouldn't the worst case be summation n, not n^2 ?

[angelachan]

how come in the this video he says in the worst case it takes n^2 steps but in the lecture David says it takes (n-1)*(n-1) steps? I understand that in the end the Big O is n^2 because the lesser values are dropped, but I wanted to make sure I know how it was calculated before that, whether it's actually n*n or (n-1)*(n-1)

[plamenyossifov]

What is the idea behind the swap counter? I coded it without a swap counter and it still works.

[jojojawjaw]

Since we're not really using the numeric value of the swap counter, would it work if it was just a boolean value that starts out as false, and gets set to true each time a swap is performed, and then reset to false at the beginnig of the new iteration?