Insertion Sort Algorithm: Visualization and Animation

Insertion sort is an algorithm used to sort a list of items in ascending, descending or any other custom order. In the previous articles, we’ve explored what insertion sort is, how it works, and even looked at its pseudocode. Now, let’s bring this algorithm to life through visualization and animation. By the end of this article, you’ll gain an intuitive understanding of how insertion sort modifies data, making the entire concept much clearer and easier to grasp.

Why Visualization and Animation are Helpful

Sorting algorithms can sometimes feel abstract. Instead of just reading about how they work, seeing them in action can make a huge difference! Visualizations help us understand:

  • How elements are compared: You can actually see which elements are being compared at each step.
  • How elements are shifted: The shifting of elements to create space for insertion becomes very clear.
  • The overall flow of the algorithm: Animation provides a step-by-step view of how the algorithm progresses from an unsorted to a sorted state.

Visualization of Various Steps in Insertion Sort Algorithm

Let’s visualize how insertion sort works by applying it to a small array of numbers: [8, 2, 4, 1, 3]. Insertion sort visits one element at a time from the unsorted portion and gradually builds a sorted list by “inserting” elements into their correct positions within the sorted portion.

Here’s how the algorithm sorts the list step by step:

Step 0: Initial State

Initially, we consider the first element 8 to be already sorted and this becomes the initial sorted portion. The rest of the array [2, 4, 1, 3] is the unsorted portion that we’ll gradually insert into the sorted portion.

Step 1: Inserting 2

  1. We pick the first element from the unsorted portion, which is 2.
  2. We compare 2 with 8 (the last element in the sorted portion).
  3. Since 2 is less than 8, we shift 8 to the right to make space for 2.
  4. We insert 2 into its correct position at the beginning of the array.
  5. Now, the sorted portion is [2, 8] and the unsorted portion is [4, 1, 3].

Step 2: Inserting 4

  1. We pick the first element from the unsorted portion, which is 4.
  2. We compare 4 with 8 (the last element in the sorted portion).
  3. Since 4 is less than 8, we shift 8 to the right.
  4. We compare 4 with 2 (the next element from the end).
  5. Since 4 is greater than 2, we insert 4 between 2 and 8.
  6. Now, the sorted portion is [2, 4, 8] and the unsorted portion is [1, 3].

Step 3: Inserting 1

  1. We pick the first element from the unsorted portion, which is 1.
  2. We compare 1 with 8 (the last element in the sorted portion).
  3. Since 1 is less than 8, we shift 8 to the right.
  4. We compare 1 with 4, since 1 is less than 4, we shift 4 to the right.
  5. We compare 1 with 2, since 1 is less than 2, we shift 2 to the right.
  6. We insert 1 at the beginning of the array.
  7. Now, the sorted portion is [1, 2, 4, 8] and the unsorted portion is [3].

Step 4: Inserting 3

  1. We pick the first element from the unsorted portion, which is 3.
  2. We compare 3 with 8 (the last element in the sorted portion).
  3. Since 3 is less than 8, we shift 8 to the right.
  4. We compare 3 with 4, since 3 is less than 4, we shift 4 to the right.
  5. We compare 3 with 2, since 3 is greater than 2, we insert 3 between 2 and 4.
  6. Now, the sorted portion is [1, 2, 3, 4, 8] and the unsorted portion is empty.

After these steps, the entire array [1, 2, 3, 4, 8] is sorted.

In summary: Insertion sort works by repeatedly taking an element from the unsorted portion and inserting it into the correct position within the sorted portion. This process continues until the entire array is sorted.

Step By Step Slide Show

Below is the step by step visualization of insertion sort algorithm:

What’s Next?

Now that you have visualized how insertion sort works, you might want to: