Programa Java para QuickSort en una lista enlazada individualmente

QuickSort en la lista doblemente enlazada se analiza aquí . QuickSort en una lista enlazada individualmente se proporcionó como ejercicio. Las cosas importantes acerca de la implementación son que cambia los punteros en lugar de intercambiar datos y la complejidad del tiempo es la misma que la implementación de la lista doblemente enlazada. 

sorting image

En la partición() , consideramos el último elemento como pivote. Recorremos la lista actual y si un Node tiene un valor mayor que el pivote, lo movemos después de la cola. Si el Node tiene un valor menor, lo mantenemos en su posición actual. 

En QuickSortRecur() , primero llamamos a la partición() que coloca el pivote en la posición correcta y devuelve el pivote. Después de colocar el pivote en la posición correcta, encontramos el Node de cola del lado izquierdo (lista antes del pivote) y recurrimos a la lista izquierda. Finalmente, recurrimos a la lista derecha.

Java

// Java program for Quick Sort on
// Singly Linked List
 
// Sort a linked list using
// quick sort
public class QuickSortLinkedList
{
    static class Node
    {
        int data;
        Node next;
 
        Node(int d)
        {
            this.data = d;
            this.next = null;
        }
    }
 
    Node head;
 
    void addNode(int data)
    {
        if (head == null)
        {
            head = new Node(data);
            return;
        }
 
        Node curr = head;
        while (curr.next != null)
            curr = curr.next;
 
        Node newNode = new Node(data);
        curr.next = newNode;
    }
 
    void printList(Node n)
    {
        while (n != null)
        {
            System.out.print(n.data);
            System.out.print(" ");
            n = n.next;
        }
    }
 
    // Takes first and last node,
    // but do not break any links in
    // the whole linked list
    Node partitionLast(Node start,
                      Node end)
    {
        if (start == end ||
            start == null ||
            end == null)
            return start;
 
        Node pivot_prev = start;
        Node curr = start;
        int pivot = end.data;
 
        // Iterate till one before the end,
        // no need to iterate till the end
        // because end is pivot
        while (start != end)
       {
            if (start.data < pivot)
            {
                // Keep tracks of last
                // modified item
                pivot_prev = curr;
                int temp = curr.data;
                curr.data = start.data;
                start.data = temp;
                curr = curr.next;
            }
            start = start.next;
        }
 
        // Swap the position of curr i.e.
        // next suitable index and pivot
        int temp = curr.data;
        curr.data = pivot;
        end.data = temp;
 
        // Return one previous to current
        // because current is now pointing
        // to pivot
        return pivot_prev;
    }
 
    void sort(Node start, Node end)
    {
        if(start == null ||
           start == end||
           start == end.next )
            return;
 
        // Split list and partition recurse
        Node pivot_prev = partitionLast(start, end);
        sort(start, pivot_prev);
 
        // If pivot is picked and moved to the start,
        // that means start and pivot is same
        // so pick from next of pivot
        if (pivot_prev != null &&
            pivot_prev == start)
            sort(pivot_prev.next, end);
 
        // If pivot is in between of the list,
        // start from next of pivot, since we
        // have pivot_prev, so we move two nodes
        else if (pivot_prev != null &&
                 pivot_prev.next != null)
            sort(pivot_prev.next.next, end);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        QuickSortLinkedList list =
                 new QuickSortLinkedList();
        list.addNode(30);
        list.addNode(3);
        list.addNode(4);
        list.addNode(20);
        list.addNode(5);
 
        Node n = list.head;
        while (n.next != null)
            n = n.next;
 
        System.out.println(
               "Linked List before sorting");
        list.printList(list.head);
 
        list.sort(list.head, n);
 
        System.out.println(
               "Linked List after sorting");
        list.printList(list.head);
    }
}
// This code is contributed by trinadumca

Producción:

Linked List before sorting 
30 3 4 20 5 
Linked List after sorting 
3 4 5 20 30 

¡ Consulte el artículo completo sobre QuickSort en la lista de enlaces individuales para obtener más detalles!

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *