Sort algorithms and their implementations

By Kris Terziev October 29, 2021 Programming 16 Minutes

Sorting algorithms are one of the most popular algorithms in programming, and together with searching algorithms, they make data more manageable.

Sorting algorithms allow us to sort or organize data in different formats, alphabetically, numerically, ascending or descending order, highest or lowest, or vice versa. They perform operations on data structures by re-arranging the data, inserting or removing it in specific formats.

There are different sorting algorithms, and we divide them into two formats - stable and unstable sorting.
Stable sorting algorithms treat identical elements of a data structure as the same and preserve their order of appearance. An array containing elements [7, 4, 2, 4, 1, 8] will sort as [1, 2, 4, 4, 7, 8], in this case, 4 is an equal element. The first 4 appears first at index 1 appears first, followed by the 4 at index 3.
In unstable sorting, the ordering of identical elements is not there. The algorithm decides to choose which element goes first. 4 at index 3 can be written before the 4 at index 1.

Does stability in sorting matter?

Stability creates reliability in the ordering of data, and we need it during stacking.
Some of the different types of sorting algorithms include

Heap sort
Quick sort
Insertion sort
Bubble sort
Merge sort
Counting sort
Radix sort
Shell sort
Selection sort and
Bucket sort.

We will be looking at some of them in detail.

Quick sort

Quick sort uses a divide-and-conquer method to sorting. It takes an unsorted sequence and sorts it out in either ascending or descending order. Quick sorts pick a pivot number to base its comparison of all the other numbers. A pivot number is an element chosen from the list and used as a comparison to partition the data structure.
There are different methods to pick out a pivot number:

To pick the last element as pivot
To pick the first element
Pick the middle or median number
Pick a random element

After we choose a pivot number, we iterate through the data structure with it. If an element is higher than the pivot number, the algorithm moves that to one list. Alternatively, if it is less than the pivot number, it is moved to another list.

[0, 9, 3, 8, 2, 7, 5]

If we decide to use the last element as our pivot, our first arrangement will be

Algorithm

STEP 1:
Start

STEP 2:
Choose a pivot number

STEP 3:
Use pivot number to compare other numbers to

STEP 4:
Create a partitioned list with this pivot number.
  IF pivot number is greater than an element, send it to list one
  IF pivot number is less than an element, send it to list two

STEP 5:
Repeat the process until the sequence has a correct order.

STEP 6:
Exit

Code implementation with Python

def quick_sort(arr):
  n = len(arr)
    if n <= 1:
      return arr
    else:
      pivot_no = arr.pop()  

# get the partitioned lists
  list1 = []
  list2 = []

  for item in arr:
    if item > pivot_no:
      list1.append(item)
    else:
      list2.append(item)

  return quick_sort(list2) + [pivot_no] + quick_sort(list1)

#to print the values
print(quick_sort([0, 9, 3, 8, 2, 7, 5]))

Code implementation with Javascript

var arr = [0, 9, 3, 8, 2, 7, 5];

function swap(arr, list1, list2)
{
  var temp = arr[list1];
  arr[list1] = arr[list2];
  arr[list2] = temp;
}

function partition(arr, l, r)
{
  var pivot_no = arr[Math.floor((r + l) / 2)], //getting //a pivot number using the middle element
    a = l, //left pointer
    b = r; //right pointer
  while (a <= b)
  {
    while (arr[a] < pivot_no)
    {
      a++;
    }
    while (arr[b] > pivot_no)
    {
      b--;
    }
    if (a <= b)
    {
      swap(arr, a, b);
      a++;
      b--;
    }
  }
  return a;
}

function quick_sort(arr, l, r)
{
  var index;
  if (arr.length > 1)
  {
    index = partition(arr, l, r); //index returned from //partition
    if (l < index - 1)
    {
      quick_sort(arr, l, index - 1);
    }
    if (index < r)
    {
      quick_sort(arr, index, r);
    }
  }
  return arr;
}
// first call to quicksort
var sortedArray = quick_sort(arr, 0, arr.length - 1);
console.log(sortedArray);

Bubble sort

