Quick Sort on a Doubly Linked List (Python)

Question

I have been trying to figure out and understand how to quick sort on a doubly linked list in python. I have a good understanding of how the quick sort is supposed to work however I have not been able to solve this problem. I have tried reading and implementing many versions online but it seems that even some of the code snippets online are not 100% correct. For example, I pulled code from an online source that, yes indeed performed a quick sort on the numbers they inputted. However this was not the case with a totally random set of numbers. I want a program that will run for any set of numbers, not just some. With all that being said here is my code that sometimes works but not for all sets of numbers. Any help would be greatly appreciated!

# A python program to sort a linked list using Quicksort

# A class that will function as a linked list
class LL_numbers:
    def __init__(self):
        self.head = None
        self.tail = None
    
    # Function that will insert a new node to the end of the linked list
    def push(self, new_data):
        new_node = Node(new_data)

        # If the head is empty fill the head and tail with the new node
        if(self.head == None):
            self.head = new_node
            self.tail = new_node
            return
        
        # If the head is not empty, find the last element (tail) and add an element to the tail
        self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node

    def print_list(self):
        current = self.head
        while(current):
            print(current.data, end=", ")
            current = current.next


    def partition(self,left,right):
        i = left.prev
        pivot = right
        j = left

        while(j != right):

            if j.data <= pivot.data:

                # Increment i
                if i == None:
                    i = left
                else:
                    i = i.next
                    i.data, j.data = j.data, i.data
            j = j.next
        # increment i
        if i == None:
            i = left
        else:
            i = i.next
        i.data, right.data = right.data, i.data
        return i
            

    def quickSort(self,left,right):
        if(right != None and left != right and left != right.next):
            p = self.partition(left,right)
            self.quickSort(left, p.prev)
            self.quickSort(p.next,right)


# A node of the doubly linked list
class Node:
    def __init__(self,d):
        self.data = d
        self.next = None
        self.prev = None
  
def main():

    linked_numbers = LL_numbers()

    # 5, 3, 2, 4, 3, 9, 0, 6, 1, 10,
    # for n in range(10):
    #     rand_val = random.randint(0,10)
    #     linked_numbers.push(rand_val)
    linked_numbers.push(5)
    linked_numbers.push(3)
    linked_numbers.push(2)
    linked_numbers.push(4)
    linked_numbers.push(3)
    linked_numbers.push(9)
    linked_numbers.push(0)
    linked_numbers.push(6)
    linked_numbers.push(1)
    linked_numbers.push(10)
    
    

    

    print("Before Quick Sorting:\n")
    linked_numbers.print_list()

    print("\nAfter Quick Sorting:\n")
    print(linked_numbers.tail.data)
    linked_numbers.quickSort(linked_numbers.head, linked_numbers.tail)
    linked_numbers.print_list()

if __name__ == "__main__":
    main()

Output:

Before Quick Sorting:

5, 3, 2, 4, 3, 9, 0, 6, 1, 10,
After Quick Sorting:

10
5, 1, 0, 2, 3, 3, 4, 6, 9, 10,

Answer 1

The problem is in partition in the body of the loop:

                if i == None:
                    i = left
                else:
                    i = i.next
                    i.data, j.data = j.data, i.data

The swap should also happen in the if case, so it should be moved out of the else block:

                if i == None:
                    i = left
                else:
                    i = i.next
                i.data, j.data = j.data, i.data