Рубрики

Быстрая сортировка по односвязному списку

Быстрая сортировка по двусвязному списку обсуждается здесь . Быстрая сортировка по односвязному списку была дана в качестве упражнения. Ниже приведена реализация C ++ для того же. Важными моментами реализации являются то, что они меняют указатели, а не обмениваются данными, а временная сложность такая же, как и в случае с «Двойным списком».

В partition () мы рассматриваем последний элемент как опорный. Мы перемещаемся по текущему списку и, если узел имеет значение больше, чем pivot, мы перемещаем его после хвоста. Если узел имеет меньшее значение, мы сохраняем его в текущей позиции.
В QuickSortRecur () мы сначала вызываем partition (), который устанавливает pivot в правильное положение и возвращает pivot. После того, как пивот расположен в правильном положении, мы находим хвостовой узел левой стороны (список перед пивотом) и возвращаемся к левому списку. Наконец, мы вернемся к правильному списку.

C ++

// C ++ программа для быстрой сортировки по однострочному списку
#include <iostream>
#include <cstdio>

using namespace std;

  
/ * узел односвязного списка * /

struct Node

{

    int data;

    struct Node *next;

};

  
/ * Полезная функция для вставки узла в начало связанного списка * /

void push(struct Node** head_ref, int new_data)

{

    / * выделить узел * /

    struct Node* new_node = new Node;

  

    / * вставить данные * /

    new_node->data = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node;

}

  
/ * Утилита для печати связанного списка * /

void printList(struct Node *node)

{

    while (node != NULL)

    {

        printf("%d ", node->data);

        node = node->next;

    }

    printf("\n");

}

  
// Возвращает последний узел списка

struct Node *getTail(struct Node *cur)

{

    while (cur != NULL && cur->next != NULL)

        cur = cur->next;

    return cur;

}

  
// Разделяем список, принимая последний элемент в качестве оси

struct Node *partition(struct Node *head, struct Node *end,

                    struct Node **newHead, struct Node **newEnd)

{

    struct Node *pivot = end;

    struct Node *prev = NULL, *cur = head, *tail = pivot;

  

    // Во время раздела заголовок и конец списка могут измениться

    // который обновляется в переменных newHead и newEnd

    while (cur != pivot)

    {

        if (cur->data < pivot->data)

        {

            // Первый узел, который имеет значение меньше, чем стержень - становится

            // новый руководитель

            if ((*newHead) == NULL)

                (*newHead) = cur;

  

            prev = cur; 

            cur = cur->next;

        }

        else // Если узел cur больше чем pivot

        {

            // Перемещаем узел cur к следующему из tail и меняем tail

            if (prev)

                prev->next = cur->next;

            struct Node *tmp = cur->next;

            cur->next = NULL;

            tail->next = cur;

            tail = cur;

            cur = tmp;

        }

    }

  

    // Если сводные данные - самый маленький элемент в текущем списке,

    // пивот становится главой

    if ((*newHead) == NULL)

        (*newHead) = pivot;

  

    // Обновляем newEnd до текущего последнего узла

    (*newEnd) = tail;

  

    // Возвращаем узел разворота

    return pivot;

}

  

  
// здесь сортировка происходит исключая конечного узла

struct Node *quickSortRecur(struct Node *head, struct Node *end)

{

    // базовое условие

    if (!head || head == end)

        return head;

  

    Node *newHead = NULL, *newEnd = NULL;

  

    // Разделим список, newHead и newEnd будут обновлены

    // функцией разделения

    struct Node *pivot = partition(head, end, &newHead, &newEnd);

  

    // Если pivot является наименьшим элементом - не нужно повторяться для

    // левая часть.

    if (newHead != pivot)

    {

        // Установить узел перед сводным узлом как NULL

        struct Node *tmp = newHead;

        while (tmp->next != pivot)

            tmp = tmp->next;

        tmp->next = NULL;

  

        // повторить список перед поворотом

        newHead = quickSortRecur(newHead, tmp);

  

        // Меняем следующий последний узел левой половины на разворот

        tmp = getTail(newHead);

        tmp->next = pivot;

    }

  

    // повторить список после элемента pivot

    pivot->next = quickSortRecur(pivot->next, newEnd);

  

    return newHead;

}

  
// Основная функция для быстрой сортировки. Это обертка над рекурсивной
// функция quickSortRecur ()

void quickSort(struct Node **headRef)

{

    (*headRef) = quickSortRecur(*headRef, getTail(*headRef));

    return;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    struct Node *a = NULL;

    push(&a, 5);

    push(&a, 20);

    push(&a, 4);

    push(&a, 3);

    push(&a, 30);

  

    cout << "Linked List before sorting \n";

    printList(a);

  

    quickSort(&a);

  

    cout << "Linked List after sorting \n";

    printList(a);

  

    return 0;

}

