CODEWITHSUNDEEP
sortingkotlinquicksortsoftware-design
Patrick
Patrick

Reputation: 184

Kotlin: Sorting | Location of swap operation

I'm implementing the Quicksort algorithm in Kotlin. For that, I created an interface, ISort, with a type parameter and a single function, sort. For sorting, I need the swap operation. I was wondering what the best location of this swap function is. My ideas:

1) Unfortunately, in Kotlin one cannot make interface function protected. Thus, every class could see the swap in its implementations and that's not too nice (although it's not too bad either, I agree).

2) Putting it in the QuickSort implementation is even worse because there might be several implementations of the ISort interface that need a swap function.

3) My next thought was to create a singleton object but Kotlin permits objects with type parameters.

Here is the interface definition:

interface ISort<T> {
  fun sort(toSort: MutableList<T>): MutableList<T>
  // 1) Putting swap here has a too high visibility
}

And here is the skeleton of the QuickSort class:

class QuickSort<T> : ISort<T> {
  override fun sort(toSort: MutableList<T>): MutableList<T> {
    doQuickSort(toSort) // Internally uses swap
    return toSort
  }
  // 2) Putting swap here might lead to code duplication of swap
}

So, from a software engineering perspective what would be the best place / location for the swap operation.

Upvotes: 1

Views: 367

Answers (1)

Naetmul
Naetmul

Reputation: 15572

Top level functions

In a file sort.kt or so,

package abc.def.sort


fun <T> quicksort(list: MutableList<T>): MutableList<T> {
    ...
}

// invisible in other files, but visibie in "sort.kt"
private fun <T> swap(...) {
    ...
}

To use the swap function in other sorts, you will need to define other sort functions in the same file. (Or copy the swap function many times.)

This is recommended for very simple functions.

Object as a namespace

This is similar to the method above, but more OOP-ish than the previous one.

object QuickSort {
    fun <T> sort(list: MutableList<T>): MutableList<T> {
        ...
    }

    private fun <T> swap(...) {
        ...
    }
}

or

object Sorts {
    fun <T> quicksort(list: MutableList<T>): MutableList<T> {
        ...
    }

    // add other sort methods...

    private fun <T> swap(...) {
        ...
    }
}

However, this is not recommended in Kotlin (Best practices for top-level declarations).

Combination of abstract class and object

The swap function can be reused for other sorts in this way.

abstract class Sort {
    abstract fun <T> sort(list: MutableList<T>): MutableList<T>

    protected fun <T> swap(...) {
        ...
    }
}

object QuickSort : Sort() {
    override fun <T> sort(list: MutableList<T>): MutableList<T> {
        ...
    }
}

I think [making the type parameter T be a class type parameter, not a function type parameter] will make the problem unnecessarily more complex because you will have to create a class instance for each time you use different type T.

Upvotes: 1

Related Questions