Рубрики

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

Ниже приведена типичная рекурсивная реализация QuickSort для массивов. Реализация использует последний элемент в качестве оси.

/ * Типичная рекурсивная реализация Quicksort для массива * /

  
/ * Эта функция принимает последний элемент как pivot, помещает элемент pivot в его

   правильная позиция в отсортированном массиве, и все места меньше (меньше, чем

   круг) слева от центра и все большие элементы справа от центра * /

int partition (int arr[], int l, int h)

{

    int x = arr[h];

    int i = (l - 1);

  

  

    for (int j = l; j <= h- 1; j++)

    {

        if (arr[j] <= x)

        {

            i++;

            swap (&arr[i], &arr[j]);

        }

    }

    swap (&arr[i + 1], &arr[h]);

    return (i + 1);

}

  
/ * A [] -> Массив для сортировки, l -> Начальный индекс, h -> Конечный индекс * /

void quickSort(int A[], int l, int h)

{

    if (l < h)

    {        

        int p = partition(A, l, h); / * Индекс разделения * /

        quickSort(A, l, p - 1);  

        quickSort(A, p + 1, h);

    }

}

Можем ли мы использовать тот же алгоритм для связанного списка?
Ниже приведена реализация C ++ для двусвязного списка. Идея проста, мы сначала узнаем указатель на последний узел. Когда у нас есть указатель на последний узел, мы можем рекурсивно отсортировать связанный список, используя указатели на первый и последний узлы связанного списка, аналогично приведенной выше рекурсивной функции, где мы передаем индексы первого и последнего элементов массива. Функция секционирования для связанного списка также похожа на секцию для массивов. Вместо того, чтобы возвращать индекс элемента pivot, он возвращает указатель на элемент pivot. В следующей реализации quickSort () — это просто функция-обертка, основной рекурсивной функцией является _quickSort (), которая аналогична quickSort () для реализации массива.

C ++

// Программа на C ++ для сортировки связанного списка с использованием Quicksort
#include <bits/stdc++.h>

using namespace std;

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

class Node 

    public:

    int data; 

    Node *next; 

    Node *prev; 

}; 

  
/ * Утилита для замены двух элементов * /

void swap ( int* a, int* b ) 

{ int t = *a; *a = *b; *b = t; } 

  
// Полезная функция для поиска
// последний узел связанного списка
Node *lastNode(Node *root) 

    while (root && root->next) 

        root = root->next; 

    return root; 

  
/ * Рассматривает последний элемент как опорный,
помещает элемент поворота на его
правильная позиция в отсортированном массиве,
и местами все меньше (меньше чем
опора) слева от опоры и все большее
элементы справа от оси * /
Node* partition(Node *l, Node *h) 

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

    int x = h->data; 

  

    // аналогично i = l-1 для реализации массива

    Node *i = l->prev; 

  

    // Аналогично "for (int j = l; j <= h- 1; j ++)"

    for (Node *j = l; j != h; j = j->next) 

    

        if (j->data <= x) 

        

            // Аналогично i ++ для массива

            i = (i == NULL)? l : i->next; 

  

            swap(&(i->data), &(j->data)); 

        

    

    i = (i == NULL)? l : i->next; // Аналогично i ++

    swap(&(i->data), &(h->data)); 

    return i; 

  
/ * Рекурсивная реализация
быстрой сортировки для связанного списка * /

void _quickSort(Node* l, Node *h) 

    if (h != NULL && l != h && l != h->next) 

    

        Node *p = partition(l, h); 

        _quickSort(l, p->prev); 

        _quickSort(p->next, h); 

    

  
// Основная функция для сортировки связанного списка.
// Он в основном вызывает _quickSort ()

void quickSort(Node *head) 

    // Найти последний узел

    Node *h = lastNode(head); 

  

    // Вызов рекурсивной быстрой сортировки

    _quickSort(head, h); 

  
// Утилита для печати содержимого arr

void printList(Node *head) 

    while (head) 

    

        cout << head->data << " "

        head = head->next; 

    

    cout << endl; 

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

void push(Node** head_ref, int new_data) 

    Node* new_node = new Node; / * выделить узел * /

    new_node->data = new_data; 

  

    / * так как мы добавляем в

    начало, prev всегда NULL * /

    new_node->prev = NULL; 

  

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

    new_node->next = (*head_ref); 

  

    / * изменить prev головного узла на новый узел * /

    if ((*head_ref) != NULL) (*head_ref)->prev = new_node ; 

  

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

    (*head_ref) = new_node; 

  
/ * Код водителя * /

int main() 

    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; 

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

С

// C программа для сортировки связанного списка с использованием Quicksort
#include <stdio.h>
#include <stdlib.h>

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

struct Node

{

    int data;

    struct Node *next;

    struct Node *prev;

};

  
/ * Утилита для замены двух элементов * /

void swap ( int* a, int* b )