Джава

// Java программа для быстрой сортировки по однострочному списку

  
/ * сортировать связанный список с помощью быстрой сортировки * /

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;

    }

}

  
// занимает первый и последний узел,
// но не ломать ссылки в
// весь связанный список
Node paritionLast(Node start, Node end)
{

    if(start == end || 

       start == null || end == null)

        return start;

  

    Node pivot_prev = start;

    Node curr = start; 

    int pivot = end.data; 

      

    // итерация до конца до конца,

    // не нужно перебирать до конца

    // потому что конец это стержень

    while(start != end )

    {

        if(start.data < pivot)

        

            // отслеживаем последний измененный элемент

            pivot_prev = curr; 

            int temp = curr.data; 

            curr.data = start.data; 

            start.data = temp; 

            curr = curr.next; 

        }

        start = start.next; 

    }

      

    // меняем позицию курсора т.е.

    // следующий подходящий индекс и пивот

    int temp = curr.data; 

    curr.data = pivot; 

    end.data = temp; 

  

    // вернуть предыдущий к текущему

    // потому что ток сейчас указывает на пивот

    return pivot_prev;

}

  

void sort(Node start, Node end)

{

    if(start == end )

        return;

          

    // разделить список и разделить рекурсив

    Node pivot_prev = paritionLast(start, end);

    sort(start, pivot_prev);

      

    // если пивот выбран и перемещен в начало,

    // это означает, что начало и поворот одинаковы

    // поэтому выбираем из ближайшего пивота

    if( pivot_prev != null && 

        pivot_prev == start )

        sort(pivot_prev.next, end);

          

    // если точка находится между списком,

    // начать со следующей точки разворота,

    // так как у нас есть pivot_prev, поэтому мы перемещаем два узла

    else if(pivot_prev != null && 

            pivot_prev.next != null)

        sort(pivot_prev.next.next, end);

}

  
// Код драйвера

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("\nLinked List after sorting");

    list.printList(list.head);

}
}

  
// Этот код предоставлен trinadumca

C #

// C # программа для быстрой сортировки на
// однострочный список

using System;

  
/ * сортировать связанный список с помощью быстрой сортировки * /

class GFG 

{

public class Node

{

    public int data;

    public Node next;

  

    public 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)

    {

        Console.Write(n.data);

        Console.Write(" ");

        n = n.next;

    }

}

  
// занимает первый и последний узел,
// но не ломать ссылки в
// весь связанный список
Node paritionLast(Node start, Node end)
{

    if(start == end || 

       start == null || end == null)

        return start;

  

    Node pivot_prev = start;

    Node curr = start; 

    int pivot = end.data; 

      

    // итерация до конца до конца,

    // не нужно перебирать до конца

    // потому что конец это стержень

    int temp;

    while(start != end )

    {

          

        if(start.data < pivot)

        

            // отслеживаем последний измененный элемент

            pivot_prev = curr; 

            temp = curr.data; 

            curr.data = start.data; 

            start.data = temp; 

            curr = curr.next; 

        }

        start = start.next; 

    }

      

    // меняем позицию курсора т.е.

    // следующий подходящий индекс и пивот

    temp = curr.data; 

    curr.data = pivot; 

    end.data = temp; 

  

    // вернуть предыдущий к текущему

    // потому что ток сейчас указывает на пивот

    return pivot_prev;

}

  

void sort(Node start, Node end)

{

    if(start == end )

        return;

          

    // разделить список и разделить рекурсив

    Node pivot_prev = paritionLast(start, end);

    sort(start, pivot_prev);

      

    // если пивот выбран и перемещен в начало,

    // это означает, что начало и поворот одинаковы

    // поэтому выбираем из ближайшего пивота

    if( pivot_prev != null && 

        pivot_prev == start )

        sort(pivot_prev.next, end);

          

    // если точка находится между списком,

    // начать со следующей точки разворота,

    // так как у нас есть pivot_prev, поэтому мы перемещаем два узла

    else if(pivot_prev != null && 

            pivot_prev.next != null)

        sort(pivot_prev.next.next, end);

}

  
// Код драйвера

public static void Main(String[] args)

{

    GFG list = new GFG();

    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;

  

    Console.WriteLine("Linked List before sorting");

    list.printList(list.head);

  

    list.sort(list.head , n);

  

    Console.WriteLine("\nLinked List after sorting");

    list.printList(list.head);

}
}

  
// Этот код предоставлен 29AjayKumar


Выход:

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

Эта статья предоставлена Balasubramanian.N . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Быстрая сортировка по односвязному списку

0.00 (0%) 0 votes