There are many algorithms that deal with sorting collections of data. One of the most basic forms of sorting is known as Bubble Sort and is named by it's nature of the order of data having a "bubbling" effect as a collection of data is sorted. We will start off by implementing a Bubble Sort algorithm on a one-dimensional Array.
The bubbleModule built here uses a simple strategy of going thru the array and, starting at the beginning, it compares the first 2 elements to see which is smaller. If the one to the right is smaller, it swaps their positions. Then the 2nd position, whether changed or not, becomes the first of the next two to be compared. It is compared to the next element in the array and the greater one is placed to the right, the lesser one to the left. When it reaches the end of the array, it repeats the process. When no moves are made in a pass thru the array, the sorter stops and returns the completed, sorted array.
For this type of sort algorithm, the worst case scenario is where the array runs from largest to smallest, with the largest to the right and smallest to the left. In Big O notation, a computer science methodology to analyze the perfomance of an algorithm, bubble sort methods are ranked as O(N^2). This means that for the number of elements in the array (N), the time and memory consumption is squared. So if our bubbleModule was given an array of 4 items and it was the worst case scenario (as mentioned above), the function would need to pass thru the array 4 times (the 4th sees no swaps and this indicates it is sorted and to stop the function). So, here we see the function will "look" at the array 16 times, even if it doesn't swap any positions. Even when it reaches the last number in the array it must look at that number and see if there is another element after it to compare it to. When it sees there is none. It either begins again, if swaps were made, or it stops (if no swaps were made). So that last look at the array is counted too in the time/performance. In a best case scenario, where no moves are made, the performance is directly proportional to the number of elements in the array. So 4 items (in order) would result in 4 "looks" with no swaps. This is performance is called O(N) in Big O notation.
###Bubble Sort Implementation The trick to remembering bubble sort is to visualize that your array is vertical rather than horizontal. If smaller values are "deeper" in the array, they will "rise" to the top until they are the smallest value. If larger values are "higher" in the array, they will sink to the bottom until they are the largest value.
###Your challenge
- Create a project and a repo for your Bubble Sort implementation. You probably want a README as well.
- Add Mocha/Chai to your project for writing your tests against your function.
- Write your tests FIRST that will indicate that your sorting function works with multiple inputs.
- Implement a function that will take an input Array and apply the bubble sort algorithm to sort the input and return the number of moves that were necessary to sort the Array.
###Extra Create a way for all Arrays to be able to use your bubble sort function as a method of the Array object.
###Super Extra Write a browser tool that will visually show the array and it's values as they are being sorted to see how the elements are moving in real time. It will be impossible to see things being sorted in real time, so you may need to tweak your function to make this work or find new ways of calling it.
#quick-sort This algorithm is one of the most efficient algorithms. You can think of it as a "Divide and Conquer" strategy. It selects a value from the array and names it the 'pivot'. It then splits the array into two smaller parts by comparing each number in the array with the pivot. The numbers less than the pivot are put into a left side array and the ones greater are put in a right side array. These halves are then passed back thru the function in a 'recursive' way which just means it will continue to do this forever unless a base case situation is met. So each half is split using a new pivot and those halves are split by designating a pivot for each and so on and so on. The base case is when there is no longer any left or right halves to split. It then reassembles these sorted pieces by 'glueing' the individual left values with the individual pivot values and that to all the individual right elements.
For this type of algorithm, in the best case scenario, it performs O(log N) according to the Big O notation. This is also called Logarithmic time. Basically, this means at first this function is very consumptive of time and memory compared to the number of elements introduced. This is because of the initial splits of the bulk data and comparison to the pivot. However, as the 'halves' become smaller and smaller, the time and memory allocations lessen dramatically and begin to approach a constant speed no matter the original data size. In a sense, the function is splitting itself into two different working functions by splitting each array using sorting. A worst case scenario would be when the largest or smallest value in the array is chosen everytime as the pivot point. This, unfortunately, keeps everything sorted in one array rather than two. The function efficiency is greatly reduced as it loses its ability to simultaneously work on more than one array. The same is true if the array is full of the same number over and over. In these scenarios, it performs at O(N^2) or quadratic time where the number of elements to the time/space consumption is in N to N^2 ratio.
#merge-sort This type of algorithm finds the length of the array and finds the number that is half of this. It then divides the array into two arrays (left and right) by the the position number in the array. So if you have an array of 4 values, the mid point would be position 2. So the values at position 1 and 2 could be put into a left array and postions 3 and 4 could be put into a right array. We could call these 'partitions'. After this is done, we do it again and again (recursively) until each value is isolated or the left and right array has only 1 value. Now, we can think of this as an upside down tree that starts with one main trunk with two major branches, like an upside down Y. Then each of these two branches split into two more branches and so on. When we get to the final two branches, we compare them to each other and sort them, putting them in a new array with least to the left and greatest to the right. We do this by continually comparing the first element in the array to first element in the other array we are comparing it with. When we identify the least, we erase it from its old array and put it in the new one. We do this to the next greatest one. We work back up the upside down tree this way. The new arrays replacing the old unsorted halves. Eventually, we come back to two sorted arrays which we do the final combination into the new array, comparing as we go.
For the merge sort the best case,average case, and worst case performances are all O(log N) which means at first the workload is heavy causing a spike in time and memory allocation in comparison with number of items. However, as it begins to break down the arrays and process them separately, it approaches a constant speed despite the number of elements to process. In some data sets, it is actually more efficient than quick sort. Even in the worst case scenario, merge sort does 39% fewer comparisons than quick sort does in its average scenario. However, the more number of elements the more memory allocation is used due to the fact that it uses 2X the number of elements as it creates a new array each time it sorts the individual arrays with one element each.