Sort Routines
Output
Sorting method:
Unsorted list:
Sorted list:
Time Taken:
Bubble Sort
The bubble sort routine works by comparing two values and swapping their positions depending on their size. For example, if a list is required to be ordered from smallest to largest, the bigger values will be moved to the right and the smaller ones will be moved to the left. This sort routine makes passes over the list until it is ordered correctly.
The table below shows the workings of this sort routine (highlighted is where swaps occur; braces show swap pairs).
|
7 |
2 |
9 |
1 |
3 |
|
{2 |
7} |
9 |
1 |
3 |
|
2 |
7 |
{1 |
9} |
3 |
|
2 |
{1 |
7} |
9 |
3 |
|
{1 |
2} |
7 |
9 |
3 |
|
1 |
2 |
7 |
{3 |
9} |
|
1 |
2 |
{3 |
7} |
9 |
Advantages
- Easy to understand
- Easy to implement
- No external memory needed
- Performs greatly when the list is almost sorted
Disadvantages
- Very time expensive
- More element assignments than insertion sort
Code Snippet (JavaScript)
Insertion Sort
The insertion sort routine works by splitting the list into sorted and unsorted sides. Items from the unsorted list are compared against the sorted list to determine their new position. The routine finishes when the sorted list portion takes up the whole list.
The table below shows the workings of this sort routine (highlighted is where insertions occur; braces show separation between sorted and unsorted lists).
|
{7} |
{2 |
9 |
1 |
3} |
|
{2 |
7} |
{9 |
1 |
3} |
|
{2 |
7 |
9} |
{1 |
3} |
|
{1 |
2 |
7 |
9} |
{3} |
|
{1 |
2 |
3 |
7 |
9} |
Advantages
- Efficient on small sets of data
- Easy to implement
- Only pass through the array once
- Also performs well when the list is almost sorted
Disadvantages
- Less effective on larger data sets
Code Snippet (JavaScript)
Quick Sort
The quicksort is a much more complex sorting routine which implements recursion (a function/subroutine calling itself). It involves picking a pivot number which is used to compare against elements. All elements which are smaller are placed in a 'smaller than' list and elements which are larger are placed in a 'larger than' list. The same function is then performed on both of these lists repeatedly until there are either 1 or 0 elements in all lists. All lists are then collected back together, sorted. The pivot number can be chosen at random, or the first or last item; however, it is more effective to pick a pivot which is around the middle (which is unknown to begin with, leaving it by chance).
The table below shows the workings of this sort routine (highlighted indicated pivot number; braces show sorted lists).
|
7 |
2 |
9 |
1 |
3 |
|
|
2 |
|
||
|
{1 |
2} |
{7 |
9 |
3} |
|
|
7 |
|
||
|
|
|
{3 |
7 |
9} |
|
{1 |
2 |
3 |
7 |
9} |
Advantages
- Efficient on large sets of data
- Works well on very unsorted list
- Fastest best case speed of all 3 routines
Disadvantages
- Slows down drastically on unsuccessful pivot selections
- Can be complex to implement
Code Snippet (JavaScript)
