Comparison of Popular Sorting Algorithms, including Bubble Sort and Quick Sort

Hi and welcome to our algorithms section of the Ruby programming course this is going to be a really exciting set of videos because these are some pretty advanced algorithms that are used as a computer science field for development for things like that and these type of algorithms the ones we’re going to go over are considered some of the best ways of learning how programming actually work. So it’s really important to go through here if you’ve ever taken a computer science courses. This is something that you’ll probably have heard a lot about if not that’s perfectly fine we’ll be able to learn as we go. But I want to first talk about just the importance of it. So let me open up an Iraqi section right here. Session right here and I’m going to create an array.

So we have our array right here. Now if I do a dot sort you can see that it sorts the array from lead at least to greatest. And that works perfectly the sort method works great in Ruby and it actually performs very very well. So you typically would not create or implement your own sorting algorithm. So why would you want to learn it. Why are we spending section in several videos dedicated just to that and it’s because learning how to create a sorting algorithm is considered one of the base elements of programming. So once we get past the point of learning what the syntax is for conditional or how to create loops anything like that learning how to create an algorithm from scratch is one of the things that all good computer scientists and all good developers need to be able to implement. So the very first thing we’re going to do is look at some of the sorting algorithms that we’re going to cover in this section and the computer science division of the University of San Francisco did an incredible job in creating this visualization tool for sorting algorithms. I want to start off here. You have an idea of what we’re going to cover some of the ones we’re going to be covering next few videos is one we’re going to do the bubble sort then we’re going to do the quick sort and then we’re going to do merge sort. Now the bubble sort is one we’d only learn just for learning how to program a very basic sorting mechanism. You’d never use bubble sort in a real production application and I’ll show you why. So you click here and you can see what bubble sort does. It goes down the line from the left all the way to the right and it simply compares each element and says OK if the one on the left is less than the one on the right we stay the same. If it’s greater than than it moves in it just keeps on iterating down and taking that one down essentially. And the reason why it’s named what it’s named is it’s taking the largest elements and it’s bubbling them to the top. And so it will it potentially it could take a if few have 97 it looks like elements in this array. It could take 97 times going through the entire array before it sort it so bubbles or is a horrible performance sorting algorithm and you’d never use it in production. But it is great for learning how to implement certain algorithm types. So this could take forever even just letting it run and watching it here. So I’m going to stop this one and move on to quicksort and show you that this one quicksort is a much more advanced one. It’s a divide and conquer algorithm and it’s what’s called a recursive algorithm. So what it does is it picks a pivot point and then it starts sorting inside of whatever that group is. And you can see right here where it’s picking pivots and then it dynamically starts sorting each of the elements like it just did. There’s a great out these ones and it’s focusing here. Now it’s sorting these elements and it may not make a lot of sense in the beginning why this would why this would be a good algorithm but it’s a very advanced one and the reason why it’s so good is because well the performances are great but it breaks the entire data set down into much are pieces so it takes values compares them and then look at the end. You have a fully sorted set of values that you can put together. And this performs dramatically better than bubble sort. Or a lot of those a lot of those type algorithms quicksort is pretty much the most advanced sorting algorithm that most people like to implement because it performs the best and the other nice thing about the other nice thing about quicksort is you don’t go learn how to make it but you don’t really have to worry about too much because when we just ran this algorithm right here when we called sorte on our array this actually uses quicksort Ruby by default uses a quicksort algorithm. So that is neat that with one line of code you can call it the last ones merge sort merge sort is kind of similar to the way quicksort is in the sense that it’s a divide and conquer algorithm. You can see that it takes certain subsections of the array and it divides them out and then it compares those subsections and then it merges those together. So it essentially spreads items out and compares those smaller subsets and then merges them in with the preexisting values and put them all together. This is one that performs almost as well as Quix or in certain cases it can perform as well. But for the most part quicksort is kind of consider the de facto standard for sorting algorithms. But through this action we’re going to learn how to implement all of them. So this is something also that if you’re taking any kind of coding tests or computer science test or interview questions. Being able to implement a sorting algorithm or at least knowing the basics on how those are implemented is something that will come in very handy because it’s one of the more common questions that you’ll get asked whether you’re interviewing for someone like Facebook or you’re interviewing just for a normal software company. So it’ll be good familiarise yourself with these even though you’re mainly in production simply called the defacto sorting method if you’re using Ruby.