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
- Compare the first and second elements of the array.
- If the first element is greater than the second element, swap their positions.
- Repeat this process until the end of the array.
- Once this process is complete, the last element is fixed in its position as the largest value.
- 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!