Selection Sort in Kotlin

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

We first check for the 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 the Smallest element in the array
  • Using the 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 an 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 the 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 the current index then we assign the smaller element's index to indexOfMin This process goes on until we find 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 sub-array (second largest number of the array (the 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 sub-arrays until the array gets sorted.

Quicksort

The change in the code will be, we are going to iterate 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 the list:

    • Before sorting, just make sure you got enough elements to sort. Minimum two elements are required to sort. If you less than two elements 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 sublist, 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 sublist

      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 the end of the first iteration, so similar to this on second iteration second small element will be at the end of the 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)
}


The 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

Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions