kotlin coding test course, bubble sort program 2

Hello! In this tutorial, we will learn how to implement the Bubble Sort algorithm using the Kotlin language. Bubble Sort is one of the most basic sorting algorithms and is often featured as a fundamental problem in coding tests due to its simplicity. We will solve a problem together with detailed explanations.

Problem Definition

Write a program to sort a given integer array in ascending order. The length of the array is N (1 ≤ N ≤ 1000), and each element is M (-10⁴ ≤ M ≤ 10⁴).

Example

• Input: [64, 34, 25, 12, 22, 11, 90]
• Output: [11, 12, 22, 25, 34, 64, 90]

Algorithm Explanation

Bubble Sort is an algorithm that sorts by comparing two adjacent elements and swapping them if they are in the wrong order. This process is repeated, and thus the largest value moves to the end of the array, which is why it is called “Bubble.” The average and worst-case time complexity of Bubble Sort is O(N²).

Bubble Sort Algorithm

1. Get the size N of the array.
2. Repeat from 0 to N-1.
3. Repeat from the first index of the array up to N-i-1, comparing the values at the two indices.
4. If the value at the first index is greater than the value at the second index, swap the two values.
5. After all iterations are complete, the array will be sorted.

Kotlin Implementation

Now let’s implement the algorithm in Kotlin:

fun bubbleSort(arr: IntArray): IntArray {
    val n = arr.size
    for (i in 0 until n - 1) { 
        // The last i elements are already sorted, so repeat up to n-i-1.
        for (j in 0 until n - i - 1) {
            // Compare two adjacent elements
            if (arr[j] > arr[j + 1]) {
                // Swap
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}

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

Explanation

The code above shows a basic implementation of Bubble Sort. The main function bubbleSort takes an integer array as input and returns the sorted array. It operates by using two nested loops to compare adjacent elements and swap them when necessary.

Code Execution Process

When the code is executed, it will output the following result:

Sorted array: 11, 12, 22, 25, 34, 64, 90

Complexity Analysis

The time complexity of Bubble Sort is O(N²). This is because, in the worst case, all elements need to be compared. However, in the best case (an already sorted array), the time complexity reduces to O(N). The space complexity is O(1).

Advantages and Disadvantages of Bubble Sort

The advantages and disadvantages of Bubble Sort are as follows:

• Advantages:
  • Simple to implement.
  • Consumes minimal memory.
  • Can check whether the array is already sorted during the sorting process.
• Disadvantages:
  • Time complexity is too high, making it inefficient for large datasets.
  • Performs worse compared to other efficient sorting algorithms.

Application Problem

Now let’s tackle a slightly more advanced problem based on the concepts we’ve covered. Remove duplicate elements from the given array and output the sorted result.

Problem Definition

Write a program that takes an integer array as input, removes duplicate elements, and outputs the result sorted in ascending order.

Example

• Input: [64, 34, 25, 25, 12, 22, 11, 90, 90]
• Output: [11, 12, 22, 25, 34, 64, 90]

Code Implementation

fun removeDuplicatesAndSort(arr: IntArray): IntArray {
    return arr.distinct().toIntArray().let { bubbleSort(it) }
}

fun main() {
    val inputArray = intArrayOf(64, 34, 25, 25, 12, 22, 11, 90, 90)
    val resultArray = removeDuplicatesAndSort(inputArray)
    println("Array after removing duplicates and sorting: ${resultArray.joinToString(", ")}")
}
    

Result

When the above code is executed, the following result will be produced:

Array after removing duplicates and sorting: 11, 12, 22, 25, 34, 64, 90

Conclusion

In this tutorial, we explored the Bubble Sort algorithm in detail, and through this, we solved basic sorting and duplicate removal problems. Although Bubble Sort is a simple and easy-to-understand algorithm, familiarizing yourself with various sorting algorithms that appear in coding tests will allow you to solve problems more effectively. In the next tutorial, we will cover more efficient sorting algorithms. Thank you!