kotlin coding test course, bubble sort

Hello! In this post, we will discuss solving coding test problems using Kotlin. The topic is a representative method for sorting arrays, Bubble Sort. This course will cover the theoretical background and code of bubble sort.

What is Bubble Sort?

Bubble sort is the simplest form of sorting algorithm, named “Bubble” because the largest number in the given data ‘floats to the surface’ last. This method sorts by repeatedly traversing the array and comparing two adjacent elements.

How Bubble Sort Works

1. Compare the first and second elements of the array.
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 this process is complete, the last element is fixed in its position as the largest value.
5. Repeat the above process until sorting is complete.

Time Complexity of Bubble Sort

The worst-case time complexity of bubble sort is O(n²). This is because, for an array of length n, there are n iterations, and each iteration involves n-1 comparisons. However, in the best-case scenario (when the array is already sorted), it has a time complexity of O(n).

Problem Description

Let’s solve the following problem.

Problem: Sort the given integer array in ascending order using the bubble sort algorithm.

Problem-Solving Process

Now, let’s write Kotlin code to solve the problem. First, let’s outline the basic logic of bubble sort.

Implementing Bubble Sort

fun bubbleSort(arr: IntArray): IntArray {
    val n = arr.size
    for (i in 0 until n - 1) {
        for (j in 0 until n - i - 1) {
            // Compare two adjacent elements to sort
            if (arr[j] > arr[j + 1]) {
                // Swapping
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}
    

The code above is a function that takes an integer array as input, sorts it in ascending order, and returns it. It uses two nested for loops to traverse the array, comparing elements and swapping their positions.

Example Execution

Now, let’s call the created function to check if the sorting works correctly.

fun main() {
    val array = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    println("Array before sorting: ${array.joinToString(", ")}")
    val sortedArray = bubbleSort(array)
    println("Array after sorting: ${sortedArray.joinToString(", ")}")
}
    

When the above code is executed, the following output can be obtained.

Array before sorting: 64, 34, 25, 12, 22, 11, 90
Array after sorting: 11, 12, 22, 25, 34, 64, 90
    

Optimizing Bubble Sort

The basic bubble sort code compares to the end of the array on every iteration, which can be inefficient for performance improvements. Therefore, let’s see how we can optimize bubble sort.

Optimization Using a Flag Variable

If the array is already sorted, there is no need to iterate further. To address this, we can set a variable to record ‘whether a swap occurred.’ If no swaps have occurred, we can conclude that the array is sorted.

fun optimizedBubbleSort(arr: IntArray): IntArray {
    val n = arr.size
    var swapped: Boolean
    for (i in 0 until n - 1) {
        swapped = false
        for (j in 0 until n - i - 1) {
            if (arr[j] > arr[j + 1]) {
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
                swapped = true
            }
        }
        // Exit the loop if no swaps occurred
        if (!swapped) {
            break
        }
    }
    return arr
}
    

Example Execution of the Optimized Version

fun main() {
    val array = intArrayOf(64, 34, 25, 12, 22, 11, 90, 1, 2, 3, 4, 5)
    println("Array before sorting: ${array.joinToString(", ")}")
    val sortedArray = optimizedBubbleSort(array)
    println("Array after sorting: ${sortedArray.joinToString(", ")}")
}
    

When the above code is executed, you can see the following results.

Array before sorting: 64, 34, 25, 12, 22, 11, 90, 1, 2, 3, 4, 5
Array after sorting: 1, 2, 3, 4, 5, 11, 12, 22, 25, 34, 64, 90
    

Applications of Bubble Sort

Bubble sort is a simple sorting algorithm, generally suitable for learning purposes or as an introduction to algorithms. However, in situations where there is a large amount of data or efficiency is important, more efficient algorithms like quicksort or mergesort are necessary.

Conclusion

In this post, we explored the concept of bubble sort, its implementation, and optimization techniques. It is very important to try various approaches while learning and implementing algorithms. In the next session, we will cover other sorting algorithms.

Thank you!