Differences Between Selection Sort and Insertion Sort
Selection Sort and Insertion Sort are two simple comparison-based sorting algorithms. Both are easy to understand, easy to implement, and useful for learning how sorting works. At first glance, they may seem almost identical because both repeatedly build a sorted portion of the array. The important difference is how they build that sorted portion.
Selection Sort repeatedly searches for the smallest remaining element and puts it in its correct position. Insertion Sort, on the other hand, takes the next element and inserts it into the correct position within the portion that is already sorted.
1. The Core Idea
Selection Sort: Find the minimum, then swap
Selection Sort divides the array into two conceptual parts: a sorted portion on the left and an unsorted portion on the right. During each pass, it searches the unsorted portion for the smallest element. Once the smallest element is found, it swaps that element with the first element of the unsorted portion.
In other words: select the smallest remaining value and place it where it belongs.
Insertion Sort: Take the next element and insert it
Insertion Sort also grows a sorted portion from left to right. However, instead of searching the entire unsorted portion for a minimum, it takes the next element and moves larger elements to the right until the correct position for that element is found.
In other words: take the next value and insert it into the sorted portion.
2. A Simple Example
Consider the array:
[5, 2, 4, 1, 3]How Selection Sort approaches it
Selection Sort looks through the unsorted portion to find the smallest value. On the first pass, it finds 1 and swaps it with 5. The array becomes:
[1, 2, 4, 5, 3]It then searches the remaining unsorted portion for the next smallest value. The process continues until every element is in its correct position.
How Insertion Sort approaches it
Insertion Sort starts by treating 5 as a sorted portion. It then takes 2 and inserts it before 5:
[2, 5, 4, 1, 3]Next, it takes 4. Since 5 is larger than 4, it shifts 5 to the right and places 4 before it:
[2, 4, 5, 1, 3]It keeps repeating this process, inserting each new element into the correct location in the sorted portion.
3. The Main Difference in Their Algorithms
The easiest way to remember the difference is to focus on what each algorithm does during a pass:
- Selection Sort searches for the smallest element.
- Insertion Sort shifts and inserts the current element into its proper position.
Selection Sort asks: "What is the smallest element remaining?"
Insertion Sort asks: "Where should this element go among the elements I have already sorted?"
4. Comparison of Selection Sort and Insertion Sort
| Feature | Selection Sort | Insertion Sort |
|---|---|---|
| Basic strategy | Find the minimum element and swap it into position. | Take the next element and insert it into the sorted portion. |
| Sorted portion | Grows by selecting the minimum from the unsorted portion. | Grows by inserting one element at a time. |
| Best-case time | O(n²) | O(n) |
| Average-case time | O(n²) | O(n²) |
| Worst-case time | O(n²) | O(n²) |
| Space complexity | O(1) extra space | O(1) extra space |
| Stable? | Generally no, with the standard swap-based implementation. | Yes, with the standard implementation. |
| Adaptive? | No. It performs essentially the same comparisons even when the array is nearly sorted. | Yes. It can become very fast when the array is already or nearly sorted. |
| Movement of elements | Usually fewer writes because it primarily swaps elements. | May perform many shifts when elements are far from their final positions. |
5. Time Complexity: Why the Difference Matters
Selection Sort
Selection Sort searches the remaining unsorted elements on every pass. Even if the array is already sorted, it still needs to scan the unsorted portion to determine which element is the minimum.
Therefore, its best, average, and worst-case time complexity is generally:
Best: O(n²)
Average: O(n²)
Worst: O(n²)Insertion Sort
Insertion Sort behaves differently. If the array is already sorted, each new element only needs a quick comparison with the preceding element, so very little work is required.
Its typical time complexities are:
Best: O(n)
Average: O(n²)
Worst: O(n²)This makes Insertion Sort particularly useful when the input is already sorted or nearly sorted.
6. Swapping vs. Shifting
Another useful distinction is what happens to elements that are already in the array.
Selection Sort primarily uses swaps. Once it finds the minimum element, it swaps that element with the first element of the unsorted section. This means it generally performs relatively few writes.
Insertion Sort primarily uses shifts. When an element needs to move left, larger elements are shifted one position to the right until the correct location is available.
This distinction can matter when writing to memory is considerably more expensive than comparing values.
7. Stability
A sorting algorithm is called stable when equal elements retain their original relative order after sorting.
Insertion Sort is naturally stable when implemented by shifting elements only when they are strictly greater than the current value.
Standard Selection Sort is generally not stable because swapping the minimum element with the first unsorted element can change the relative order of equal elements.
8. When Should You Use Each One?
Use Insertion Sort when:
- The data is already sorted or nearly sorted.
- You need a stable sorting algorithm.
- You want a simple algorithm that performs well on small inputs.
- New elements are being added incrementally to an already sorted collection.
Use Selection Sort when:
- You want an extremely simple sorting algorithm.
- Minimizing the number of writes or swaps is important.
- The input is small and performance is not a major concern.
- You specifically want to demonstrate the concept of repeatedly selecting the minimum.
9. The Key Insight
Both algorithms are quadratic in their average and worst cases, but that does not mean they behave identically.
Selection Sort is more rigid: it keeps searching for the minimum regardless of how organized the input already is.
Insertion Sort is more responsive to the input: the more sorted the data is, the less work it generally needs to do.
The simplest way to remember the difference:
Selection Sort says: "Find the smallest and select it."
Insertion Sort says: "Take the next element and insert it where it belongs."
10. Final Comparison
Selection Sort and Insertion Sort are both excellent algorithms for understanding the fundamentals of sorting. Neither is normally the first choice for sorting large, unsorted datasets, where more advanced algorithms such as Merge Sort, Heap Sort, or Quicksort are generally more appropriate.
For small or nearly sorted data, however, Insertion Sort can be surprisingly effective. Selection Sort has a different strength: it keeps the implementation simple and limits the number of swaps.
Ultimately, the most important difference is not just their Big-O notation. It is the way they construct the sorted portion of the array: Selection Sort selects the next element by searching for a minimum, while Insertion Sort builds the sorted portion by inserting each new element into its proper place.
No comments:
Post a Comment