I'm trying to Sort a list of Items using a recursive Quicksort, while testing i noticed that repeated use of the Method makes the size of my list double which is not intended.

    /*list is filled with four Items:
    item test = new item(234, 44.2, "wardrobe", "Example Wardrobe");
    item test1 = new item(432, 87.2, "Chair", "Example Table");
    item test2 = new item(007, 600.666, "Table", "Example Table");
    item test3 = new item(02,5.4,"Jar","Example Jar");*/

    dlinkedList dList=Operations.fillList(); 
    dlinkedList list = dlinkedList.quicksortPrice(dList);
    dlinkedList.printAllElements(list);
    System.out.println(" sorted once ");
    list = dlinkedList.quicksortPrice(dList);
    dlinkedList.printAllElements(list);
    System.out.println(" sorted twice ");

Expected Output:

| Name: Jar| Price: 5.4| Category: Example Jar
| Name: wardrobe| Price: 44.2| Category: Example Wardrobe
| Name: Chair| Price: 87.2| Category: Example Table
| Name: Table| Price: 600.666| Category: Example Table
sorted once

| Name: Jar| Price: 5.4| Category: Example Jar
| Name: wardrobe| Price: 44.2| Category: Example Wardrobe
| Name: Chair| Price: 87.2| Category: Example Table
| Name: Table| Price: 600.666| Category: Example Table
sorted twice

Actual Output:

| Name: Jar| Price: 5.4| Category: Example Jar
| Name: wardrobe| Price: 44.2| Category: Example Wardrobe
| Name: Chair| Price: 87.2| Category: Example Table
| Name: Table| Price: 600.666| Category: Example Table
sorted once

| Name: Jar| Price: 5.4| Category: Example Jar
| Name: wardrobe| Price: 44.2| Category: Example Wardrobe
| Name: Chair| Price: 87.2| Category: Example Table
| Name: Table| Price: 600.666| Category: Example Table
| Name: wardrobe| Price: 44.2| Category: Example Wardrobe
| Name: Chair| Price: 87.2| Category: Example Table
| Name: Table| Price: 600.666| Category: Example Table sorted twice

    static dlinkedList sortedList = new dlinkedList();
    public static dlinkedList quicksortPrice(dlinkedList list) {
        dlinkedList smaller = new dlinkedList();
        dlinkedList greater = new dlinkedList();
        Node y = list.head;
        pivot = list.tail;
            if (pivot == null) {
                return sortedList;
            } else {
                if (numberOfElements(sortedList) == 0){
                    sortedList.addAtEndOfList(pivot.data);
                }
                while (y.next != null) {
                    if (y.data.price < pivot.data.price) {
                        smaller.addAtEndOfList(y.data);
                        y = y.next;
                    } else if (y.data.price > pivot.data.price) {
                        greater.addAtEndOfList(y.data);
                        y = y.next;
                    } else {
                        sortedList.insertAfterNode(sortedList.tail, y.data, sortedList);
                        y = y.next;
                    }
                }
                if(numberOfElements(greater) == 0){
                }else{
                    sortedList.insertAfterNode(sortedList.searchByPrice(pivot.data.price),   greater.tail.data,sortedList);
                }
                if (numberOfElements(smaller) == 0) {
                }else{
                  sortedList.insertBeforeNode(sortedList.searchByPrice(pivot.data.price),smaller.tail.data,sortedList  );
                }
                if(numberOfElements(smaller) == 0 && numberOfElements(greater) == 0){
                return sortedList;
                }else{
                    quicksortPrice(smaller);
                    quicksortPrice(greater);}
            }
        return sortedList;
    }

I've narrowed my problem down to the static list I use to store the sorted Items between the recursive Iterations, but sadly I don't know how to solve the Problem. I've tried to clear the list between every sort but that empties the whole list for some reason... Any Help would be much appreciated.

CodePudding user response：

Okay so I've solved it, the Doublylinked List sortedList was static and kept all the results from the throughout every Iteration which led to the List getting bigger. The Solution to clear the List by designating all the Nodes to null did not work because that also cleared the origin of the Pointers, so the Original List also became a null list.

After every sort I assign a null list to the variable sortedList, maybe not the most elegant Solution because I now have a null list in my code for only this purpose, but it works...

dlinkedList empty = new dlinkedList();
dlinkedList sortedList = sortMenuSwitch(mainMenuInput());
dlinkedList.sortedList = empty;