Difference Between Insertion Sort and Selection Sort

In this article, we will explain the difference between Insertion Sort and Selection Sort. These are two basic sorting algorithms used to arrange numbers in order. We will look at how they work, how fast they are, and when to use each one.

By the end, you'll have a clear understanding of the differences between Insertion Sort and Selection Sort. Here's what we'll cover:

• What is Insertion Sort?
• What is Selection Sort?
• Complexity Comparison
• Key Differences Between Insertion Sort and Selection Sort
• When to Use Which Sorting Algorithm?

What is Insertion Sort?

Insertion Sort is a simple and efficient sorting algorithm. In each iteration, the algorithm removes an element from the unsorted portion of the input data and inserts it into the correct position in the sorted list. This process repeats until all input elements have been processed and the entire list is sorted.

Advantages of Insertion Sort

Here are the key benefits of Insertion Sort:

• Simple Implementation: The algorithm is simple and easy to understand.
• Efficient for Small Data: Insertion sort performs well when the dataset is small or nearly sorted.
• Adaptive: If the input list is partially sorted (may not be completely sorted) then insertion sort takes time complexity of O(n + d), where d is the number of inversions.
• Practical Efficiency: In practice, insertion sort is more efficient than Selection Sort and Bubble Sort even though all of them have O(n²) worst-case time complexity.
• Stable: It maintains the relative order of elements with equal keys.
• In-place: It requires only a constant amount (O(1)) of extra memory.
• Online: Insertion sort can sort a list as it receives it.

Disadvantages of Insertion Sort

Here are the main drawbacks of using Insertion Sort:

• Slow for Large Data: It becomes very slow for large datasets.
• Not Efficient for Unsorted Data: It takes too long if the data is completely unsorted.
• High Overhead: It requires a lot of shifting and cannot be used for large-scale problems.

How Insertion Sort Works

Insertion Sort works by picking an element from the unsorted portion and placing it in its correct position in the sorted portion. This repeats until the array is sorted, with no extra memory used. The steps are:

• Start from the second element (the first is considered sorted).
• Compare the current element with previous elements in the sorted portion.
• Shift larger elements to the right to make space.
• Insert the current element into its correct position.
• Repeat until all elements are sorted.

Let's understand the working of Insertion sort with a visual example:

Implementation of Insertion Sort

Here's the C++ code for Insertion Sort. The algorithm starts by comparing the second element with the first and placing it in the correct position. It then repeats this for each element, shifting larger ones to the right to make space for the current element. This continues until the entire array is sorted.

#include <iostream>
using namespace std;

// Function to perform Insertion Sort
void insertionSort(int A[], int n) {
    int i, j, v;
    for(i = 1; i < n; i++) {
        v = A[i];  // The element to be inserted
        j = i;     // Start comparing from the current element

        // Shift elements that are greater than v one position to the right
        while(j > 0 && A[j - 1] > v) {
            A[j] = A[j - 1];
            j--;
        }

        // Place the element in its correct position
        A[j] = v;
    }
}

// Function to print an array
void printArray(int A[], int n) {
    for(int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Array before sorting: ";
    printArray(arr, n);

    insertionSort(arr, n);

    cout << "Array after sorting: ";
    printArray(arr, n);

    return 0;
}

The output below shows the elements of the array both before and after applying Insertion Sort.

Array before sorting: 12 11 13 5 6
Array after sorting: 5 6 11 12 13

What is Selection Sort?

Selection Sort is an in-place sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the array and placing it in the correct position. It is simple and works well for small datasets or when sorting files with large values and small keys.

Advantages of Selection Sort

Here are the key advantages of Selection Sort:

• Simple to implement: It's easy to understand and write the code.
• In-place sorting: No extra memory is required, as sorting is done within the array itself.
• Efficient for small datasets and fewer swaps: It performs fewer swaps than Bubble Sort, making it suitable for smaller datasets.

Disadvantages of Selection Sort:

Here are the key disadvantages of Selection Sort:

• Inefficient for large datasets: With a time complexity of O(n²), it performs poorly on large arrays.
• Too many comparisons and swaps: It makes more comparisons than necessary and is not optimized for partially sorted arrays.

How Selection Sort Works

Selection Sort works by finding the smallest element in the unsorted portion of the array and swapping it with the current unsorted element. This process continues until all elements are sorted. Here are the steps:

• Find the smallest element in the unsorted portion of the array.
• Swap it with the first unsorted element.
• Repeat this for the rest of the elements until the array is fully sorted.

Let's understand the working of Selection sort with a visual example:

Implementation of Selection Sort

Here's the C++ code for Selection Sort. The selectionSort function finds the minimum element in the unsorted portion and swaps it with the first unsorted element, repeating until the array is sorted. The printArray function displays the array before and after sorting.

#include <iostream>
using namespace std;

// Function to perform Selection Sort
void selectionSort(int A[], int n) {
    int i, j, min, temp;
    for(int i = 0; i < n - 1; i++) {
        min = i;  // Assume the minimum is the first element
        for(int j = i + 1; j < n; j++) {
            if(A[j] < A[min]) {
                min = j;  // Find the index of the minimum element
            }
        }
        
        // Swap the found minimum element with the first element
        temp = A[min];
        A[min] = A[i];
        A[i] = temp;
    }
}

// Function to print an array
void printArray(int A[], int n) {
    for(int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Array before sorting: ";
    printArray(arr, n);

    selectionSort(arr, n);

    cout << "Array after sorting: ";
    printArray(arr, n);

    return 0;
}

Below is the output, showing the array before and after Selection Sort, with elements sorted in ascending order.

Array before sorting: 64 25 12 22 11
Array after sorting: 11 12 22 25 64

Complexity Comparison

Here's a detailed comparison of Insertion Sort and Selection Sort, including their time and space complexities for different cases:

Difference Between Insertion Sort and Selection Sort

Insertion Sort and Selection Sort are simple sorting algorithms with different approaches, swap counts, and stability, as shown in the table below:

When to Use Which Sorting Algorithm?

Use Insertion Sort when the array is small or nearly sorted, as it is simple to implement and performs well in such cases. On the other hand, use Selection Sort when memory usage is a concern, as it doesn't require additional space. It is also suitable for small datasets where ease of implementation is prioritized over efficiency.

Conclusion

In this article, we compared Insertion Sort and Selection Sort. While both are simple algorithms, Insertion Sort is more efficient for small or partially sorted data, whereas Selection Sort performs worse with larger datasets. Understanding their strengths and weaknesses helps in selecting the right algorithm based on factors like data size and memory constraints.