DEV Community

Bill Odida
Bill Odida

Posted on

Understanding Selection Sort in Kotlin: A Beginner's Guide

What is Selection Sort?

Selection Sort is a simple and intuitive sorting algorithm that divides the input array into two parts: a sorted section and an unsorted section. It repeatedly selects the smallest (or largest, depending on the order) element from the unsorted section and swaps it with the first element of the unsorted section, effectively growing the sorted section one element at a time.

While not as efficient as algorithms like Merge Sort or Quick Sort, Selection Sort is easy to understand and implement. It is most suitable for small datasets due to its simplicity and predictable behavior.

When to Use Selection Sort?

Selection Sort is not the fastest algorithm for large datasets, but it has some use cases where it might be a reasonable choice:

  • Small Datasets: For small arrays, the simplicity of Selection Sort can make it a convenient choice.

  • Limited Memory: Selection Sort sorts in place, meaning it requires minimal additional memory, making it suitable for memory-constrained applications.

  • Understanding Sorting Fundamentals: Its straightforward nature makes Selection Sort an excellent starting point for learning about sorting algorithms.

However, for larger datasets, Selection Sort's inefficiency becomes apparent due to its O(n²) time complexity in both average and worst-case scenarios.

How Selection Sort Works

Selection Sort operates in a step-by-step process that involves finding the smallest (or largest) element in the unsorted section and moving it to the sorted section.

Step-by-Step Explanation

Here's how Selection Sort works:

  1. Find the Smallest Element:

    • Start from the first element of the array and traverse through the unsorted section to find the smallest element.
  2. Swap the Smallest Element:

    • Swap the smallest element with the first element of the unsorted section, effectively growing the sorted section by one.
  3. Repeat:

    • Move to the next element and repeat the process until the entire array is sorted.

Visual Representation of Selection Sort

To sort the array [29, 10, 14, 37, 13]:

  1. Find the smallest element (10) and swap it with the first element: [10, 29, 14, 37, 13]
  2. Find the next smallest element (13) and swap it with the second element: [10, 13, 14, 37, 29]
  3. Continue this process until the array is fully sorted: [10, 13, 14, 29, 37]

Pseudocode for Selection Sort

function selectionSort(arr):
    for i from 0 to size of arr - 1:
        minIndex = i
        for j from i + 1 to size of arr:
            if arr[j] < arr[minIndex]:
                minIndex = j
        swap arr[i] with arr[minIndex]
    return arr
Enter fullscreen mode Exit fullscreen mode

Implementing Selection Sort in Kotlin

fun selectionSort(arr: IntArray): IntArray {
    for (i in arr.indices) {
        // Assume the first unsorted element is the smallest
        var minIndex = i
        for (j in i + 1 until arr.size) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        // Swap the smallest element with the first unsorted element
        val temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp
    }
    return arr
}
Enter fullscreen mode Exit fullscreen mode

Code Walkthrough

  • Outer Loop:

    • The outer loop starts from the first element and moves towards the last, representing the growing sorted section.
  • Inner Loop:

    • The inner loop scans the unsorted section of the array to find the smallest element.
  • Swap Operation:

    • The smallest element is swapped with the first element of the unsorted section, ensuring the sorted section grows by one.

Visual Step-by-Step Process

Initial Array: [29, 10, 14, 37, 13]

Pass 1:

[29, 10, 14, 37, 13]  // Find minimum in entire array
 ↓   ↓         
[10, 29, 14, 37, 13]  // 10 is minimum, swap with first element
 ✓
Enter fullscreen mode Exit fullscreen mode

Pass 2:

[10, 29, 14, 37, 13]  // Find minimum in unsorted portion
 ✓   ↓          ↓
[10, 13, 14, 37, 29]  // 13 is minimum, swap with second element
 ✓   ✓
Enter fullscreen mode Exit fullscreen mode

Pass 3:

[10, 13, 14, 37, 29]  // Find minimum in unsorted portion
 ✓   ✓   ↓
[10, 13, 14, 37, 29]  // 14 is already in position
 ✓   ✓   ✓
Enter fullscreen mode Exit fullscreen mode

Pass 4:

[10, 13, 14, 37, 29]  // Find minimum in unsorted portion
 ✓   ✓   ✓   ↓   ↓
[10, 13, 14, 29, 37]  // 29 is minimum, swap with fourth element
 ✓   ✓   ✓   ✓
Enter fullscreen mode Exit fullscreen mode

Final Result:

[10, 13, 14, 29, 37]  // Array is sorted
 ✓   ✓   ✓   ✓   ✓
Enter fullscreen mode Exit fullscreen mode

Legend:

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

Time Complexity Analysis

Best Case: O(n²)

  • Even if the array is already sorted, Selection Sort still needs to verify this by comparing all elements
  • For each element i, it needs to scan through (n-i) elements to confirm it's in the right position
  • Total comparisons: (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2

Worst Case: O(n²)

  • Occurs when array is sorted in reverse order
  • Same number of comparisons as best case
  • Maximum number of swaps needed (n-1 swaps)

Average Case: O(n²)

  • Regardless of input distribution, Selection Sort always makes the same number of comparisons
  • Number of comparisons: n(n-1)/2
  • Number of swaps ranges from 0 to (n-1)

Space Complexity: O(1)

  • Only requires a single additional memory space for the swap operation
  • Sorts in-place, modifying the original array

Detailed Performance Breakdown

Number of Operations

For an array of size n:

  1. Comparisons:
    • First pass: (n-1) comparisons
    • Second pass: (n-2) comparisons
    • Third pass: (n-3) comparisons And so on...

Total comparisons = (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2

  1. Swaps:
    • Best case: 0 swaps (already sorted)
    • Worst case: (n-1) swaps (reverse sorted)
    • Average case: (n-1)/2 swaps

Performance Table

Array Size (n) Comparisons Best Case Swaps Worst Case Swaps
10 45 0 9
100 4,950 0 99
1,000 499,500 0 999

Optimization Techniques

  1. Early Termination

    • If no swaps are made in a pass, the array is sorted
    • However, this doesn't improve the big-O complexity
  2. Memory Usage Optimization

   fun selectionSort(arr: IntArray) {
       for (i in arr.indices) {
           var minIdx = i
           for (j in i + 1 until arr.size) {
               if (arr[j] < arr[minIdx]) minIdx = j
           }
           // Single swap operation using XOR
           if (i != minIdx) {
               arr[i] = arr[i] xor arr[minIdx]
               arr[minIdx] = arr[i] xor arr[minIdx]
               arr[i] = arr[i] xor arr[minIdx]
           }
       }
   }
Enter fullscreen mode Exit fullscreen mode

Comparison with Other Sorting Algorithms

Algorithm Time Complexity (Average) Space Complexity Stable In-Place
Selection Sort O(n²) O(1) No Yes
Bubble Sort O(n²) O(1) Yes Yes
Quick Sort O(n log n) O(log n) No Yes
Merge Sort O(n log n) O(n) Yes No

Advantages and Disadvantages of Selection Sort

Advantages:

  • Simple to understand and implement
  • Performs well on small datasets
  • Requires no additional memory

Disadvantages:

  • Inefficient for large datasets due to O(n²) time complexity
  • Not a stable sorting algorithm (does not preserve the order of equal elements)

Conclusion

Selection Sort is a straightforward sorting algorithm best suited for small datasets or learning purposes. While it may not match the efficiency of more advanced algorithms like Merge Sort or Quick Sort, its simplicity and in-place sorting make it a useful tool in specific scenarios.

Top comments (0)