Elementary Sorting Methods: the inefficient three

mgcadmin 18-09-2021

A look at the three most common elementary sorting algorithms using perl

The First Three

When learning about sorting algorithms, or whenever one talks about sorting algorithms, there are three elementary sorting algorithms that are bound to be brought up. In order of efficiency these three are Bubble sort, Selection sort, and Insertion sort.

These are collectively known as whats called exchange sorts, and they are far less efficient than the more commonly used Quicksort, Mergesort, and Heapsort, all of which are O(n log n) algorithms.

Still, its worth studying these algorithms, as not only are they valuable for sorting smaller collections of data, but they give us a place to start when designing more efficient algorithms.

Bubble sort

Bubble sort is the simplest of sorting algorithms, and its also the least efficient. In fact its inefficiency is so widely known that when Presidential Candidate gave an interview at Google before becoming president, he was asked "What algorithm would you use to sort 3 million 32-bit integers?" His answer? "Well, i think bubble sort would be the wrong way to go." While this exchange (no pun intended) was most likely pre-planned, it highlights bubble sorts most striking characteristic: its incredible inefficiency.

Why is bubble sort so bad? lets take a look at a working example to better understand why. Here is a working example of bubble sort in Perl:

sub bubbleSort {
  my (@unsorted) = @_;
  my ($i, $j, $tmp);
  for ($i = 0; $i < $#unsorted; $i++)
  {
   for ($j = $i+1; $j <= $#unsorted; $j++)
   {
    if ($unsorted[$j] < $unsorted[$i])
    {
      $tmp = $unsorted[$i];
      $unsorted[$i] = $unsorted[$j];
      $unsorted[$j] = $tmp;
    }
   }
 }
 return @unsorted;
}

The loop within a loop is common to the three elementary sorting methods i'm going to discuss. It's what happens inside that nested loop that alters the efficiency of each algorithm. Bubble sort is straight forward, It takes each value in the array, and directly compares it to each value in the array swapping the values to place the smaller value first. The problem is that bubblesort keeps checking all the values even if its already placed the value being examined in its sorted position.

Selection Sort

Selection sort cuts down on the amount of comparisions it needs to make because after each iteration, the first n values are definitively placed in their sorted position. Selection sort works by selecting the smallest value not yet chosen and placing it at the point in the list that the outer loop has gotten to.

For example: if the loop is on its third iteration, it selects the third smallest number in the list (the smallest value not yet selected) and places it in the third position of the array, swapping the proper element with the element currently occupying that space if it differs from the value selected.

sub selectionSort {
  my (@unsorted) = @_;
  my ($i, $j, $smallest, $tmp);
  for ($i = 0; $i < $#unsorted; $i++)
  {
    $smallest = $j;
    for ($j = $i + 1; $j < $#unsorted; $j++)
    {
      if ($unsorted[$j] < $unsorted[$smallest]) {
        $smallest = $j;
      }
   }
   if ($unsorted[$smallest] < $unsorted[$i]) {
   $tmp = $unsorted[$i];
   $unsorted[$i] = $unsorted[$smallest];
   $unsorted[$smallest] = $tmp;
  }
 }
 return @unsorted;
}

By employing this method of sorting, we've cut down drastically on the number of swaps compared to bubble sort. Where bubble sort does O(n²) comparisons and O(n²) swaps, Selection sort only makes O(n) swaps for every O(n²) comparisons.

But we still have room for improvement.

Insertion Sort

Where insertion sort build the sorted list from the front, and moving towards the end of the list, Insertion sort takes elements from the end of the list and inserts them into their sorted position towards the front of the list. It's a little bit harder to visualize how it works compared to the other two methods so lets take a look at the code for insertion sort:

sub insertionSort {
  my (@unsorted) = @_;
  my ($i, $j, $v, $tmp);
  for ($i = 1; $i <= $#unsorted; $i++)
  {
   $j = $i;
   $v = $unsorted[$j];
   while ($unsorted[$j - 1] > $v)
   {
    $unsorted[$j] = $unsorted[$j-1];
    $j--;
   }
   $unsorted[$j] = $v;
  }
  return @unsorted;
}

A Sorting Algorithm Show Down

The best way to understand whats happening during each sort is to borrow a technique from Robert Sedgewick's seminal text "Algorithms" and peek inside the data structure being sorted during the sort.

In order to do this I've modified the above code examples to sort charachters instead of integers, and to print the contents of the array being sorted after each iteration of the outside loop. Aside from these changes the code used is exactly the same. If we want to sort the string "ASORTINGEXAMPLE" into alphabetical order, we end up with the following output:

original array: 
A S O R T I N G E X A M P L E 
Bubble Sort: 
A S O R T I N G E X A M P L E 
A A S R T O N I G X E M P L E 
A A E S T R O N I X G M P L E 
A A E E T S R O N X I M P L G 
A A E E G T S R O X N M P L I 
A A E E G I T S R X O N P M L 
A A E E G I L T S X R O P N M 
A A E E G I L M T X S R P O N 
A A E E G I L M N X T S R P O 
A A E E G I L M N O X T S R P 
A A E E G I L M N O P X T S R 
A A E E G I L M N O P R X T S 
A A E E G I L M N O P R S X T 
A A E E G I L M N O P R S T X 

original array: 
A S O R T I N G E X A M P L E 
Selection Sort: 
A A O R T I N G E X S M P L E 
A A E R T I N G E X S M P L O 
A A E E T I N G R X S M P L O 
A A E E G I N T R X S M P L O 
A A E E G I L T R X S M P N O 
A A E E G I L M R X S T P N O 
A A E E G I L M N X S T P R O 
A A E E G I L M N O S T P R X 
A A E E G I L M N O P T S R X 
A A E E G I L M N O P R S T X 

original array: 
A S O R T I N G E X A M P L E 
Insertion Sort: 
A O S R T I N G E X A M P L E 
A O R S T I N G E X A M P L E 
A O R S T I N G E X A M P L E 
A I O R S T N G E X A M P L E 
A I N O R S T G E X A M P L E 
A G I N O R S T E X A M P L E 
A E G I N O R S T X A M P L E 
A E G I N O R S T X A M P L E 
A A E G I N O R S T X M P L E 
A A E G I M N O R S T X P L E 
A A E G I M N O P R S T X L E 
A A E G I L M N O P R S T X E 
A A E E G I L M N O P R S T X 

As you can see the order in which the elements, and the number of swaps conducted vary greatly based on which sorting method is employed. But keep in mind, None of these three sorting methods can compare to more advanced sorting methods like Merge Sort, Quicksort, or Tree Sort. Of course, we could have also just used perls build in sort(), itsself being an implementation of Merge Sort.

All of the source code for the examples used in this article are available on my github:

https://github.com/maxgoren/examples/blob/main/elementarysorts.pl

---