Quick Sort in Kotlin is one of the fastest algorithms with average time complexity O(nlogn).

Quick Sort is popular because it is faster and also space efficient. But in worst case it is `O(n^2)`

then also it is better than other sorting algorithms which exhibit `O(n^2)`

time complexity.

Quick Sort works on __divide and conquer paradigm__. It chooses an element known a pivot and ensures that it gets placed at its right position in the list that is being sorted and then the process is repeated with the sub list on left of the pivot and on right of the pivot, till the **list** is sorted.

The process of **placing the pivot element in its final position is called as the partitioning**. You can choose any element as the pivot element and partition the array based on it.

**Step 1:**it will choose an element as pivot element. There are many ways to select the pivot element. We can take**first element as pivot element or last element, randomized element, middle element, etc.****Step 2:**Quick sort will maintain two indexes, one from left side and one form right side. First it will start search from left side for greater element than pivot then we will stop incrementing left index. Or else we will increment that left index.**Step 3:**From right side we will search for lesser element than pivot. If we found lesser element than pivot then we will stop decrementing right index or else we will decrement right index.**Step 4:**we should exchange elements so that all elements which are lesser than pivot should come to left side and elements that are greater than pivot should come to right side. Now we have greater element present at left side at left index and lesser element present at the right index. If we swap these 2 elements then they are at correct positions according to pivot.**Step 5:**Again continue the same procedure until left index and right index cross each other means right index should be lesser than left index. Means all elements were placed right now right index position will be the pivot position. Pivot and the element present at right index should be swapped.**Step 6:**Now**array**is dived into 2 parts. Elements which are present in the left side of pivot are one sub array and elements which are present at right side pivot is one array. It is division part. Recursively apply above procedure on sub arrays.**Step 7:**the base condition for quick sort is same as merge sort. It will divide until sub array length is 1.

- First an formost, check the size of the list, if there is only one element then no need to sort.

```
if (items.count() < 2){
return items
}
```

```
val pivot = items[items.count()/2]
```

`filter`

```
val equal = items.filter { it == pivot }
```

`filter`

lambda from kotlin list to filter elements whoch are lesser than the pivot and store it in a list called lesser```
val less = items.filter { it < pivot }
```

```
val greater = items.filter { it > pivot }
```

```
return quicksort(less) + equal + quicksort(greater)
```

Complete program for quick sort in kotlin

```
fun quicksort(items:List<Int>):List<Int>{
if (items.count() < 2){
return items
}
val pivot = items[items.count()/2]
val equal = items.filter { it == pivot }
// println("pivot value is : "+equal)
val less = items.filter { it < pivot }
// println("Lesser values than pivot : "+less)
val greater = items.filter { it > pivot }
// println("Greater values than pivot : "+greater)
return quicksort(less) + equal + quicksort(greater)
}
fun main(args: Array<String>) {
println("\nOriginal list:")
val numbers = listOf<Int>(2, 4, 7, 3, 6, 9, 5, 1, 0)
println(numbers)
println("\nOrdered list:")
val ordered = quicksort(numbers)
println(ordered)
}
```

Output of QuickSort with Kotlin

```
Original list:
[2, 4, 7, 3, 6, 9, 5, 1, 0]
Ordered list:
[0, 1, 2, 3, 4, 5, 6, 7, 9]
```

```
Original list:
[2, 4, 7, 3, 6, 9, 5, 1, 0]
Ordered list:
[0, 1, 2, 3, 4, 5, 6, 7, 9]
```

*Image Credit: codenuclear*

Quick Sort of Arrays in Kotlin

```
fun main(args: Array<String>) {
val array = IntArray(2, 4, 7, 3, 6, 9, 5, 1, 0)
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
}
```

You can attend first 3 classes for free, the total

The course time would be 8.00 PM(IST) for the first three classes

If you are interested to learn, then you can join the course by sending email to

| |||||