#Sort algorithms
##Learning Objectives
- Understand what sort algorithms do and how computers sort things
- build a bubble sort and understand its Big O notation
- build a merge sort and understand its Big O notation
What is a Sort algorithm?
Think back to the phonebook example we did where we were looking up John smith, would it have worked if the phone book wasnt sorted?
Why else would a computer want to sort things? Think back to the different data structures that Aaron taught this morning.
If you have a sorted dataset you dont need to load it all into memory, you can just begin a search in approxamitelyu the right spot rather than going through the whole list.
We're going to learn two different sorting algorithms today and I want you guys to think about which is better
Before we get into CS stuff I want you guys to think about all the different ways that you sort things naturally
###Bubble Sort This is often the first sort algorithm people learn and for good reason, its one of the easiest to exaplain and visualize.
I kind of talked about a Bubble Sort algorithm a long time ago when I asked you guys how a computer would sort students based on height. Does anyone remember how it worked? Why dont I take some volunteers and lets go through it again.
Lets pseudocode this out first and then try to write it in javscript based off that.
bubbleSort(array)
Now whats the first step in the bubble sort going to be?
We want to compare the first item to the second item right?
Then the second item to the third
lets add that in
bubblesort(array)
for each i in 0 to length of array do
end for
Now what should I do inside of this loop?
What do I need to check?
bubblesort(array)
for each i in length of array do
if array[i] > array[i+1] then
temp = array[i]
array[i] = array[i+1]
array[i+1] = temp
end for
So this would go through the array one and sort it but what do we need to do for a bubble sort?
We cant just go through it once and expect to be done right? We have to go through it again, and if we dont have to switch anything we're done.
How could we write this out using a do...while loop in pseudocode?
Now I want you guys to try to spend 20min converting our pseudocode to javascript, I'll go through it after everyones given it a shot.
- What is the Big O notation for a bubble sort? remember we have to assume the worst case scenario
###Merge Sort So bubble sort is really slow and its relaly only useful as an example of sorting algorithm to get students on their way.
Its O(n**2)
However there is a better way!
Enter...merge sort!
The algorithm for merge sort is based on the idea that it’s easier to merge two already sorted lists than it is to deal with a single unsorted list. To that end, merge sort starts by creating n number of one item lists where n is the total number of items in the original list to sort. Then, the algorithm proceeds to combine these one item lists back into a single sorted list.
The merging of two lists that are already sorted is a pretty straightforward algorithm. Assume you have two lists, list A and list B. You start from the front of each list and compare the two values. Whichever value is smaller is inserted into the results array. So suppose the smaller value is from list A; that value is placed into the results array. Next, the second value from list A is compared to the first value in list B. Once again, the smaller of the two values is placed into the results list. So if the smaller value is now from list B, then the next step is to compare the second item from list A to the second item in list B. The code for this is
function merge(left, right){
var result = [],
il = 0,
ir = 0;
while (il < left.length && ir < right.length){
if (left[il] < right[ir]){
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
return result.concat(left.slice(il)).concat(right.slice(ir));
}
This function merges two arrays, left and right. The il variable keeps track of the index to compare for left while ir does the same for right. Each time a value from one array is added, its corresponding index variable is incremented. As soon as one of the arrays has been exhausted, then the remaining values are added to the end of the result array using concat().
The merge() function is pretty simple but now you need two sorted lists to combine. As mentioned before, this is done by splitting an array into numerous one-item lists and then combining those lists systematically.
Think about this in non CS terms at first, dont we basically want to split our items up into pairs over and over and over again?
function mergeSort(items){
// Terminal condition - don't need to do anything for arrays with 0 or 1 items
if (items.length < 2) {
return items;
}
var work = [],
i,
len;
for (i=0, len=items.length; i < len; i++){
work.push([items[i]]);
}
work.push([]); //in case of odd number of items
for (var lim=len; lim > 1; lim = Math.floor((lim+1)/2)){
for (var j=0,k=0; k < lim; j++, k+=2){
work[j] = merge(work[k], work[k+1]);
}
}
return work[0];
}
First thing to notice is that we have a terminal case at the very top, if the array is less than 2 items it doesnt need to be sorted.
For arrays with 2 or more items, we first add each element of the input array as a element in a multidmensional array work
Then we add an extra item so that when we split it to find the middle we dont cut anything off.
Then we use a nested loop with some variables. Lets take a look at the outer loop first what does this loop through?
What does the inner loop loop though?
Two variables, j which is the index for the arrya that we are going to return, and k which is the index of the item from the work array
If we've wrote everthing correctly It should work.
###Challenges
If you've made it this far, Why not go a little deeper? Write what weve done in javascript in ruby :)
###resources http://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html https://github.com/nzakas/computer-science-in-javascript/