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
  • bubbleSort-test.js
  • insertionSort.js
  • insertionSort-test.js
  • mergeSort.js
  • mergeSort-test.js
  • quickSort.js
  • quickSort-test.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 out-of-order 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

Sorting Algorithms Video

Merge Sort Chart.

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.

Lesson Search Results

Showing top 10 results