연결 리스트의 퀵정렬 (Quick sort on Singly Linked List)

연결 리스트에서의 퀵정렬 역시 배열에서의 퀵정렬과 동일한 방식으로, 주어진 데이터를 두 개로 partition하고 각각의 영역을 다시 퀵정렬한 후에 연결을 하는 방법으로 구현한다.

연결 리스트를 partition하는 것과 정렬된 sub linked list를 하나의 연결 리스트로 합치는 과정만 조금 다르다.

func QuickSort(root *Node) *Node {

    if root == nil {

        return nil

    }

    small, pivot, large := partition2(root)

    small = QuickSort(small)

    large = QuickSort(large)

    pivot.Next = large

    var newRoot *Node

    if small == nil {

        newRoot = pivot

    } else {

        newRoot = small

        lastSmall := getLast(small)

        lastSmall.Next = pivot

    }

    return newRoot

}

func partition(root *Node) (*Node, *Node, *Node) {

    var small, large *Node

    node := root.Next

    for node != nil {

        next := node.Next

        if node.Val < root.Val {

            node.Next = small

            small = node

        } else {

            node.Next = large

            large = node

        }

        node = next

    }

    root.Next = nil

    return small, root, large

}