Sorting Suite
Sorting Suite
Sorting algorithms are one of the common domains for studying Computer Science data structures and algorithms. They give us an opportunity to focus on algorithms of various complexity all solving a relatively simple problem.
In this project, you are challenged to implement four fundamental sorting algorithms. Your final submission should include at least these eight files:
bubbleSort.js
bubbleSorttest.js
insertionSort.js
insertionSorttest.js
mergeSort.js
mergeSorttest.js
quickSort.js
quickSorttest.js
For your testing start with testing small arrays of numbers and/or letters. For more advanced testing you will need to generate arrays of numbers to see how large of an array your different sorting algorithms can sort.
1. Bubble Sort
Big Picture
Bubble Sort is often one of the first algorithms of any kind that programmers attempt. There are very few steps which make it not too difficult to implement. But it takes many instructions to actually execute – so the performance is typically quite bad.
The Algorithm
You can see a graphical run of the algorithm here.
For a high level understanding check out the wikipedia article. Bubble sort works by comparing and possibly swapping two values in an array. Say we start with this array of numbers:
5 0 1 3 4 2
The algorithm would start with a variable previous
pointing to the first element,
5
and current
pointing to the second value 0
. Then if current
is
less than previous
the two values are swapped. The swap would take
place in this case, because 0
is less than 5
.
After that single swap the sequence would be:
v v
0 5 1 3 4 2
The algorithm would continue with previous
advancing one spot to the right,
to point at 5
, and current
advancing to point at 1
.
1
is less than 5
, so we swap them again to get:
0 1 5 3 4 2
Notice that the 5
moved forward two spaces.
This is commonly called “bubbling up”.
The number being “bubbled” will always be the largest number seen up to this point.
Now, previous
advances to 2
, and current
advances to 3
.
3
is not less than 2
, so the focus advances without swapping.
This repeats moving right one space at a time until
reaching the end of the array,
meaning the largest number in the array must be in the last position.
After the second bubbling, we know that the last two items must be the two
largest items in the array, and they are sorted. After the third iteration,
the last 3 items are sorted. Thus we repeat the process once for each
element in the array, allowing us to know that the last n
items are sorted,
where n
is the size of the array.
Richer Example
Let’s look at the sequence for a more outoforder sequence:
Each iteration the largest out of order number bubbles to the top
 [ 5, 4, 3, 2, 1 ]
 [ 4, 5, 3, 2, 1 ]
 [ 4, 3, 5, 2, 1 ]
 [ 4, 3, 2, 5, 1 ]

[ 4, 3, 2, 1, 5 ]
 [ 4, 3, 2, 1, 5 ]
 [ 3, 4, 2, 1, 5 ]
 [ 3, 2, 4, 1, 5 ]
 [ 3, 2, 1, 4, 5 ]

[ 3, 2, 1, 4, 5 ]
 [ 3, 2, 1, 4, 5 ]
 [ 2, 3, 1, 4, 5 ]
 [ 2, 1, 3, 4, 5 ]
 [ 2, 1, 3, 4, 5 ]

[ 2, 1, 3, 4, 5 ]
 [ 2, 1, 3, 4, 5 ]
 [ 1, 2, 3, 4, 5 ]
 [ 1, 2, 3, 4, 5 ]
 [ 1, 2, 3, 4, 5 ]

[ 1, 2, 3, 4, 5 ]
 [ 1, 2, 3, 4, 5 ]
 [ 1, 2, 3, 4, 5 ]
 [ 1, 2, 3, 4, 5 ]
 [ 1, 2, 3, 4, 5 ]
 [ 1, 2, 3, 4, 5 ]