A bubble sort takes an unsorted list and re-arranges them in ascending or descending order (from lowest to highest). It does this by comparing adjacent values at any given time. The element with the lower value moves to the left, while one with a higher value - to the right. This process repeats until we get to the end of the list.

When we can no longer perform swaps, we break out of the loop.

The bubble sort algorithm is considered inefficient, especially for large data structures. To swap one item, we need to make iterations through the data structure for n^2 times.

[6, 14, 20, 3, 2, 10]

For the first iteration, we'll look at 6 and 14. 6 is already on the left, and it is smaller than 14, so we leave it.

Second iteration,
Then 14 and 20. Leave it

Third iteration
20 and 3. We move 3 to the left. It becomes [6, 14, 3, 20, 2, 10]

Fourth iteration
14 and 3. We move 3 to the left of 14 it becomes [6, 3, 14, 20, 2, 10].

We continue this process, iterating and moving every adjacent value until we sort out the sequence.

Algorithm

STEP 1:
Start

STEP 2:
Compare the first two adjacent numbers

STEP 3:
Move the smaller value to the left and the higher one to the right

STEP 4:
IF smaller value is already on the left, make no swap and leave it as it is

STEP 5:
Repeat this process until the end of the data structure

STEP 6:
If you can no longer make swaps and all items are sorted out, break out of the loop

STEP 7:
Exit

Code implementation with Python

def bubble_sort(list_a):
  length = len(list_a) - 1 
    
  sorted = False 

  while not sorted:  #Repeat until sorted = True
    sorted = True  # to break the loop when the sequence is sorted

    for i in range(0, length): # For every value in the list
      if list_a[i] > list_a[i+1]: #if value in list is greater than value directly to the right of it,
        sorted = False # These values are unsorted
        list_a[i], list_a[i+1] = list_a[i+1], list_a[i] 
                
  return list_a # to return a list that is not sorted

print(bubble_sort([6, 14, 20, 3, 2, 10]))

Code implementation with Javascript

function bubble_sort(arr)
{
  let swapped = true;
  do {
    swapped = false;
    for (let j = 0; j < arr.length; j++)
    {
      if (arr[j] > arr[j + 1])
      {
        let t = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = t;
        swapped = true;
      }
    }
  } while (swapped);
  return arr;
}
var num = [6, 14, 20, 3, 2, 10];
var sortedList = bubble_sort(num);
console.log(sortedList);

Selection sort

A selection sort repeatedly goes through a list to find the smallest or minimum value and sends it to a location. It usually picks the first element to compare its value to the rest. When a new feature with a lower value than the first is found, this becomes the new minimum value.

The program then moves to the left of the list and creates two sub-lists: the unsorted and sorted elements. All minimum values move to the sorted list while higher values remain in the unsorted lists.
The subsequent iterations will go through the unsorted higher value list, looking for the minimum number to send to the sorted list. It continues this process until all higher values move to the sorted list.
The selection sort algorithm has a complexity of O(n^2) with iterations calculated as (n - 1) + (n - 2) + ... + 1. It is known to perform better than the bubble sort.

Algorithm

STEP 1:
Start

STEP 2:
Pick the first element as the minimum value

STEP 3:
Iterate through the data structure to compare the first element with other elements

STEP 4:
IF there is an element with a lower minimum is discovered, make that the new minimum value

STEP 5:
Create two sub-lists and move all identified minimum values to the one list as sorted list and the move the higher values to another list as an unsorted list

STEP 6:
Move through the unsorted higher value list, and pick the minimum values

STEP 7:
Move minimum values from unsorted list to sorted list

STEP 8:
Repeat process for each iteration until the sequence is sorted

STEP 9:
Exit

Code implementation with Python

def selection_sort(num):
  length = range(0, len(num)-1)

  for i in length:
    min_value = i  #picks the first element as the minimum point
      #iterate through the list to compare the first elements to other elements
      for j in range(i+1, len(num)):
        if num[j] < num[min_value]:
          min_value = j
        if min_value != i:
          num[min_value], num[i] = num[i], num[min_value]
  return num

print(selection_sort([6,7,8,2,6,5,3,5,8,7,6,7,8,4,7,9,0]))

