Sunday, June 23, 2024
HomeAlgorithmsQuick Sort Kotlin Implementation - Sorting Algorithms #4

Quick Sort Kotlin Implementation – Sorting Algorithms #4

-

Quick Sort is based on divide and conquer algorithmic technique, similar to Merge Sort. In this tutorial, we will be looking at  Quick Sort Kotlin Implementation.

How Quick Sort Works?

In Quick Sort, we will consider a random element of an array as pivot and partition the array into two – left part and right part. The main essence of Quick sort is as follows: If an element is considered to be sorted, then all the other elements which are left to it should be less than that element and all the right elements must be greater than it.

Related Links

To understand the above, let us take an example of [1, 2, 3, 4, 5]. Here, if we consider 3 as pivot, which is in sorted position, the elements left to it ([1, 2]) are less than 3 and the elements right to it (4, 5) are greater than 3. Hence we know that 3 is in sorted position.Now let us discuss on how Quick sort algorithm is written.

We will select a random element as pivot and partition the array such that elements less than pivot position will be on left and elements greater will be on right. Any greater element on left will be swapped with any less element on right. In this manner we will keep on partitioning the array into sub arrays and rearranging them.

Sometimes Theory can be confusing than Practice – Vamsi Tallapudi 🙂

Let us quickly dive into the algorithm for Quick Sort Kotlin Implementation

Algorithm For Quick Sort Kotlin Implementation


package main.dataStructures.sorting
fun main(args: Array<String>) {
val array = readLine()!!.split(" ").map { it.toInt() }.toIntArray() // 1) Read the input and split into array
quickSort(array, 0, array.size-1)
for(i in array) println(i)
}
fun quickSort(array: IntArray, left: Int, right: Int) {
val index = partition (array, left, right)
if(left < index-1) { // 2) Sorting left half
quickSort(array, left, index-1)
}
if(index < right) { // 3) Sorting right half
quickSort(array,index, right)
}
}
fun partition(array: IntArray, l: Int, r: Int): Int {
var left = l
var right = r
val pivot = array[(left + right)/2] // 4) Pivot Point
while (left <= right) {
while (array[left] < pivot) left++ // 5) Find the elements on left that should be on right
while (array[right] > pivot) right– // 6) Find the elements on right that should be on left
// 7) Swap elements, and move left and right indices
if (left <= right) {
swapArray(array, left,right)
left++
right–
}
}
return left
}
fun swapArray(a: IntArray, b: Int, c: Int) {
val temp = a[b]
a[b] = a[c]
a[c] = temp
}

view raw

QuickSort.kt

hosted with ❤ by GitHub

As usual, Let us briefly discuss the points which are commented and are worth mentioning from the above Quick Sort Kotlin algorithm.

  1. Read the Input and Split into array: Here we are trying to read the input whose values are separated by spaces (for eg., 5 4 3 2 1) and later split them into an array of integers.
  2. Sorting left half: Here we will be calling the quickSort() recursively on the left half so that it will be sorted.
  3. Sorting right half: Here we will be calling the quickSort() recursively on the right half so that it will be sorted.
  4. Pivot Point: Here we are calculating the pivot point. For simplicity and efficient time complexity, we are taking the average of low and high as pivot. In general, we can have any element of the array / sub array as pivot.
  5. Find the elements on left that should be on right: Here we are iterating through the left array till we find the element greater than pivot position.
  6. Find the elements on right that should be on left: Here we are iterating through the right array until we find the element less than the pivot position.
  7. Swap elements, and move left and right indices: At this point of code, if left < right, then we have found left and right positions that needs to be swapped. Then we will increment left and decrement right positions respectively so that we will be ready for next iteration.

Performance

Performance of Quick sort depends upon the factors like choice of pivot selection point etc. On an average case, Quick sort’s time complexity is O(nlogn) and in worst case it is O(n2).

In the upcoming articles we will be discussing about Searching Algorithms.

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

3 Sum | Leetcode #15 | 100 Days of Code Day 10

Today we are going to solve 3 Sum - our first Medium Level Array problem from Coderefer DSA Sheet. If you are new to this...

Best Time to Buy and Sell Stock – Day 7 | 100 Days of Code

Welcome to Day 7 of 100 Days of Code where today we solve yet another most frequently asked easy array problem called - Best Time...

Contains Duplicate – Day 8 | 100 Days of Code

Welcome to Day 8 of 100 Days of Code and today we are going to solve yet another easy-level problem - Contains Duplicate as part...

Two Sum – Day 6 | 100 Days of Code

Welcome to Day 6 of 100 Days of Code where we solve the most frequently asked Easy level Array problem - Two Sum. Let us...

Follow us

1,358FansLike
10FollowersFollow
397SubscribersSubscribe

Most Popular