Strand Sort in Kotlin

Strand sort is a sorting algorithm. It works by repeatedly pulling sorted sublists out of the list to be sorted and merging them with a result array. Each iteration through the unsorted list pulls out a series of elements which were already sorted, and merges those series together.

The name of the algorithm comes from the "strands" of sorted data within the unsorted list which are removed one at a time. It is a comparison sort due to its use of comparisons when removing strands and when merging them into the sorted array.

The strand sort algorithm is O("n" log "n") in the average case. In the best case (a list which is already sorted) the algorithm is linear, or O("n").In the worst case (a list which is sorted in reverse order) the algorithm is O("n"2).

Strand sort is most useful for data which is stored in a linked list, due to the frequent insertions and removals of data. Using another data structure, such as an array, would greatly increase the running time and complexity of the algorithm due to lengthy insertions and deletions.

Strand sort is also useful for data which already has large amounts of sorted data, because such data can be removed in a single strand.

Cycle Sort Complete program of the Strand sort in kotlin


fun strandSort(l: List<Int>): List<Int> {
    fun merge(left: MutableList<Int>, right: MutableList<Int>): MutableList<Int> {
        val res = mutableListOf<Int>()
        while (!left.isEmpty() && !right.isEmpty()) {
            if (left[0] <= right[0]) {
                res.add(left[0])
                left.removeAt(0)
            }
            else {
                res.add(right[0])
                right.removeAt(0)
            }
        }
        res.addAll(left)
        res.addAll(right)
        return res
    }

    var list = l.toMutableList()
    var result = mutableListOf<Int>()
    while (!list.isEmpty()) {
        val sorted = mutableListOf(list[0])
        list.removeAt(0)
        val leftover = mutableListOf<Int>()
        for (item in list) {
            if (sorted.last() <= item)
                sorted.add(item)
            else
                leftover.add(item)
        }
        result = merge(sorted, result)
        list = leftover
    }
    return result
}

fun main(args: Array<String>) {
    val l = listOf(-2, 0, -2, 5, 5, 3, -1, -3, 5, 5, 0, 2, -4, 4, 2)
    println(strandSort(l))
}	

Output of the Strand sort in kotlin


[-4, -3, -2, -2, -1, 0, 0, 2, 2, 3, 4, 5, 5, 5, 5]	

Introsort 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