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

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

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 (lenth 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 element which are equal to the pivot element. This lambda accepts a condition and returns a list of element which satisfy the condition
  • 
    val equal = items.filter { it == pivot }							
    

  • Use the 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 }							
    

  • Again use the filter lambda to filter elements which are greater than pivot element.
  • 
    val greater = items.filter { it > pivot }								
    

  • Now again call the function recursively to perform operation, but this time pass the splitted arrys. Do the same process again and again till, we left with multiple arrays with sigle 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)
}			

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

aaaaaaaaaaaaa
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

Recent Addition

new tutorial Selenium Online Training : Our next online training course for Selenium with Java starts from 17th December 2018.

You can attend first 3 classes for free, the total course fee is INR 10,000

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 chercher.tech@gmail.com

or Register below


 
Join My Facebook Group
Join Group