Cycle Sort in Kotlin | Data Structures

Cycle sort is a comparison sorting algorithm, which forces array to be factored into the number of cycles, where each of them can be rotated to produce a sorted array. It is theoretically optimal in the sense that it reduces the number of writes to the original array.

Unlike every other sort, items are never written elsewhere in the array simply to push them out of the way of the action.

Each value is either written zero times, if it's already in its correct position, or written one time to its correct position. This matches the minimal number of overwrites required for a completed in-place sort.

Patience Sort Kotlin program for Cycle sort


fun cycleSort(array: Array<Int>): Int {
    var writes = 0

    // Loop through the array to find cycles to rotate.
    for (cycleStart in 0 until array.size - 1) {
        var item = array[cycleStart]

        // Find where to put the item.
        var pos = cycleStart
        for (i in cycleStart + 1 until array.size){
            if (array[i] < item){
                pos++
            }
        }

        // If the item is already there, this is not a cycle.
        if (pos == cycleStart) continue

        // Otherwise, put the item there or right after any duplicates.
        while (item == array[pos]){
            pos++
        }
        val temp = array[pos]
        array[pos] = item
        item = temp
        writes++

        // Rotate the rest of the cycle.
        while (pos != cycleStart) {
            // Find where to put the item.
            pos = cycleStart
            for (i in cycleStart + 1 until array.size){
                if (array[i] < item) pos++
            }

            // Otherwise, put the item there or right after any duplicates.
            while (item == array[pos]){
                pos++
            }
            val temp2 = array[pos]
            array[pos] = item
            item = temp2
            writes++
        }
    }
    return writes
}

fun main(args: Array<String>) {
    val array = arrayOf(0, 1, 2, 2, 2, 2, 5, 8, 4, 7, 0, 6)
    println("Before sorting : ")
    for(a in array) print("$a  ")

    cycleSort(array)
    println("\n\nAfter sorting : ")
    for(a in array) print("$a  ")
}			


Output of the Cycle sort in Kotlin


Before sorting : 
0  1  2  2  2  2  5  8  4  7  0  6  

After sorting : 
0  0  1  2  2  2  2  4  5  6  7  8 			

Bogo 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