package com.thealgorithms.datastructures.lists;
/*
 *
 * @aurthor - Prabhat-Kumar-42
 * @github - https://github.com/Prabhat-Kumar-42
 *
 * Problem :
 *    QuickSort on Linked List
 *
 * Note: Taking head as pivot in current implementation.
 *        N represents NULL node
 *    Example:
 *
 *      -> Given Linked List :
 *            5 -> 3 -> 8 -> 1 -> 10 -> 2 -> 7 -> 4 -> 9 -> 6
 *
 *      -> How Sorting will work according to the QuickSort Algo written below
 *
 *      current pivot : 5
 *      List lessThanPivot : 3 -> 1 -> 2 -> 4
 *      List greaterThanPivot : 5 -> 8 -> 10 -> 7 -> 9 -> 6
 *
 *      -> reccur for lessThanPivot and greaterThanPivot
 *
 *            lessThanPivot :
 *                current pivot : 3
 *                lessThanPivot : 1 -> 2
 *                greaterThanPivot : 4
 *
 *             greaterThanPivot:
 *                 current pivot : 5
 *                 lessThanPivot : null
 *                 greaterThanPivot : 8 -> 10 -> 7 -> 9 -> 6
 *
 *        By following the above pattern, reccuring tree will form like below :
 *
 *        List-> 5 -> 3 -> 8 -> 1 -> 10 -> 2 -> 7 -> 4 -> 9 -> 6
 *
 *        Pivot :                  5
 *                                /\
 *                               /  \
 *                              /    \
 *                             /      \
 *                            /        \
 *        List: (3 -> 1 -> 2 -> 4)   (5 -> 8 -> 10 -> 7 -> 9 -> 6)
 *        Pivot :          3               5
 *                        /\              /\
 *                       /  \            /  \
 *                      /    \          /    \
 *                     /      \        /      \
 *         List:   (1 -> 2)   (4)   (N)   (8 -> 10 -> 7 -> 9 -> 6)
 *         Pivot:     1        4                8
 *                   /\       /\               /\
 *                  /  \     /  \             /  \
 *                 /    \   /    \           /    \
 *         List:  (N)  (2) (N)   (N)   (6 -> 7)   (9 -> 10)
 *         Pivot:       2                  6         9
 *                     /\                 /\        /\
 *                    /  \               /  \      /  \
 *                   /    \             /    \    /    \
 *         List:   (N)   (N)          (N)   (7) (N)   (10)
 *         Pivot:                            7          10
 *                                          /\          /\
 *                                         /  \        /  \
 *                                        /    \      /    \
 *                                       (N)   (N)   (N)   (N)
 *
 *
 *      -> After this the tree will reccur back (or backtrack)
 *         and the returning list from left and right subtree will attach
 *         themselves around pivot.
 *         i.e. ,
 *                  (listFromLeftSubTree) -> (Pivot) -> (listFromRightSubtree)
 *
 *         This will continue until whole list is merged back
 *
 *          eg :
 *             Megring the above Tree back we get :
 *
 *          List: (1 -> 2)        (4)           (6 -> 7)         (9 -> 10)
 *                  \             /                  \             /
 *                   \           /                    \           /
 *                    \         /                      \         /
 *                     \       /                        \       /
 *                      \     /                          \     /
 *                       \   /                            \   /
 *                        \ /                              \ /
 *          Pivot:         3                                8
 *          List:   (1 -> 2 -> 3 -> 4)            (6 -> 7 -> 8 -> 9 -> 10)
 *                                  \              /
 *                                   \            /
 *                                    \          /
 *                                     \        /
 *                                      \      /
 *                                       \    /
 *                                        \  /
 *                                         \/
 *          Pivot:                          5
 *          List:      (1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10)
 *
 *
 *      -> This will result in a sorted Linked List
 */

public class QuickSortLinkedList {

    private final SinglyLinkedList list; // The linked list to be sorted
    private Node head; // Head of the list

    /**
     * Constructor that initializes the QuickSortLinkedList with a given linked list.
     *
     * @param list The singly linked list to be sorted
     */
    public QuickSortLinkedList(SinglyLinkedList list) {
        this.list = list;
        this.head = list.getHead();
    }

    /**
     * Sorts the linked list using the QuickSort algorithm.
     * The sorted list replaces the original list within the SinglyLinkedList instance.
     */
    public void sortList() {
        head = sortList(head);
        list.setHead(head);
    }

    /**
     * Recursively sorts a linked list by partitioning it around a pivot element.
     *
     * <p>Each recursive call selects a pivot, partitions the list into elements less
     * than the pivot and elements greater than or equal to the pivot, then combines
     * the sorted sublists around the pivot.</p>
     *
     * @param head The head node of the list to sort
     * @return The head node of the sorted linked list
     */
    private Node sortList(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node pivot = head;
        head = head.next;
        pivot.next = null;

        Node lessHead = new Node();
        Node lessTail = lessHead;
        Node greaterHead = new Node();
        Node greaterTail = greaterHead;

        while (head != null) {
            if (head.value < pivot.value) {
                lessTail.next = head;
                lessTail = lessTail.next;
            } else {
                greaterTail.next = head;
                greaterTail = greaterTail.next;
            }
            head = head.next;
        }

        lessTail.next = null;
        greaterTail.next = null;

        Node sortedLess = sortList(lessHead.next);
        Node sortedGreater = sortList(greaterHead.next);

        if (sortedLess == null) {
            pivot.next = sortedGreater;
            return pivot;
        } else {
            Node current = sortedLess;
            while (current.next != null) {
                current = current.next;
            }
            current.next = pivot;
            pivot.next = sortedGreater;
            return sortedLess;
        }
    }
}