Different Sorting Algorithms Part 2 • 9 min read

Custom LinkedList with Sorting

In this example, I extend the functionality of a LinkedList to include sorting algorithms such as Quick Sort and Bogo Sort. We also implement the Comparable interface for elements so that they can be sorted based on their natural ordering.

This is the definition of the Node class. Each node in the LinkedList contains data and a reference to the next node.

class Node<T> {
    T data;
    Node<T> next;

    Node(T data) {
        this.data = data;
        this.next = null;
    }
}

This is the definition of the LinkedList class. It maintains a reference to the head of the list and provides methods to insert elements and display the list.

class LinkedList<T extends Comparable<T>> {
    private Node<T> head;

    public LinkedList() {
        head = null;
    }

    public void insert(T data) {
        Node<T> newNode = new Node<>(data);
        if (head == null) {
            head = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
    }

    public void display() {
        Node<T> current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

Quick Sort Implementation

This is the implementation of the Quick Sort in the LinkedList class. Quick Sort is a divide-and-conquer sorting algorithm that partitions the list around a pivot element.

    // Implementing Quick Sort
    public void quickSort() {
        head = quickSort(head);
    }

    private Node<T> quickSort(Node<T> head) {
        if (head == null || head.next == null) {
            return head;
        }
        // Selecting pivot
        Node<T> pivot = head;
        Node<T> lessHead = null;
        Node<T> greaterHead = null;
        Node<T> equalHead = head;
        Node<T> current = head.next;
        // Partitioning
        while (current != null) {
            Node<T> next = current.next;
            if (current.data.compareTo(pivot.data) < 0) {
                current.next = lessHead;
                lessHead = current;
            } else if (current.data.compareTo(pivot.data) > 0) {
                current.next = greaterHead;
                greaterHead = current;
            } else {
                current.next = equalHead;
                equalHead = current;
            }
            current = next;
        }
        // Recursively sorting sublists
        if (lessHead != null) {
            lessHead = quickSort(lessHead);
        }
        if (greaterHead != null) {
            greaterHead = quickSort(greaterHead);
        }
        // Combining sorted sublists
        Node<T> sorted = null;
        if (lessHead != null) {
            sorted = lessHead;
            while (lessHead.next != null) {
                lessHead = lessHead.next;
            }
            lessHead.next = equalHead;
        } else {
            sorted = equalHead;
        }
        while (equalHead.next != null) {
            equalHead = equalHead.next;
        }
        equalHead.next = greaterHead;
        return sorted;
    }

Bogo Sort Implementation

This is the implementation of Bogo Sort in the LinkedList class. Bogo Sort is a highly inefficient sorting algorithm that randomly shuffles the list until it’s sorted.

    // Implementing Bogo Sort
    public void bogoSort() {
        while (!isSorted()) {
            shuffle();
        }
    }

    private boolean isSorted() {
        Node<T> current = head;
        while (current != null && current.next != null) {
            if (current.data.compareTo(current.next.data) > 0) {
                return false;
            }
            current = current.next;
        }
        return true;
    }

    private void shuffle() {
        Random rand = new Random();
        Node<T> current = head;
        int length = 0;
        while (current != null) {
            length++;
            current = current.next;
        }
        T[] arr = (T[]) new Comparable[length];
        current = head;
        int i = 0;
        while (current != null) {
            arr[i++] = current.data;
            current = current.next;
        }
        // Fisher-Yates shuffle algorithm
        for (int j = arr.length - 1; j > 0; j--) {
            int index = rand.nextInt(j + 1);
            T temp = arr[index];
            arr[index] = arr[j];
            arr[j] = temp;
        }
        // Reassigning shuffled data to the list
        current = head;
        i = 0;
        while (current != null) {
            current.data = arr[i++];
            current = current.next;
        }
    }
}