{ int t = *a; *a = *b; *b = t; }

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

struct Node *lastNode(struct Node *root)

{

    while (root && root->next)

        root = root->next;

    return root;

}

  
/ * Рассматривает последний элемент как опорный, помещает
элемент поворота в правильной позиции в отсортированном массиве,
и помещает все меньше (меньше, чем шарнир) влево
центра и всех больших элементов справа от центра * /

struct Node* partition(struct Node *l, struct Node *h)

{

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

    int x = h->data;

  

    // аналогично i = l-1 для реализации массива

    struct Node *i = l->prev;

  

    // Аналогично "for (int j = l; j <= h- 1; j ++)"

    for (struct Node *j = l; j != h; j = j->next)

    {

        if (j->data <= x)

        {

            // Аналогично i ++ для массива

            i = (i == NULL) ? l : i->next;

  

            swap(&(i->data), &(j->data));

        }

    }

    i = (i == NULL) ? l : i->next; // Аналогично i ++

    swap(&(i->data), &(h->data));

    return i;

}

  
/ * Рекурсивная реализация быстрой сортировки для связанного списка * /

void _quickSort(struct Node* l, struct Node *h)

{

    if (h != NULL && l != h && l != h->next)

    {

        struct Node *p = partition(l, h);

        _quickSort(l, p->prev);

        _quickSort(p->next, h);

    }

}

  
// Основная функция для сортировки связанного списка.
// Он в основном вызывает _quickSort ()

void quickSort(struct Node *head)

{

    // Найти последний узел

    struct Node *h = lastNode(head);

  

    // Вызов рекурсивной быстрой сортировки

    _quickSort(head, h);

}

  
// Утилита для печати содержимого arr

void printList(struct Node *head)

{

    while (head)

    {

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

        head = head->next;

    }

    printf("\n");

}

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

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

{

    struct Node* new_node = (struct Node*) 

               malloc(sizeof(struct Node)); / * выделить узел * /

    new_node->data = new_data;

  

    / * так как мы добавляем в начале,

    prev всегда NULL * /

    new_node->prev = NULL;

  

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

    new_node->next = (*head_ref);

  

    / * изменить prev головного узла на новый узел * /

    if ((*head_ref) != NULL) (*head_ref)->prev = new_node ;

  

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

    (*head_ref) = new_node;

}

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

int main(int argc, char **argv)

{

    struct Node *a = NULL;

    push(&a, 5);

    push(&a, 20);

    push(&a, 4);

    push(&a, 3);

    push(&a, 30);

  

    printf("Linked List before sorting \n");

    printList(a);

  

    quickSort(a);

  

    printf("Linked List after sorting \n");

    printList(a);

  

    return 0;

}

Джава

// Java-программа для сортировки связанного списка с использованием Quicksort

class QuickSort_using_Doubly_LinkedList{

    Node head;

    

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

    static class Node{

        private int data;

        private Node next;

        private Node prev;

          

        Node(int d){

            data = d;

            next = null;

            prev = null;

        }

    }

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

    Node lastNode(Node node){

        while(node.next!=null)

            node = node.next;

        return node;

    }

      

  
/ * Рассматривает последний элемент как pivot, помещает элемент pivot в его

   правильная позиция в отсортированном массиве, и все места меньше (меньше, чем

   круг) слева от центра и все большие элементы справа от центра * /

    Node partition(Node l,Node h)

    {

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

        int x = h.data;

          

        // аналогично i = l-1 для реализации массива

        Node i = l.prev;

          

        // Аналогично "for (int j = l; j <= h- 1; j ++)"

        for(Node j=l; j!=h; j=j.next)

        {

            if(j.data <= x)

            {

                // Аналогично i ++ для массива

                i = (i==null) ? l : i.next;

                int temp = i.data;

                i.data = j.data;

                j.data = temp;

            }

        }

        i = (i==null) ? l : i.next;  // Аналогично i ++

        int temp = i.data;

        i.data = h.data;

        h.data = temp;

        return i;

    }

      

    / * Рекурсивная реализация быстрой сортировки для связанного списка * /

    void _quickSort(Node l,Node h)

    {

        if(h!=null && l!=h && l!=h.next){

            Node temp = partition(l,h);

            _quickSort(l,temp.prev);

            _quickSort(temp.next,h);

        }

    }

      

    // Основная функция для сортировки связанного списка. В основном это вызывает _quickSort ()

    public void quickSort(Node node)

    {

        // Найти последний узел

        Node head = lastNode(node);

          

        // Вызов рекурсивной быстрой сортировки

        _quickSort(node,head);

    }

      

     // Утилита для печати содержимого arr

     public void printList(Node head)

     {

        while(head!=null){

            System.out.print(head.data+" ");

            head = head.next;

        }

    }

      

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

    void push(int new_Data)

