Sunday, October 1, 2023
HomeAlgorithmsBubble Sort Kotlin Implementation - Sorting Algorithms #2

Bubble Sort Kotlin Implementation – Sorting Algorithms #2

-

Bubble Sort is the simplest Algorithm of all the sorting techniques. It compares two adjacent elements and swaps them if they are in wrong order. In this article we will focus on Bubble Sort Kotlin Implementation

How Bubble Sort Works?

Bubble sort works by iterating through the array of N elements, from the first element to the last, comparing each adjacent elements and swapping them if they are in wrong order. Once an iteration is completed, last element is in sorted position and we will start another iteration through N-1 elements. Enough of the theory, let’s dive into the Bubble Sort Kotlin Implementation Algorithm

Bubble Sort Kotlin Algorithm


package main.dataStructures.sorting
fun main(args: Array<String>) {
var numSwaps = 0
var isSorted = false
val str = readLine()!!
val intList: ArrayList<Int> = ArrayList(str.split(" ").map { it.toInt() }) //1) read values and convert them to arraylist
var lastUnsorted = intList.size 1 // 2) to keep the track of unsorted array
while (!isSorted) {
isSorted = true
for (i in 0 until lastUnsorted) {
if (intList[i] > intList[i + 1]) {
swapValues(intList, i, i + 1)
numSwaps++
isSorted = false // 3) making this as false whenever the swap needs to be performed.
}
}
lastUnsorted// 4) decreasing the count since one more element from right side is placed in sorted position
}
for(i in intList) {
println(i)
}
}
fun swapValues(list: ArrayList<Int>, a: Int, b: Int) {
val temp = list[b]
list[b] = list[a]
list[a] = temp
}

view raw

BubbleSort.kt

hosted with ❤ by GitHub

Related Links

Things to Explain from Above Algorithm

Let us briefly discuss the points which are commented and are worth mentioning from the above algorithm.

  1. Read values and convert them to arraylist: As usual, we will read input from the console using readLine() method and convert it to arraylist in this line of code.
  2. To keep the track of unsorted array: Earlier we mentioned that for each iteration, the respective last element in the iteration gets sorted. So from next iteration onwards, we will iterate through 0 to (last element-1). This variable helps tracking that.
  3. Making this as false whenever the swap needs to be performed: Here isSorted is being made as false because we identified adjacent items that needs to be swapped. If any iteration is such that no adjacent items needs to be swapped, then that means the total array is sorted. Otherwise we will make isSorted = false so that it is ready for next iteration.
  4. Decreasing the count since one more element from right side is placed in sorted position: As mentioned in point 2, we are decreasing the count as the last element of the iteration is sorted and in next iteration we can ignore that last element.

Advantages

  1. Simplest form of all sorting, easy to understand
  2. No additional memory required.

Disadvantages

  1. Bit Expensive. Average and Worst case complexity is O(n2).

In the next articles, we will be discussing another interesting sorting algorithm techniques like Merge sort.

Want to improve this article / contribute new articles ? Reach us at – http://13.126.215.213.xip.io/test/write-an-article/

 

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.

LATEST POSTS

House Robber Problem | Maximum Sum of non-adjacent elements

In this blog post, we will discuss about how to find maximum sum of Non-Adjacent elements. Since House Robber Problem is a typical DP Problem...
00:11:41

Check Array Formation Through Concatenation | Leetcode Problem 1640

In this video, we will explain Check Array Formation Through Concatenation, Leetcode's 1640th problem in 2 different approaches along with a coding solution. Problem statement You are given...

Binary Tree Traversals in Kotlin – PreOrder, InOrder and PostOrder Traversals

Binary Tree Traversals are most common Tree Problems in an Interview as well as Competitive Programming. They can be efficient while searching, inserting and deleting...

Next Greater node in a Linked List – Leetcode Problem #1019

In this article, we will discuss the solution for 1019th Problem from Leetcode - Next Greater Node In Linked List. Let us see the question in...

Follow us

1,358FansLike
10FollowersFollow
400SubscribersSubscribe

Most Popular