Bubble Sort - CS50 Shorts
Рет қаралды 117,291
6 жыл бұрын***
This is CS50, Harvard University's introduction to the intellectual enterprises of computer science and the art of programming.
***
HOW TO SUBSCRIBE
kzfaq.info_c...
HOW TO TAKE CS50
edX: cs50.edx.org/
Harvard Extension School: cs50.harvard.edu/extension
Harvard Summer School: cs50.harvard.edu/summer
OpenCourseWare: cs50.harvard.edu/x
HOW TO JOIN CS50 COMMUNITIES
Discord: / discord
Ed: cs50.harvard.edu/x/ed
Facebook Group: / cs50
Faceboook Page: / cs50
GitHub: github.com/cs50
Gitter: gitter.im/cs50/x
Instagram: / cs50
LinkedIn Group: / 7437240
LinkedIn Page: / cs50
Reddit: / cs50
Quora: www.quora.com/topic/CS50
Slack: cs50.edx.org/slack
Snapchat: / cs50
Twitter: / cs50
KZfaq: / cs50
HOW TO FOLLOW DAVID J. MALAN
Facebook: / dmalan
GitHub: github.com/dmalan
Instagram: / davidjmalan
LinkedIn: / malan
Quora: www.quora.com/profile/David-J...
Twitter: / davidjmalan
***
CS50 SHOP
cs50.harvardshop.com/
***
LICENSE
CC BY-NC-SA 4.0
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International Public License
creativecommons.org/licenses/...
David J. Malan
cs.harvard.edu/malan
malan@harvard.edu
@FroZenL1Qu1d 5 жыл бұрын
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.
@coffeeisthepathtovictory1290 3 жыл бұрын
// Translating this into code, was a heavy, painful, anxiety inducing, lost in the woods kind of experience. // More please
@khaled-dev 3 жыл бұрын
int main(void) { //let's make an array of numbers that we want to sort int size = 6; int arr1[6] = {3, 5, 1, 2, 10, 8}; //let's sort this array while(1) { int swapped = 0; for(int i = 0; i < size-1; i++) { if(arr1[i] > arr1[i+1]) { int temp = arr1[i]; arr1[i] = arr1[i+1]; arr1[i+1] = temp; swapped = 1; } } if(swapped == 0) { break; } } // print the sorted array printf(" Sorted Array "); for(int i = 0; i < size;i++) { printf("%d ", arr1[i]); } return 0; }
@lorenzobandinelli2638 3 жыл бұрын
@@khaled-dev thank you so much!
@cowcanfly6859 3 жыл бұрын
@@khaled-dev hey the (size-1) is present so that we swap the 2nd last and last integers right ? also anyway to write the code such that it ignores the already sorted pairs?
@coldwinter1884 3 жыл бұрын
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.
@chiefmiester3801 3 жыл бұрын
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
@Marta-dh6nr 4 жыл бұрын
Thank you for your explanations!
@davidkorn5253 Жыл бұрын
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"
@meepable 6 жыл бұрын
Beautiful explanation. Super easy to read and implement this "version" of the bubble sort.
@troyke 4 жыл бұрын
Thank you Doug!
@AdrianzDev 9 ай бұрын
I'm learning algorithms and data structures and this kind of content is very helpful for reach my goal Thank you!
@stackflowovercuckoosnest633 3 жыл бұрын
There was no pseudocode step for checking that the largest number was at the end of the array described at 2:49
@sebawesyaj2740 5 жыл бұрын
Thank you Doug
@arielspalter7425 3 жыл бұрын
Where are all the likes? There's no way there aren't any.... This series is absorbed fantastic.
@art_vibes_1972 3 жыл бұрын
You're the best, Doug
@xrolediamond2617 6 жыл бұрын
Nice one. Simple and straight to the point. This really helped alot. Thanks
@alialparslan2288 2 жыл бұрын
That was dope!
@VKWiCK 3 жыл бұрын
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]))
@Bob-zg2zf 3 жыл бұрын
Wonderful
@patrickmcauliffe7162 4 жыл бұрын
you rule DOUGIE!!!
@anonymousindia27 6 жыл бұрын
Great job👏👏
@sigmundtetevia5933 4 жыл бұрын
Can you pls do radix sort
@sadekomar 2 жыл бұрын
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++; }
@crististaci9364 3 жыл бұрын
Y'al nerd! Thanks dad Doug. Verry informative, and i apprciate your winks and nods to the problems
@danielkeehl7450 3 жыл бұрын
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.
@biesman5 2 жыл бұрын
N*(N-1) is basically N^2
@ezzenious9923 2 жыл бұрын
Yeah, that's how Big-O notation works, anything that's not exponential pretty much doesn't matter for it's purposes.
@dg-gaming942 Жыл бұрын
wouldn't the worst case be summation n , not n^2 ?
@louiversal_ 4 жыл бұрын
Why do you need to set the swap counter to a non-zero value initially?
@ThePokemonrocks5 4 жыл бұрын
The condition was to repeat swapping until the swap counter is zero. If the counter is zero from the beginning, then the algorithm would not execute. The counter is used to determine if the array is sorted or not, with the logic going if the counter is == 0 despite doing a passthrough, then that must mean the array is sorted. Hope this helps!
@louiversal_ 4 жыл бұрын
ThePokemonrocks5 yes it helped, thank you!!
@Cami555555Sheep 2 жыл бұрын
@@ThePokemonrocks5 I guess you could use a do while loop in C though to run it once and not have to declare the swap counter a non-zero number?
@aminekidane5757 4 жыл бұрын
I didn't got O(n^2) but i rather found O(0.5(n^2 - n )). But I don't know why.
@aayushbajaj876 4 жыл бұрын
When we talk about O() complexity, we only take the highest order so no need to worry about anything else just take the n^2.
@jojojawjaw 3 жыл бұрын
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?
@jojojawjaw 3 жыл бұрын
From what I understood, it's not exactly standing for a counter, it's an indicator of whether a swap did happen or not in this particular iteration
@tellahsage6477 3 жыл бұрын
I did that in tideman and it worked fine. So i guess yes, and it's even better since booleans take a quarter the amount of space ints do in memory
@happyeevee4955 4 жыл бұрын
*bubble*
@eeeveeeve 4 жыл бұрын
bubble
@angelachan342 3 жыл бұрын
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)
@SkyNet604 3 жыл бұрын
He says the worst case takes O(n^2), in details it takes (n-1)(n-1) steps
@danielkeehl7450 3 жыл бұрын
@@SkyNet604 neither of you is right. The worst scenario is N * (N - 1). You mustn't count elements, you should count condition checks instead. One swap involves a pair of adjacent elements, and there are N - 1 of them in an array where N in the amount of elements. Yet the worst case implies looping through an array N times since each time it only sorts the greatest unsorted element and the other are left unsorted. To make sure on your own, it is up to you to write a simple program and set another counter which is not zeroed out each pass through an array. Initialise an array with values sorted backwards and you will see that it is N * (N - 1).
@danielkeehl7450 3 жыл бұрын
@@SkyNet604 It also depends upon what exactly you count. If the amount of swaps is counted, it is a triangular number T(N - 1), where N is the amount of elements. That is, the resulting amount for the worst case scenario is the sum of all the numbers from 1 to N - 1.
@zoltanbiro428 2 жыл бұрын
@@danielkeehl7450 The last loop is unnecessary, as the array is guaranteed to be sorted in (n-1) iterations, therefore the worst-case would be (n-1) * (n - 1). However, with a better implementation the worst-case would be only n * (n - 1) / 2 comparisons (sum of an arithmetic progression with 1 as the first element, and (n-1) as the last element), because each loop we guarantee that the last place is correct, so in each pass we have to make one less comparison.
@plamenyossifov6135 3 жыл бұрын
What is the idea behind the swap counter? I coded it without a swap counter and it still works.
@ezzenious9923 2 жыл бұрын
Really you just need some way to tell if at least 1 swap occurred after every iteration.
@sadekomar 2 жыл бұрын
Without the swap counter, we can't stop after the first pass.
@parkerboling7744 4 жыл бұрын
wat it mean at 5:44?
@AlqantDBlank 4 жыл бұрын
it means the best and worst case scenarios for this type of sort represented in symbols
@rafatulalam8677 3 жыл бұрын
based on what I understood from the pseudocode Python code for Bubble sort: (my take) arr = [6, 5 ,3, 1, 1, 4, 7, 2] def bubble_sort(arr): swap_counter = -1 length = len(arr) while(swap_counter != 0): swap_counter = 0 count = 0 while(count < length - 1): if arr[count] > arr[count+1]: temp = arr[count + 1] arr[count + 1] = arr[count] arr[count] = temp swap_counter += 1 count += 1 length -= 1 return arr print('Before Bubble Sort : ',arr) print('After Bubble Sort : ', bubble_sort(arr))
@Walruz1000 3 жыл бұрын
my_arr = [9, 3, 8, 6, 1, 2, 7, 4, 5] swap_counter = -1 while swap_counter != 0: swap_counter = 0 for i in range(0, len(my_arr) - 1): x = my_arr[i] y = my_arr[i + 1] if my_arr[i + 1] < my_arr[i]: swap_counter += 1 my_arr[i] = y my_arr[i + 1] = x
@rakinrahman890 3 жыл бұрын
ew python