Quick Sort on Linked List

by

Implementing quicksort on a linked list is a bit tricky as compared to an array because we can’t easily access elements by index. In quicksort, we need to partition the list into two sub-lists around a pivot element and then recursively sort those sub-lists.

Here’s how we can implement quicksort on a linked list:

  1. Define a Node class to represent a node in the linked list. Each node should have a data property to store its value, and a next property to point to the next node in the list.
  2. Define a quickSort function that takes the head of the linked list as an argument and returns the sorted linked list.
  3. In the quickSort function, check if the linked list is empty or has only one element, in which case it is already sorted and can be returned as is.
  4. Otherwise, select a pivot element from the list. For simplicity, we can choose the first element as the pivot.
  5. Traverse the list and partition it into two sub-lists: one with elements smaller than the pivot and the other with elements greater than or equal to the pivot.
  6. Recursively call the quickSort function on the two sub-lists to sort them.
  7. Concatenate the sorted sub-lists with the pivot element to form the final sorted linked list.
Kotlin
class Node(var data: Int, var next: Node? = null)

fun quickSort(head: Node?): Node? {
    if (head == null || head.next == null) {
        return head
    }

    // Select the first element as the pivot
    var pivot = head
    var current = head.next
    head.next = null

    // Partition the list around the pivot
    var smaller: Node? = null
    var smallerTail: Node? = null
    var greater: Node? = null
    var greaterTail: Node? = null

    while (current != null) {
        val nextNode = current.next
        current.next = null

        if (current.data < pivot.data) {
            if (smaller == null) {
                smaller = current
                smallerTail = current
            } else {
                smallerTail?.next = current
                smallerTail = current
            }
        } else {
            if (greater == null) {
                greater = current
                greaterTail = current
            } else {
                greaterTail?.next = current
                greaterTail = current
            }
        }

        current = nextNode
    }

    // Recursively sort the smaller and greater sub-lists
    smaller = quickSort(smaller)
    greater = quickSort(greater)

    // Concatenate the sorted sub-lists with the pivot element
    if (smaller == null) {
        return pivot
    } else {
        var sortedList = smaller
        while (smallerTail?.next != null) {
            smallerTail = smallerTail.next
        }
        smallerTail?.next = pivot
        pivot.next = greater
        return sortedList
    }
}
fun main() {
    // Create an unsorted linked list
    val node5 = Node(5)
    val node2 = Node(2)
    val node4 = Node(4)
    val node1 = Node(1)
    val node3 = Node(3)

    node5.next = node2
    node2.next = node4
    node4.next = node1
    node1.next = node3

    // Sort the linked list using quicksort
    val sortedList = quickSort(node5)

    // Print the sorted list
    var current = sortedList
    while (current != null) {
        print("${current.data} ")
        current = current.next
    }
}

In the main function I provided, we create an unsorted linked list with 5 nodes as follows: 5 -> 2 -> 4 -> 1 -> 3

Each node in the linked list has an integer value stored in its data field, as well as a reference to the next node in the list stored in its next field.

We then pass the head of the unsorted linked list (in this case, node5) to the quickSort function. The quickSort function uses the quicksort algorithm to sort the linked list in ascending order, and returns the head of the sorted list.

Finally, we iterate through the sorted linked list starting from the head (sortedList) and print out each node’s integer value. The output of the program should be: 1 2 3 4 5

Leave a Comment