Expectations
Implement a bubbleSort
function which will make the following code snippet work:
bubbleSort(["d", "b", "a", "c"])
=> ["a", "b", "c", "d"]
2. Insertion Sort
Big Picture
Insertion sort is a next step up from Bubble Sort. Make sure that you’ve successfully implemented Bubble Sort before you dive into this section.
Insertion sort uses slightly more complex logic but the algorithm is generally much higher performing than Bubble.
The Algorithm
You can see a visualization of the algorithm here.
For a high level understanding check out the wikipedia article. Insertion sort works by adding items to a sorted array. Typically sorting is done in place inside the array which needs sorting. The first element in the array becomes the sorted array. We iterate through the set to be sorted, pulling one element at a time, then inserting it into its correct position in the sorted section of the array.
Let’s start with this array of numbers: [ 1, 0, 4, 3, 2 ]
Pass 1
A list with only one item is always sorted, so we start our sorted list with the first element in our array:
original array: [ 1, 0, 4, 3, 2 ]
[ sorted  unsorted ]
original array: [ 1,  0, 4, 3, 2 ]
Pass 2
We pull the first unsorted element, the 0
, and compare it to the last element of the sorted set, 1
. Since 0
is less than 1
, we swap it with the 1
:
unsorted: [0, 4, 3, 2]
to insert: 0
[ sorted  unsorted ]
before insert: [ 1,  0, 4, 3, 2 ]
[ sorted  unsorted ]
after insert: [ 0, 1,  4, 3, 2 ]
Pass 3
We pull the first unsorted element, the 4
, and compare it to the last element of the sorted set, 1
. Since 4
is greater than 1
, we add the 4
to the end of the sorted array.
unsorted: [4, 3, 2]
to insert: 4
[ sorted  unsorted ]
before insert: [ 0, 1,  4, 3, 2 ]
[ sorted  unsorted ]
after insert: [ 0, 1, 4,  3, 2 ]
Pass 4
We pull the first unsorted element, the 3
, and compare it to the last element of the sorted set, 4
. Since 3
is less than 4
, we swap the 3
and 4
. We then compare the 3
with the previous position of the sorted set, 1
. Since 3
is greater than 1
we have the 3
in the correct position.
unsorted: [3, 2]
to insert: 3
[ sorted  unsorted ]
before insert: [ 0, 1, 4,  3, 2 ]
[ sorted  unsorted ]
after insert: [ 0, 1, 3, 4,  2 ]
Pass 5
We pull the first unsorted element, the 2
, and compare it to the last element of the sorted set, 4
. Since 2
is less than 4
we swap the 2
and 4
. We then compare the 2
with the previous position of the sorted set, 3
. Since 2
is less than 3
, we swap the 2
and 3
. Then we look at the previous position of the sorted set, 1
. Since 2
is greater than 1
we have the 2
in the correct position.
unsorted: [2]
to insert: 2
[ sorted  unsorted ]
before insert: [ 0, 1, 3, 4,  2 ]
[ sorted  unsorted ]
after insert: [ 0, 1, 2, 3, 4,  ]
Since we have no more elements in the unsorted section of our array, we are done with the algorithm.
Challenge
Implement an insertionSort
which will make the following code snippet
work:
insertionSort(["d", "b", "a", "c"])
=> ["a", "b", "c", "d"]
3. Merge Sort
Merge sort is the most complicated, quickest and fascinating of the three IMO. You can create a really interesting recursive solution.
Theory
For a high level understanding check out the wikipedia article. For a sweet line dancing example, see this Merge sort can be thought of as splitting an array into two arrays and sorting the halves by also splitting them in half and sorting those halves by splitting them in half… and so on. Once we split down to arrays
For a brief example let’s look at a simple array. The first step would be to split the array into smaller arrays
Split the arrays
original_array: [2, 0, 1, 3]
first_split: [2, 0]
remaining_split: [1, 3]
We then proceed to split one of those arrays further until we are left with just numbers to compare.
Split again
first_split: [2, 0]
first_num: 2
second_num: 0
We then compare those numbers and put them back into an array together. 1 and 0 will swap, creating a sorted split array.
Sort the doubly split array
sorted_first_split: [0, 2]
remaining_split: [1, 3]
We do the same operation on the remaining split, but we it’s already sorted so there will be no change. We then merge these two sorted halves together to create a final sorted array. This is accomplished by comparing the each element in the first split to those in the remaining split.
Merge the split and sorted arrays
first_split_candidates: 0, 2
remaining_split_candidates: 1, 3
first_combination: 0, 1
second_combination: 0, 1, 2
third_combination: 0, 1, 2, 3
merged_array: [0, 1, 2, 3]
Challenge
Implement a mergeSort
function which will make the following code snippets
work.
mergeSort(["d", "b", "a", "c"])
=> ["a", "b", "c", "d"]
4. Quick Sort
With quick sort we take an array and choose one of the indexes as a pivot. We then want to move all the elements larger than the pivot to the right of the pivot and all the items smaller than the pivot to the left.
After moving all the elements to either side of the pivot we can then recursively quick sort the elements on either side of the pivot.
Example of one iteration.
pivot starts with the last index p = array.length  1
p
[ 9, 8, 5, 2, 1, 6, (3) ]
^^
swap [ (3), 8, 5, 2, 1, 6, 9 ]
^^
compare [ (3), 8, 5, 2, 1, 6, 9 ]
^^
compare [ (3), 8, 5, 2, 1, 6, 9 ]
^^
swap [ 1, 8, 5, 2, (3), 6, 9 ]
^^
compare [ 1, 8, 5, 2, (3), 6, 9 ]
^^
swap [ 1, (3), 5, 2, 8, 6, 9 ]
^^
compare [ 1, (3), 5, 2, 8, 6, 9 ]
^^
compare [ 1, (3), 5, 2, 8, 6, 9 ]
^^
swap [ 1, 2, 5, (3), 8, 6, 9 ]
^^
compare [ 1, 2, 5, (3), 8, 6, 9 ]
^^
compare
[ 1, 2, 5, (3), 8, 6, 9 ]
^^
swap
[ 1, 2, (3), 5 8, 6, 9 ]
^^
compare
[ 1, 2, (3), 5 8, 6, 9 ]
^^
compare
[ 1, 2, (3), 5 8, 6, 9 ]
^^
pivot is at its correct location
[ 1, 2, 3, 5 8, 6, 9 ]
Now we need to quickSort the elements on each side of the pivot.
something like…
quickSort([1, 2]);
quickSort([5, 8, 6, 9])
Evaluation
The evaluation will be pass/fail.
You will be need to be able to explain any of the four sorting algorithms using numbered cards.
You will be need to write either quick sort or merge sort after explaining how they work.