kotlin coding test course, selection sort

Introduction

Coding tests play an important role in the hiring process of many companies today. In particular, the ability to solve algorithm problems has a significant impact on both job changes and new hires. In this course, we will implement the Selection Sort algorithm in Kotlin and solve related problems.

What is Selection Sort?

Selection Sort is one of the simple sorting algorithms that works by finding the smallest element in a given list and swapping it with the first position, then finding the smallest element in the remaining list and swapping it with the second position. This process is repeated until the list is sorted.

How Selection Sort Works

1. Find the smallest element in the list.
2. Swap that element with the one at the front of the currently unsorted list.
3. Move the start of the unsorted list forward by one position.
4. Repeat steps 2-3 for the size of the list – 1 times.

Problem Description

Write a selection sort algorithm that sorts a given integer array in ascending order. The specific requirements are as follows:

• Input: Integer array (e.g., [64, 25, 12, 22, 11])
• Output: Sorted integer array (e.g., [11, 12, 22, 25, 64])

Problem Solving Process

Step 1: Understanding the Problem

The first step is to fully understand the problem. It is important to understand how the Selection Sort algorithm sorts the array and clearly define the inputs and outputs.

Step 2: Algorithm Design

Next, we design the algorithm for Selection Sort. We will implement this selection sort algorithm using Kotlin.

fun selectionSort(arr: IntArray): IntArray {
    for (i in arr.indices) {
        // Assume the element with the current index i is the smallest
        var minIndex = i

        // Loop from the next index i to the end to find the minimum value
        for (j in (i + 1) until arr.size) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }

        // Swap the smallest element with the element at the current index
        if (minIndex != i) {
            val temp = arr[i]
            arr[i] = arr[minIndex]
            arr[minIndex] = temp
        }
    }
    return arr
}

Step 3: Code Implementation

Based on the above algorithm, we write the Kotlin code. Below is an example of the implementation of the algorithm:

fun main() {
    val array = intArrayOf(64, 25, 12, 22, 11)
    val sortedArray = selectionSort(array)

    println("Sorted Array: ${sortedArray.joinToString(", ") { it.toString() }}")
}

Step 4: Code Testing

Test the algorithm you wrote to make sure it works correctly. Run the program with the array to check the results.

fun testSelectionSort() {
    val testCases = arrayOf(
        intArrayOf(64, 25, 12, 22, 11) to intArrayOf(11, 12, 22, 25, 64),
        intArrayOf(5, 4, 3, 2, 1) to intArrayOf(1, 2, 3, 4, 5),
        intArrayOf(1, 2, 3, 4, 5) to intArrayOf(1, 2, 3, 4, 5),
        intArrayOf(-1, -5, 3, 0) to intArrayOf(-5, -1, 0, 3)
    )

    for ((input, expected) in testCases) {
        val result = selectionSort(input)
        assert(result.contentEquals(expected)) {
            "Test failed for input: ${input.joinToString(", ")}. Expected: ${expected.joinToString(", ")}, but got: ${result.joinToString(", ")}}"
        }
    }
    println("All tests passed!")
}

fun main() {
    testSelectionSort()
}

Step 5: Optimization and Complexity

The time complexity of Selection Sort is O(n^2), which is the same for both the worst-case and best-case scenarios. This inefficiency of the algorithm can lead to performance degradation when dealing with large amounts of data. However, it can be effectively used when the amount of data is small and the implementation is simple.

Conclusion

In this course, we explored the theory of Selection Sort and how to implement it in Kotlin. Through a simple problem, we understood the process of solving algorithm problems, and we learned about how the algorithm operates through practical examples. In the next course, we will cover more efficient sorting algorithms, so stay tuned.