Code implementation with Javascript

function selection_sort(arr)
{
  let n = arr.length;
  for (let i = 0; i < n; i++)
  {
    // to get the smallest value
    let min = i;
    for (let j = i + 1; j < n; j++)
    {
      if (arr[j] < arr[min])
      {
        min = j;
      }
    }
    if (min != i)
    {
      // iterating and creating sublists
      let tmp = arr[i];
      arr[i] = arr[min];
      arr[min] = tmp;
    }
  }
  return arr;
}
let arr = [12, 2, 41, 6, 14, 3];
selection_sort(arr);
document.write(arr);

Insertion sort

Insertion sort is a stable sort algorithm that takes a data sequence and divides them into sorted and unsorted lists. It picks the first element by default and makes it the sorted list (with length = 1) while the rest are considered unsorted. It takes a similar approach to selection sort by dividing one list into two.

With insertion sort, the main iteration starts with the second element since the program considers the first element a sorted element. For each iteration, we compare the value of the first unsorted element to the one already sorted. If the value is higher, it moves to the right of the sorted items. If not - it goes to the left. This simple process repeats until the sequence is sorted.

The thing about insertion sort is that the algorithm doesn't need to iterate through the entire list before sorting. It just compares each element at the current iteration point with the sorted items to determine if they should be moved or not. The Insertion sort algorithm has a complexity of O(n^2) because it compares two nested lists.

[6, 3, 7, 2, 4, 9]

First iteration:
6 automatically moves to the sorted array list as the first element

Sorted array = 6
Unsorted array = [3,7,2,4,9]

Second iteration:
The algorithm compares 3 to 6. 3 is less than 6, so 3 moves to the left of 6.

Sorted array = [3, 6]
Unsorted array = [7,2,4,9]

Third iteration:
7 compared to 3 and 6. 7 is greater than 3 and 6, moving to the right.

Sorted array = [3, 6, 7]
Unsorted array = [2, 4, 9]

Fourth iteration:
2 is smaller than 3 and 6, moving to the left of elements on the sorted list.

Sorted array = [2, 3, 6, 7]
Unsorted array = [4, 9]

Fifth iteration:
4 is greater than 3 but less than 6 and 7. So 4 moves between 3 (to the right of 3) and 6 (to the left of 6).

Sorted array = [2, 3, 4, 6, 7]
Unsorted array = [9]

Sixth iteration:
We move 9 to the right of the elements.

Sorted array = [2,3,4,6,7,9]

Algorithm

STEP 1:
Start

STEP 2:
Divide the list into two and automatically move the first element of the array into the sorted list.

STEP 3:
Compare the first value of the sorted elements with the element in the sorted array.

STEP 4:
IF sorted element is greater, move the new element to the left of it.
IF sorted element is lower, move the new element to the right of it

STEP 5:
Repeat process for all elements

STEP 6:
Exit

Code implementation with Python

def insertion_sort(num):
  length = range(1, len(num))
    for i in length: #iterating through the values
      value_to_sort = num[i]
      while num[i-1] > value_to_sort and i>0:
        num[i], num[i-1] = num[i-1], num[i]
        i = i -1
  return num

print(insertion_sort([9,8,9,8,4,6,5,2,4,7,8,9,6,8,7,6,5,4,7,8]))

Code implementation with Javascript

function insertion_sort(nums)
{
  let n = nums.length;
  // moving the first element automatically to sorted list
  for (let i = 1; i < n; i++)
  {
    let current = nums[i];
    // The last element of our sorted subarray
    let j = i - 1;
    while ((j > -1) && (current < nums[j]))
    {
      nums[j + 1] = nums[j];
      j--;
    }
    nums[j + 1] = current;
  }
  return nums;
}
let nums = [6, 3, 7, 2, 4, 9];
insertion_sort(nums);
document.write(nums);

Merge sort

Merge sort is a divide and conquer algorithm usually done recursively. Recursion divides a problem into sub-problems and the sub-problem into further sub-problem, and this is how merge sort works.

Say we have the following values:

[24, 4, 12, 8, 18, 10, 2, 44]

We will divide the list into two and divide each group until it gets to each element.

