Algorithms: Bubble Sort

37
96



Learn the basics of bubble sort algorithm. This video is a part of HackerRank’s Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell.

Nguồn:https://quydinh.com/

37 COMMENTS

  1. !!!!!!!!!!!!!!!!!!!!!!!!!!!!THIS CODE DOESN'T WORK!!!!!!!!!!!!!!!!!
    array[i] > array[i++]; value of "i" is same both sides, hence this always fails..

  2. I remember this from high school — still a great presentation on the topic.

    Personally, I'm tired of the pretense that employers aren't that concerned with language knowledge but are deeply concerned with algorithms and problem-solving. The more experience I get with looking for real jobs the more I find its the opposite — they don't care if you could ace a college algorithms test, nor do they care if you are skilled at developing your own algorithms and systems. No, they want someone already experience in some specific domain of programming and with expertise on specific libraries / frameworks / technologies; they want "spring and hibernate" or "Django, along with SQL, HTML, CSS, and JavaScript." They may also ask for a bunch of other things that aren't important to them, but toward the top you see something like this that is non-negotiable. Funny thing is, a talent dev who has good problem solving and self-teaching skills could learn what they need, but they don't care. All the videos on YouTube pushing algorithms, data structures, design patterns, "problem-solving," etc., are red herrings luring aspiring professional away from what they really need to learn to get that first job and make real progress toward starting a career. If you've bothered to read all this consider it your reality check for the day.

     Perhaps (?) it's different for tech giants in areas with large tech industries, lots of local talent, and large teams capable of mentoring new employees — but the vast majority of business seeking devs are not like this at all.

  3. When you "swap" an array, isnt it passing by reference, meaning that it only swaps that array on that line and it doesn't remember the "new sorted" array while it continues in the loop…?

  4. This is the first time I have seen someone improve the efficiency of bubble-sort. Anyone who is really really new may not understand on the first go but this video is really well made.

  5. But doesn't the performance of this implementation depend heavily upon how isSorted is defined? Or if it is a built-in function? Considering that it is not and you write it out, then this will be a terrible algo because you check if the array is sorted or not each time you iterate through the loop! Can we do better than this?

  6. Very nicely done. Gayle does an outstanding job here. I would like to see a similar presentation using C programming code. Thank you for providing this.

  7. The algorithm shown does not sort the entire array, since you only go through the array (and potentially switch the elements) the amount of times the array is long. Thus you will only bubble the element once. You need another for loop to make it work. Other then that great video.

  8. Straight after the while (!isSorted) condition, the next line is isSorted = true; so wouldn't the code just jump out there and never go through the following if statement? or will it complete the if statement first and then check whether to restart again?

  9. I really didn't get why everyone is saying bubble sort complexity is O(n^2),
    Actually, if you consider the inner loop is getting shorter each time the outer loop loops,
    You will find the execution complexity is O(n*(n-1)/2)

  10. 😤😑😑😑😑😓😓👹👿👹👹👹😮😮😓👐👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾👳🏾🙅🏿‍♂️

  11. 00:55 it should be O(n) space, because we've got one array of n elements. Or she just thought ok additional space that we need except for the array holding n elements is 0 so its constant => O(1) …

  12. I dont get the thing with the lastUnsorted index: if you get the highest element at the beginning then this element wont be able to make it to the other side of the array, or I am wrong ?

  13. You folks that are critiquing Gales instruction and code obviously do not really know who this she is. You see those books behind her? She wrote at least three of them. I know because I read all three. I also believe she is the founder of Hacker Rank which is used by so many companies during job interviews. The big fat book was written by my professor at MIT which she also obviously understands well. Stop embarrassing yourselves.

  14. I must be thick in the head because I have not yet understood why it was while(!isSorted). Like I would say as long as not sorted, keep doing this but apparently, the code is opposite. 🙁

  15. You know in C# and other languages you can just use 1 line to efficiently sort: Array.Sort(myAwesomeArray);

    Spend the rest of the time on something actually productive. No one will ever need to implement a bubble sort or even quick sort. What do you think?

  16. Hello there.
    Your code implementation is too complicated for my opinion. This is my example:

    int[] initArray = new int[]{5,8,1,6,9,2};
    for(int i = 0; i < initArray.length – 1; i++){
    for(int b = i + 1; b < initArray.length; b++){
    if(initArray[i] > initArray[b]){
    int temp = initArray[b];
    initArray[b] = initArray[i];
    initArray[i] = temp;
    }
    }
    }

    Thanks.

LEAVE A REPLY

Please enter your comment!
Please enter your name here