Insertion Sort vs Selection Sort

When you’re learning about sorting algorithms, comparing different approaches can help you understand their strengths and weaknesses. Insertion sort and selection sort are two simple sorting algorithms often taught to beginners. In this article, we’ll compare these two, highlighting their differences, performance characteristics, and use cases. By the end, you’ll have a clear understanding of when to use each algorithm and why.

What are Insertion Sort and Selection Sort?

Before diving into the comparison, let’s briefly recap what these two algorithms do:

• Insertion Sort: Builds a sorted array one element at a time. It iterates through the array, picking up an element and inserting it into its correct position within the already sorted portion. Think of it like sorting a hand of playing cards by inserting each card into its proper place.
• Selection Sort: Repeatedly finds the minimum element from the unsorted portion and places it at the beginning. The algorithm divides the array into two parts: the sorted portion and the unsorted portion. In each iteration, the smallest element from the unsorted part is selected and swapped with the leftmost element of the unsorted part.

If you need a refresher, here’s a helpful link to the insertion sort article: Introduction to Insertion Sort Algorithm and selection sort algorithm: Introduction to Selection Sort Algorithm.

Key Differences

Let’s delve deeper into these differences and understand why they matter.

How They Work: A Closer Look

1. Insertion Sort:

   • Imagine you are arranging a bookshelf. You take one book at a time and insert it into its correct position among the books already arranged.
   • Insertion sort works similarly. It divides the array into a sorted and an unsorted region. It picks elements from the unsorted region and places them in the correct spot within the sorted region.
   • This involves shifting elements to make space for the inserted element.
   • For example, consider the list [5, 2, 4, 6, 1, 3]. Insertion sort would proceed as follows:
     • First, consider [5] as sorted sublist and [2, 4, 6, 1, 3] as unsorted sublist.
     • Pick 2 from unsorted list, compare it to 5 and insert to create the sorted sublist [2, 5] and the unsorted list becomes [4, 6, 1, 3].
     • Pick 4 from unsorted list, compare it to 5 and then 2 and insert to create the sorted sublist [2, 4, 5] and the unsorted list becomes [6, 1, 3].
     • Pick 6 from unsorted list, compare it to 5, 4 and then 2 and insert to create the sorted sublist [2, 4, 5, 6] and the unsorted list becomes [1, 3].
     • Pick 1 from unsorted list, compare it to 6, 5, 4, 2 insert to create the sorted sublist [1, 2, 4, 5, 6] and the unsorted list becomes [3].
     • Pick 3 from unsorted list, compare it to 6, 5, 4 and then 2, 1 and insert to create the sorted sublist [1, 2, 3, 4, 5, 6] and the unsorted list becomes empty [].

2. Selection Sort:

   • Imagine you are sorting books on a shelf by repeatedly selecting the smallest book and placing it at the beginning.
   • Selection sort divides the array into two parts: the sorted part (initially empty) and the unsorted part (the entire array).
   • In each iteration, it finds the minimum element from the unsorted part and swaps it with the leftmost element of the unsorted part.
   • For example, consider the list [64, 25, 12, 22, 11]. Selection sort would work like this:
     • Find the minimum element (11) and swap it with the first element (64): [11, 25, 12, 22, 64].
     • Find the minimum element in the remaining unsorted portion (12) and swap it with the second element (25): [11, 12, 25, 22, 64].
     • Find the minimum element in the remaining unsorted portion (22) and swap it with the third element (25): [11, 12, 22, 25, 64].
     • The array is now sorted.

Performance Characteristics

Both insertion sort and selection sort have a time complexity of O(n^2) in the average and worst cases. However, they differ in their best-case performance, stability and number of swaps:

• Best Case:
  • Insertion Sort: O(n) when the array is already sorted. It only needs to make one pass through the array.
  • Selection Sort: O(n^2) even when the array is already sorted. It still needs to compare each element to find the minimum in each pass.
• Number of Swaps:
  • Insertion Sort: Can vary from 0 (best case) to O(n^2) (worst case).
  • Selection Sort: Always O(n).

When to Use Which

• Insertion Sort:
  • Use insertion sort when you have a small dataset or when you expect the data to be nearly sorted.
  • It’s also a good choice when the number of writes to memory is a concern, as it typically involves fewer swaps.
• Selection Sort:
  • Selection sort can be useful when the number of swaps needs to be minimized. This is because selection sort performs exactly n-1 swaps, where n is the number of elements in the array. This makes it useful in situations where memory write operations are costly.

Key Takeaways

• Insertion sort builds a sorted array by inserting elements into their correct positions.
• Selection sort repeatedly finds the minimum element from the unsorted portion and places it at the beginning.
• Both have a time complexity of O(n^2) in the average and worst cases.
• Insertion sort is adaptive and performs well on partially sorted data.
• Selection sort always performs O(n) swaps.
• In most practical scenarios, insertion sort is a better choice than selection sort because it performs better when the input is nearly sorted, and it performs fewer writes to the memory than selection sort.

What’s Next?

Now that you understand the differences between insertion sort and selection sort, you might want to explore:

• Insertion Sort vs Merge Sort
• Insertion Sort Algorithm: Time and Space Complexity
• Other Sorting Algorithms