Kotlin Coding Test Course, Bubble Sort Program 1

In this course, we will learn how to implement the bubble sort algorithm using Kotlin. Bubble sort is one of the simplest and most intuitive sorting algorithms, which sorts an array by comparing and swapping each element. This course will be helpful for those preparing for coding tests.

What is Bubble Sort?

Bubble sort is a comparison-based sorting algorithm that works by comparing two adjacent elements and swapping them if they are not in the correct order. This process is repeated until all elements are sorted. The time complexity of this algorithm is O(n^2) in the worst case, and it is a stable sort.

How Bubble Sort Works

The basic operation of bubble sort works as follows:

  1. Start by comparing the first element of the array with the adjacent element.
  2. If the first element is greater than the second element, swap their positions.
  3. Repeat this process until the end of the array.
  4. Once a pass is completed, the last element will be the largest, indicating that sorting is complete.
  5. Repeat this process from the beginning until no more swaps are needed.

Algorithm Problem Definition

Now, let’s implement the bubble sort algorithm. We will write a Kotlin program that sorts the given integer array in ascending order.

Problem

A given integer array arr. Write a function to sort this array in ascending order using bubble sort.

The function signature is as follows:

fun bubbleSort(arr: IntArray): IntArray

Implementing in Kotlin

Now, let’s implement the function bubbleSort() in Kotlin to solve the problem. Below is the implemented code:


fun bubbleSort(arr: IntArray): IntArray {
    val n = arr.size
    for (i in 0 until n - 1) {
        // Flag for optimization
        var swapped = false
        for (j in 0 until n - i - 1) {
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j + 1]
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
                swapped = true
            }
        }
        // If no swaps occurred, the array is already sorted
        if (!swapped) break
    }
    return arr
}

Code Explanation

The code above takes an array arr as input and returns a sorted array. Let’s explain each part of the code:

  • val n = arr.size: Stores the size of the array.
  • Two for loops are used to iterate through the array. The outer loop performs a total of n-1 passes, while the inner loop handles the comparison operations.
  • The swapped flag checks if any swaps occurred during the current pass. If no swaps occurred, the array is already sorted.
  • In the part of the code that swaps the positions of two elements, a temporary variable is used to swap the values.
  • If no swaps occurred, the loop exits without further iteration.

Example Test

Now let’s test the bubbleSort() function. Here are some test cases:


fun main() {
    val arr1 = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    println("Before sorting: ${arr1.joinToString(", ")}")
    val sortedArr1 = bubbleSort(arr1)
    println("After sorting: ${sortedArr1.joinToString(", ")}")

    val arr2 = intArrayOf(5, 1, 4, 2, 8)
    println("Before sorting: ${arr2.joinToString(", ")}")
    val sortedArr2 = bubbleSort(arr2)
    println("After sorting: ${sortedArr2.joinToString(", ")}")
}

Test Results

When you run the main() function above, the following results will be output:


Before sorting: 64, 34, 25, 12, 22, 11, 90
After sorting: 11, 12, 22, 25, 34, 64, 90
Before sorting: 5, 1, 4, 2, 8
After sorting: 1, 2, 4, 5, 8

Time Complexity Analysis

Let’s analyze the time complexity of bubble sort:

  • Worst case: O(n^2) – when the array is sorted in reverse order.
  • Best case: O(n) – when the array is already sorted. In this case, it only takes one pass to finish.
  • Average case: O(n^2)

Bubble sort is less efficient compared to simple sorting algorithms like insertion sort and is not used for large datasets. However, it is suitable for understanding and practicing algorithm basics due to its simplicity.

Conclusion

In this course, we implemented the bubble sort algorithm using Kotlin. Bubble sort is a comparison-based sorting algorithm that is easy to understand and intuitive. Since it is a frequently tested topic in coding tests, be sure to practice it repeatedly.

Practice Problems

Try to improve your own bubble sort implementation or create various test cases. You can also challenge yourself with problems like:

  • Write a function to sort a given array in descending order.
  • Measure the time taken by bubble sort and compare performance for different input sizes.
  • Try to implement bubble sort recursively.

In addition, through learning various sorting algorithms, develop a deeper understanding of algorithms. Thank you!