    {

        Node new_Node = new Node(new_Data);     / * выделить узел * /

          

        // если head равен null, head = new_Node

        if(head==null){

            head = new_Node;

            return;

        }

          

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

        new_Node.next = head;

          

        / * изменить prev головного узла на новый узел * /

        head.prev = new_Node;

          

        / * так как мы добавляем в начале, prev всегда NULL * /

        new_Node.prev = null;

          

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

        head = new_Node;

    }

      

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

    public static void main(String[] args){

            QuickSort_using_Doubly_LinkedList list = new QuickSort_using_Doubly_LinkedList();

              

              

            list.push(5);

            list.push(20);

            list.push(4);

            list.push(3);

            list.push(30);

            

              

            System.out.println("Linked List before sorting ");

            list.printList(list.head);

            System.out.println("\nLinked List after sorting");

            list.quickSort(list.head);

            list.printList(list.head);

          

    }

}

  
// Этот код предоставлен Амитом Хандельвалом

C #

// AC # программа для сортировки связанного списка с использованием Quicksort

using System; 

  

public class QuickSort_using_Doubly_LinkedList

    Node head; 

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

    public class Node{ 

        public int data; 

        public Node next; 

        public Node prev; 

          

        public Node(int d){ 

            data = d; 

            next = null

            prev = null

        

    

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

    Node lastNode(Node node)

    

        while(node.next!=null

            node = node.next; 

        return node; 

    

      

  
/ * Рассматривает последний элемент как опорный,
помещает элемент поворота на его
правильная позиция в отсортированном массиве,
и местами все меньше (меньше чем
опора) слева от опоры и все
большие элементы справа от оси * /

    Node partition(Node l,Node h) 

    

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

        int x = h.data; 

          

        // аналогично i = l-1 для реализации массива

        Node i = l.prev; 

        int temp;

          

        // Аналогично "for (int j = l; j <= h- 1; j ++)"

        for(Node j=l; j!=h; j=j.next) 

        

            if(j.data <= x) 

            

                // Аналогично i ++ для массива

                i = (i==null) ? l : i.next; 

                temp = i.data; 

                i.data = j.data; 

                j.data = temp; 

            

        

        i = (i == null) ? l : i.next; // Аналогично i ++

        temp = i.data; 

        i.data = h.data; 

        h.data = temp; 

        return i; 

    

      

    / * Рекурсивная реализация

    быстрая сортировка для связанного списка * /

    void _quickSort(Node l,Node h) 

    

        if(h!=null && l!=h && l!=h.next){ 

            Node temp = partition(l,h); 

            _quickSort(l,temp.prev); 

            _quickSort(temp.next,h); 

        

    

      

    // Основная функция для сортировки связанного списка.

    // Он в основном вызывает _quickSort ()

    public void quickSort(Node node) 

    

        // Найти последний узел

        Node head = lastNode(node); 

          

        // Вызов рекурсивной быстрой сортировки

        _quickSort(node,head); 

    

      

    // Утилита для печати содержимого arr

    public void printList(Node head) 

    

        while(head!=null){ 

            Console.Write(head.data+" "); 

            head = head.next; 

        

    

      

    / * Функция для вставки узла в

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

    void push(int new_Data) 

    

        Node new_Node = new Node(new_Data); / * выделить узел * /

          

        // если head равен null, head = new_Node

        if(head==null)

        

            head = new_Node; 

            return

        

          

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

        new_Node.next = head; 

          

        / * изменить prev головного узла на новый узел * /

        head.prev = new_Node; 

          

        / * так как мы добавляем в

        начало, prev всегда NULL * /

        new_Node.prev = null

          

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

        head = new_Node; 

    

      

    / * Код водителя * /

    public static void Main(String[] args){ 

            QuickSort_using_Doubly_LinkedList list = new QuickSort_using_Doubly_LinkedList(); 

              

              

            list.push(5); 

            list.push(20); 

            list.push(4); 

            list.push(3); 

            list.push(30); 

              

              

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

            list.printList(list.head); 

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

            list.quickSort(list.head); 

            list.printList(list.head); 

    

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

Выход :

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

Сложность времени: временная сложность вышеописанной реализации такая же, как временная сложность QuickSort () для массивов. Это занимает O (n ^ 2) время в худшем случае и O (nLogn) в среднем и лучшем случаях. Наихудший случай возникает, когда связанный список уже отсортирован.

Можем ли мы реализовать случайную быструю сортировку для связанного списка?
Быстрая сортировка может быть реализована для связанного списка только тогда, когда мы можем выбрать фиксированную точку в качестве оси (как последний элемент в приведенной выше реализации). Случайная быстрая сортировка не может быть эффективно реализована для связанных списков путем выбора случайного центра.

Упражнение:
Вышеприведенная реализация предназначена для двусвязного списка. Измените его для односвязного списка. Обратите внимание, что у нас нет указателя prev в односвязном списке.
Обратитесь к быстрой сортировке по однократному списку для решения.

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

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

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

0.00 (0%) 0 votes