Selection Sort in Kotlin

Sorting is a fundamental operation in computer science, and there are various algorithms to achieve it. One such simple yet effective algorithm is Selection Sort. In this blog post, we’ll explore the Selection Sort algorithm, its implementation in Kotlin, and analyze its time complexity.

Selection Sort Overview

Selection Sort is a comparison-based sorting algorithm that works by dividing the input array into two parts: the sorted and the unsorted sub-arrays. The algorithm repeatedly finds the minimum element from the unsorted sub-array and swaps it with the first element of the unsorted subarray. This process is repeated until the entire array is sorted.

Implementation in Kotlin

Let’s implement Selection Sort in Kotlin:

fun selectionSort(arr: IntArray) {
    val n = arr.size

    for (i in 0 until n - 1) {
        var minIndex = i

        for (j in i + 1 until n) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }

        // Swap the found minimum element with the first element
        val temp = arr[minIndex]
        arr[minIndex] = arr[i]
        arr[i] = temp
    }
}

fun main() {
    val array = intArrayOf(64, 25, 12, 22, 11)
    
    println("Original Array: ${array.joinToString(", ")}")

    selectionSort(array)

    println("Sorted Array: ${array.joinToString(", ")}")
}

In this implementation, the selectionSort() function takes an array of integers and sorts it in ascending order using the Selection Sort algorithm.

Analysis of Time Complexity

Selection Sort has a time complexity of O(n²) where n is the number of elements in the array. This makes it inefficient for large datasets. The algorithm performs poorly compared to more advanced sorting algorithms like Merge Sort or Quick Sort.

Conclusion

While Selection Sort is a simple algorithm to understand and implement, it is not the most efficient sorting algorithm for large datasets. In real-world scenarios, it’s often better to use more optimized algorithms for sorting. Nevertheless, learning and implementing Selection Sort can be a valuable exercise in understanding sorting algorithms and their performance characteristics.

In summary, we’ve covered the basics of Selection Sort, implemented it in Kotlin, and discussed its time complexity. I hope this blog post helps you gain a better understanding of Selection Sort and its role in sorting algorithms. Happy coding!