Selection Sort in Kotlin

Selection sort is one of the simplest sorting algorithms. It is similar to the hand picking where we take the smallest element and put it in the first position and the second smallest at the second position and so on.

We first check for smallest element in the array and swap it with the first element of the array. Again, we check for the smallest number in a subarray excluding the first element of the array as it is where it should be (at the first position) and put it in the second position of the array.

We continue repeating this process until the array gets sorted.

The time complexity of selection sort is (O(n2)).

We can perfom teh selection sort in two ways:

  • Using Smallest element in the array
  • Using Largest element in the array


Steps to perform selection sort in Kotlin using Smallest Element:

  • Start from the first element in the array and search for the smallest element in the array.
  • Swap the first element with the smallest element of the array.
  • Take a subarray (excluding the first element of the array as it is at its place) and search for the smallest number in the subarray (second smallest number of the entire array) and swap it with the first element of the array (second element of the entire array).
  • Repeat the steps 2 and 3 with new subarrays until the array gets sorted.

Insertion Sort

Lets Understrand the code of Selection sort in Kotlin :

  • First get the size of the array into a variable, we will be using this variable few times in our code. Also create a temp variable for swapping the values when e find the smaller elements
  • 
    var n=sampleArray.size
    var temp:Int
    

  • Loop all the elements present in the array using index like from 0 to size-1, from the first element to the last element.
  • 
    for(i in 0..n-1){
    

  • For moment sake we will consider the current element from the upper loop is the smallest element, and assign this value's index to indexOfMin
  • 
    var indexOfMin = i
    

  • Create another loop, Using this loop we will be comparing the Element at current index (the value from the upper loop i) with other elements present in the array.

    We will be comparing the Current element with element present in the last index, if the last index is smaller than current index then we assign the smaller element's index to indexOfMin This process goes on till we fnd the smallest item.
  • 
    for(j in n-1 downTo  i){
    	if(sampleArray[j]< sampleArray[indexOfMin])
    		indexOfMin=j
    }
    

  • We will swap the element only when the current element's index is different than indexOfMin
  • 
    if(i!=indexOfMin){
    	temp = sampleArray[i]
    	sampleArray[i]= sampleArray[indexOfMin]
    	sampleArray[indexOfMin]=temp
    }
    

Merge Sort Complete code for Selection sort in Kotlin usig smallest element


fun selection_sort(sampleArray:IntArray){
    var n=sampleArray.size
    var temp:Int
    for(i in 0..n-1){
        var indexOfMin = i
        for(j in n-1 downTo  i){
            if(sampleArray[j]< sampleArray[indexOfMin])
                indexOfMin=j
        }
        if(i!=indexOfMin){
            temp = sampleArray[i]
            sampleArray[i]= sampleArray[indexOfMin]
            sampleArray[indexOfMin]=temp
        }
    }
}

fun main(arg: Array<String>) {
    println("Before Sort")
    var A = intArrayOf(1, 7, 3, 9, 4)
    for (i in A) print(i)

    selection_sort(A)

    println("\nSorted array is : ")
    for (i in A) print(i)
}		

Selection Sort Using Largest Element with Kotlin

Steps to perform selection sort in Kotlin using largest Element:

  • Start from the last element in the array and search for the largest element in the array.
  • Swap the last element with the largest element of the array.
  • Take a subarray (excluding the last element of the array as it is at its place) and search for the largest number in the subarray (second largest number of the array (last element excluded)) and swap it with the last element of the array (second last element of the entire array).
  • Repeat the steps 2 and 3 with new subarrays until the array gets sorted.

Quicksort The change in the code will be, we are going to itearte from the last and swap the largest element to the last.


fun selection_sort(sampleArray:IntArray){
    var n=sampleArray.size
    var temp:Int
    for(i in n-1 downTo  0){
        var max = i
        for(j in 0 until i){
            if(sampleArray[j]>sampleArray[max])
                max=j
        }
        if(i!=max){
            temp =sampleArray[i]
            sampleArray[i]=sampleArray[max]
            sampleArray[max]=temp
        }
    }
}

fun main(arg: Array<String>) {
    println("Before Sort")
    var A = intArrayOf(1, 7, 3, 9, 4)
    for (i in A) print(i)

    selection_sort(A)

    println("\nSorted array is : ")
    for (i in A) print(i)
}		

Cocktail Sort

Selection Sort in Kotlin With List

Steps to perform selection sort in Kotlin with respect to list:

  • Before sorting, just make sure you got enought elements to sort. Minimum two elements are required to sort. If you less than two element then no need to sort them as they are already sorted
  • 
    if (items.isEmpty() || items.size<2){
    	return items
    }	
    

  • Iterate the list based on the index, from 0 to list size-1.
  • 
    for (idx in 0..items.count()){
    

  • Create sub list, by excluding list- starting index, The starting index gets incremented by 1 for every iteration.

    On each iteration get the minimum element using min() function from the sub list

    Find the index of the minimum value
  • 
    val smallList = items.subList(0,items.count()-idx)
    val minItem = array.min()
    val indexOfMinItem = array.indexOf(minItem)
    

  • Now remove the minimum value from the list if it is not null, then add the same minimum value to the list.

    Now the smaller element is at the end of the list at end of first iteration, so similar to this on second iteration second small eleemnt will be at the end of list.

    On the end of all iteration the largest element will be at the last index.
  • 
    if (minItem != null) {
    	items.removeAt(indexOfMinItem)
    	items.add(minItem)
    }
    


Complete code for selection sort in Kotlin with Lists


fun selectionsort(items:MutableList<Int>):MutableList<Int>{
    if (items.isEmpty() || items.size<2){
        return items
    }
    for (idx in 0..items.count()){
        val array = items.subList(0,items.count()-idx)
        val minItem = array.min()
        val indexOfMinItem = array.indexOf(minItem)
        if (minItem != null) {
            items.removeAt(indexOfMinItem)
            items.add(minItem)
        }
    }
    return items
}
fun main(args: Array<String>) {
    println("Selection Sort")
    val names = mutableListOf(1, 7, 3, 9, 4)
    println(names)
    var ordered = insertionsort(names)
    println(ordered)
}			

Shell 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