We will examine the individual items, compare their values and merge them into temporary arrays while sorting them. The following process is to pair up separate arrays with their adjacent element in a sorted format.

The paired smaller arrays merge into bigger ones which are remerged into bigger ones and further remerged into bigger ones until every element fits back into one enormous sorted array.

There are two ways of implementing merge sort algorithms. We can achieve this using a bottom-up approach or a top-down approach. In the first approach, rather than solve recursively throughout, we can solve iteratively once the elements are broken down into sub-arrays. Both methods have in common that the complete list is broken into individual pieces and sorted.
Merge sort has a time complexity of 0(log n) and is considered one of the fastest sort algorithm.

Algorithm

STEP 1:
Start

STEP 2:
Divide the array into equal parts

STEP 3:
Divide each sub-array recursively until each becomes an individual element

STEP 4:
Combine pairs of the individual elements while sorting them out

STEP 5:
Merge each pair with another pair of paired-elements

STEP 6:
Keep pairing until the entire list becomes one complete sorted array.

STEP 7:
Exit.

Like all recursion, the code for a merge sort should have a base recursion function that determines how the rest of the recursion should perform.

Code implementation with Python

def merge_sort(arr, l_index, r_index):
  #the base function
  if l_index >= r_index:
    return

  mid = (l_index + r_index)//2
  merge_sort(arr, l_index, mid)
  merge_sort(arr, mid + 1, r_index)
  merge(arr, l_index, r_index, mid)
 
#recursive function    
def merge(arr, l_index, r_index, mid):
  # this makes copies of the arrays to be merged
  # The second parameter is non-inclusive, so we have to increase by 1
  l_copy = arr[l_index:mid + 1]
  r_copy = arr[mid+1:r_index+1]

  # the initial values for variables needed to keep track of our current #position in each array
  l_copy_index = 0
  r_copy_index = 0
  sorted_index = l_index

  # Go through both copies until we run out of elements in one
  while l_copy_index < len(l_copy) and r_copy_index < len(r_copy):
    # If our left_copy has the smaller element, put it in the sorted
    # part and then move forward in left_copy (by increasing the pointer)
    if l_copy[l_copy_index] <= r_copy[r_copy_index]:
      arr[sorted_index] = l_copy[l_copy_index]
      l_copy_index = l_copy_index + 1
    # else, move to the right
    else:
      arr[sorted_index] = r_copy[r_copy_index]
      r_copy_index = r_copy_index + 1
      
  # Regardless of where we got our element from
  # move forward in the sorted part
  sorted_index = sorted_index + 1

  # when we run out of copies in either the right or left copies
  # will go through the remaining elements and add them
  while l_copy_index < len(l_copy):
    arr[sorted_index] = l_copy[l_copy_index]
    l_copy_index = l_copy_index + 1
    sorted_index = sorted_index + 1

  while r_copy_index < len(r_copy):
    arr[sorted_index] = r_copy[r_copy_index]
    r_copy_index = r_copy_index + 1
    sorted_index = sorted_index + 1

arr = [33, 42, 9, 37, 8, 47, 5, 29, 49, 31, 4, 48, 16, 22, 26]
merge_sort(arr, 0, len(arr) -1)
print(arr)

Code implementation with Javascript

function merge(left_copy, right_copy)
{
  let arr = []
  // if any of the array is empty, we break out of loop
  while (left_copy.length && right_copy.length)
  {
    //while loop to pick the smaller elements of the left and right sub arrays
    if (left_copy[0] < right_copy[0])
    {
      arr.push(left_copy.shift())
    }
    else
    {
      arr.push(right_copy.shift())
    }
  }
  // Concatenating the leftover elements
  // (in case we didn't go through the entire left or right array)
  return [...arr, ...left_copy, ...right_copy]
}

function merge_sort(num)
{
  const half = num.length / 2
  // Base function case or terminating case
  if (num.length < 2)
  {
    return num
  }
  const left = num.splice(0, half)
  return merge(merge_sort(left), merge_sort(num))
}
num = [24, 4, 12, 8, 18, 10, 2, 44];
document.write(merge_sort(num));

Sort algorithms and their implementations