Quick Sort in Kotlin

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 the 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 as 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 the 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.

Stack in Kotlin

How Quick sort works in Kotlin :

quick-sort-kotlin-algorithm

  • 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 the left side and one form right side. First, it will start the search from the left side for a greater element than pivot then we will stop incrementing left index. Or else we will increment that left index.
  • Step 3: From the right side, we will search for lesser element than the 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 the left side and elements that are greater than pivot should come to the right side. Now we have greater element present at the 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 the left index and the right index cross each other means right index should be lesser than the 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 the 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 the right side pivot is one array. It is the 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.

Queue in Kotlin

How below Quick Sort works for List :

    • 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
}
    • Choose the pivot element from the array, you can choose any element or any logic to find pivot. Here I am finding a pivot using (length of the list)/2 i.e middle element in the list
val pivot = items[items.count()/2]
    • Now we can use filter lambda to get all the elements which are equal to the pivot element. This lambda accepts a condition and returns a list of elements which satisfy the condition
val equal = items.filter { it == pivot }
    • Use the filter lambda from kotlin list to filter elements which are lesser than the pivot and store it in a list called lesser
val less = items.filter { it < pivot }
    • Again use the filter lambda to filter elements which are greater than the pivot element.
val greater = items.filter { it > pivot }
    • Now again call the function recursively to perform operation, but this time pass the splitted arrays. Do the same process again and again, till we left with multiple arrays with a single element and arranged in order
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)
}

The 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]

Merge sort in Kotlin

Credits:

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
}

Gnome Sort in kotlin

Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions