My quick Sort Function in Kotlin give the wrong output back

Question

I tried to make a quick sort function for a linked list, which can sort objects based on a given variable. But I have the problem that the outpout of the quick sort function is neither sorted nor unchanged. Instead it is completly diffrent.

I've tried to change the addfirst function and I tried to change the connect function, but it doesn't do anything.

So for Example here the console Out put of the list I wanted to sort: (Translation:"Sein name ist": "His name his") :

Sein Name ist: Haarald(Alter: 3)
Sein Name ist: Mark(Alter: 2)
Sein Name ist: Guenter(Alter: 1)
Sein Name ist: Kai(Alter: 4)

And now the console output of the list after I gave it in the quick sort Function:

Sein Name ist: Haarald(Alter: 3)
Sein Name ist: Mark(Alter: 2)
Sein Name ist: Guenter(Alter: 1)
Sein Name ist: Kai(Alter: 4)
Sein Name ist: Haarald(Alter: 3)
Sein Name ist: Guenter(Alter: 1)
Sein Name ist: Mark(Alter: 2)
Sein Name ist: Guenter(Alter: 1)

So it's strange that the output is more than the input.

And here the function`s that I used:

Quick sort function:

fun quickSort(comparator: Comparator<T>){
        if (this.size() < 2)return;

        val pivot = this.getFirst().content;     //Vergleichs Element

        val less = Liste<T>();
        val equal= Liste<T>();
        val more = Liste<T>();

        for (element in this){
            val compared = comparator.compare(pivot,element)
            when{
                compared >  0 -> less.addfirst(element);
                compared == 0 -> equal.addfirst(element);
                compared <  0 -> more.addfirst(element);
            }
        }
        less.quickSort(comparator)
        more.quickSort(comparator)

        this.first = conect(this,conect(equal,less)).first
    }

comperator:

val intComperator = Comparator<Mensch>{o1: Mensch, o2:Mensch -> when{

          o1.alter == o2.alter -> 0
          o1.alter < o2.alter -> -1
          o1.alter > o2.alter -> 1
          else -> 0
          }
           }

Helper Functions: fun getFirst():Eintrag{ return first?: throw Exception("(getFirst)No Elements in this List")}

fun conect(mainList:Liste<T>,toAdd:Liste<T>):Liste<T> {
        mainList.getLast().next = toAdd.first;
        return mainList
    }

and the last code, the implementation of the list:

class Liste<T>:Iterable<T>{
   
    class Eintrag<T>(val content:T, var next:Eintrag<T>?)

    private var first :Eintrag<T>? = null;

And here is the full code, I'm sorry, I know it's messy and I need to break the code into more than one file and something about my formatting too: https://github.com/TheDarkRiddle/Kotlin-quick-sort

Answer 1

If your class would implement the Comparable interface docs here and example here instead of having it as a separate value, you could use a simple quick sort implementation like this.

fun <E : Comparable<E>> List<E>.quickSort(): List<E> =
    when {
        size < 2 -> this
        else -> {
            val (l, h) = subList(1, size).partition { it < first() }
            l.quickSort() + first() + h.quickSort()
        }
    }

Alternatively, you could modify this to use your comparator val, but honestly I find this to be a bit harder to understand, and will only work for objects of type Mensch.

fun List<Mensch>.quickSort(comparator: Comparator<Mensch>): List<Mensch> =
    when {
        size < 2 -> this
        else -> {
            val (l, h) = subList(1, size).partition { intComperator.compare(it, first()) == -1 }
            l.quickSort(comparator) + first() + h.quickSort(comparator)
        }
    }

I haven't included the Liste class here in any way, since when you are debugging something, it is best to reduce the code as much as possible (that is why it is also a advice on SO to create the minimal reproducible example), and then start adding to it, then you can easily detect if your comparator is off, or if your classes are off or etc.