Sorting Algorithms: Part 1

I have been revisiting sorting algorithms, and decided to write about them to solidify my understanding, and spread the knowledge! Hope you enjoy!

Problem:

Given an unsorted array of integers, sort the array in ascending order in place and return the same array.

Solution:

There are multiple sorting algorithms. For this article, I will focus on insertion sort.

Insertion sort sorts the array in place by looping through the array. At each iteration the elements to the left of the current element are sorted. We loop, yes another loop, through the sorted elements to find where the current element should be placed.

Pseudocode:

1. Loop through the array starting from the second element. We start with the second element because a one element array is already sorted :)

2. For each iteration store the number at index i in a variable, numToBePlaced.

3. Create a pointer variable j = i - 1

4. Create another loop which continues while j is greater than 0, and the number at j is greater than numToBePlaced. Inside this loop place the number at j at the j + 1 spot , and decrement j.

5. When the inner loop breaks place numToBePlaced at the j + 1 place - The loop breaks when we don’t have any numbers to the left ofj or all the numbers to the left of j are smaller than or equal to numToBePlaced.

^{The image is from the book Introduction to Algorithms by Thomas H. Cormen and others.}

Code:

function insertionSort(arr) {
  //loop through the array
  for (let i = 1; i < arr.length; i++) {
    //store the current number in a variable
    const elToBePlaced = arr[i];
    //Create a pointer variable j which will loop through the sorted part of the array
    let j = i - 1; 
    //search for where elToBePlaced should go
    while (j >= 0 && arr[j] > elToBePlaced) {
      arr[j + 1] = arr[j]; 
      j -= 1; 
    }
    //place it in its rightful position!
    arr[j + 1] = elToBePlaced
  }
  return arr;
}

If you're new to algorithms and aren't quite sure how this one works, I recommend using this visualizer. I use it to understand any code I don't fully grasp.

Time Complexity

In the worst case - i.e an array with all numbers in descending order, each element will have to be compared and swapped with every preceding element which will result in an O(N²) time complexity. TLDR: if you see a loop inside a loop then the time complexity is likely quadratic.

Space Complexity

Because we are sorting the array in place, there is no extra space being used that is proportional to the input array. Therefore space complexity is O(1) or constant.

And there you have it! Insertion sort! Reach out if you have any questions or want to talk through this algorithm or any other I write about on here.

Happy coding!