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

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

}

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

 ✓

Pass 2:

[10, 29, 14, 37, 13]  // Find minimum in unsorted portion

 ✓   ↓          ↓

[10, 13, 14, 37, 29]  // 13 is minimum, swap with second element

 ✓   ✓

Pass 3:

[10, 13, 14, 37, 29]  // Find minimum in unsorted portion

 ✓   ✓   ↓

[10, 13, 14, 37, 29]  // 14 is already in position

 ✓   ✓   ✓

Pass 4:

[10, 13, 14, 37, 29]  // Find minimum in unsorted portion

 ✓   ✓   ✓   ↓   ↓

[10, 13, 14, 29, 37]  // 29 is minimum, swap with fourth element

 ✓   ✓   ✓   ✓

Final Result:

[10, 13, 14, 29, 37]  // Array is sorted

 ✓   ✓   ✓   ✓   ✓

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

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]

           }

       }

   }

Comparison with Other Sorting Algorithms

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.