DEV Community

WolfOf420Stret
WolfOf420Stret

Posted on

Understanding Insertion Sort in Kotlin : A Beginner's Guide

What is Insertion Sort?

Insertion Sort is an intuitive and adaptive sorting algorithm that builds the final sorted array one element at a time. It works similarly to how most people sort playing cards in their hands - by taking one card at a time and inserting it into its correct position among the cards already sorted.

While not optimal for large datasets, Insertion Sort is efficient for small arrays and nearly-sorted data. Its simplicity and adaptiveness make it a practical choice in specific scenarios, and it's often used as part of more complex hybrid sorting algorithms.

When to Use Insertion Sort?

Insertion Sort shines in several specific scenarios:

  • Nearly Sorted Data: When the array is already partially sorted, Insertion Sort can perform nearly linearly.

  • Small Datasets: For arrays with fewer than 50 elements, Insertion Sort's simplicity can make it faster than more complex algorithms.

  • Online Sorting: When you need to sort data as it is received, Insertion Sort can efficiently insert new elements into an already-sorted portion.

However, for large, randomly ordered datasets, more efficient algorithms like QuickSort or MergeSort are preferable.

How Insertion Sort Works

Insertion Sort divides the array into sorted and unsorted sections, gradually moving elements from the unsorted section to their correct position in the sorted section.

Step-by-Step Explanation

Here's how Insertion Sort operates:

  1. Start with First Element:

    • Consider the first element as a sorted section of length one.
  2. Take Next Element:

    • Select the first unsorted element and store it as the 'key'.
  3. Insert in Correct Position:

    • Compare the key with each element in the sorted section from right to left.
    • Shift larger elements one position ahead.
    • Insert the key in its correct position.

Visual Representation of Insertion Sort

To sort the array [64, 34, 25, 12, 22]:

  1. Take 34 and insert it before 64: [34, 64, 25, 12, 22]
  2. Take 25 and insert it before 34: [25, 34, 64, 12, 22]
  3. Continue until fully sorted: [12, 22, 25, 34, 64]

Pseudocode for Insertion Sort

function insertionSort(arr):
    for i from 1 to size of arr:
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = key
    return arr
Enter fullscreen mode Exit fullscreen mode

Implementing Insertion Sort in Kotlin

fun insertionSort(arr: IntArray): IntArray {
    for (i in 1 until arr.size) {
        val key = arr[i]
        var j = i - 1

        // Move elements greater than key one position ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
    }
    return arr
}
Enter fullscreen mode Exit fullscreen mode

Code Walkthrough

  • Outer Loop:

    • Iterates through the unsorted section, starting from the second element.
  • Inner Loop:

    • Shifts elements of the sorted section that are greater than the key.
  • Key Placement:

    • Places the key in its correct position within the sorted section.

Visual Step-by-Step Process

Initial Array: [64, 34, 25, 12, 22]

Pass 1:

[64, 34, 25, 12, 22]  // Compare 34 with sorted portion
 ↓   ↓
[34, 64, 25, 12, 22]  // Insert 34 before 64
 ✓   ✓
Enter fullscreen mode Exit fullscreen mode

Pass 2:

[34, 64, 25, 12, 22]  // Compare 25 with sorted portion
 ↓   ↓   ↓
[25, 34, 64, 12, 22]  // Insert 25 at start
 ✓   ✓   ✓
Enter fullscreen mode Exit fullscreen mode

Pass 3:

[25, 34, 64, 12, 22]  // Compare 12 with sorted portion
 ↓   ↓   ↓   ↓
[12, 25, 34, 64, 22]  // Insert 12 at start
 ✓   ✓   ✓   ✓
Enter fullscreen mode Exit fullscreen mode

Pass 4:

[12, 25, 34, 64, 22]  // Compare 22 with sorted portion
 ↓   ↓   ↓   ↓   ↓
[12, 22, 25, 34, 64]  // Insert 22 after 12
 ✓   ✓   ✓   ✓   ✓
Enter fullscreen mode Exit fullscreen mode

Legend:

  • ↓ : Elements being compared
  • ✓ : Sorted portion
  • Unmarked: Unsorted portion

Time Complexity Analysis

Best Case: O(n)

  • Occurs when array is already sorted
  • Only requires one comparison per element
  • No shifting needed

Worst Case: O(n²)

  • Occurs when array is sorted in reverse order
  • Maximum comparisons and shifts needed for each element
  • Each element must be compared with every sorted element

Average Case: O(n²)

  • Random input data
  • Approximately half of the sorted elements are compared
  • Requires shifting of elements

Space Complexity: O(1)

  • Only requires a single additional memory space for the key
  • Sorts in-place

Detailed Performance Breakdown

Number of Operations

For an array of size n:

  1. Comparisons:

    • Best case: (n-1)
    • Worst case: n(n-1)/2
    • Average case: n(n-1)/4
  2. Shifts:

    • Best case: 0
    • Worst case: n(n-1)/2
    • Average case: n(n-1)/4

Performance Table

Array Size (n) Best Case (n) Average Case (n²/4) Worst Case (n²/2)
10 9 22 45
100 99 2,475 4,950
1,000 999 249,750 499,500

Optimization Techniques

  1. Binary Search Insertion
   fun insertionSortWithBinarySearch(arr: IntArray): IntArray {
       for (i in 1 until arr.size) {
           val key = arr[i]
           val location = binarySearch(arr, key, 0, i)
           for (j in i downTo location + 1) {
               arr[j] = arr[j - 1]
           }
           arr[location] = key
       }
       return arr
   }
Enter fullscreen mode Exit fullscreen mode
  1. Shell Sort Variation
    • A variation of Insertion Sort that allows exchange of items that are far apart

Comparison with Other Sorting Algorithms

Algorithm Best Case Average Case Worst Case Space Stable
Insertion Sort O(n) O(n²) O(n²) O(1) Yes
Selection Sort O(n²) O(n²) O(n²) O(1) No
Bubble Sort O(n) O(n²) O(n²) O(1) Yes
Quick Sort O(n log n) O(n log n) O(n²) O(log n) No

Advantages and Disadvantages of Insertion Sort

Advantages:

  • Adaptive - efficient for data that is already substantially sorted
  • Stable - maintains relative order of equal elements
  • In-place - only requires a constant amount O(1) of additional memory space
  • Online - can sort a list as it receives it

Disadvantages:

  • Quadratic time complexity makes it inefficient for large datasets
  • Generally performs worse than advanced algorithms like QuickSort
  • Requires shifting of elements, which can be expensive

Conclusion

Insertion Sort, while not suitable for large datasets, remains a valuable algorithm in specific scenarios, particularly for small or nearly-sorted arrays. Its adaptiveness, stability, and simple implementation make it a practical choice in certain applications, especially when dealing with continuous, real-time data streams.

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more