Рубрики

Итеративный выбор сортировки для связанного списка

Для заданного связанного списка задача состоит в том, чтобы отсортировать связанный список в порядке возрастания, используя сортировку выбора.

Примеры:

Input : 1->4->2->2->3
Output : 1->2->2->3->4

Input : 5->4->3->2
Output : 2->3->4->5

Алгоритм сортировки выбора : итерация заданного списка N раз, где N — количество элементов в списке. На каждой итерации сортировки выбора минимальный элемент (с учетом возрастающего порядка) из несортированного подмассива выбирается и перемещается в отсортированный подмассив.

Пример :

list = 64 25 12 22 11

// Find the minimum element in list(0...4)
// and place it at beginning
11 25 12 22 64

// Find the minimum element in list(1...4)
// and place it at beginning of list(1...4)
11 12 25 22 64

// Find the minimum element in list(2...4)
// and place it at beginning of list(2...4)
11 12 22 25 64

// Find the minimum element in list(3...4)
// and place it at beginning of list(3...4)
11 12 22 25 64 

Требуемая замена может быть сделана двумя способами:

  1. Переставляя части данных узлов.
  2. Сменив полные узлы.

Вторая реализация обычно используется, когда элементы списка являются какими-то записями, потому что в таком случае обмен данными становится утомительным и дорогим из-за присутствия большого количества элементов данных.

Метод реализации 1 : Ниже приведена реализация функции сортировки выбора для сортировки связанных списков путем замены только частей данных узла.

void selectionSort(node* head)

{

    node* temp = head;

  

    // Обход списка

    while (temp) {

        node* min = temp;

        node* r = temp->next;

  

        // Обход несортированного подсписка

        while (r) {

            if (min->data > r->data)

                min = r;

  

            r = r->next;

        }

  

        // Обмен данными

        int x = temp->data;

        temp->data = min->data;

        min->data = x;

        temp = temp->next;

    }

}

Способ 2 : обмен данными, без сомнения, легче реализовать и понять, но в некоторых случаях (как упомянуто выше) это нежелательно. При выполнении замены следующих частей двух узлов необходимо учитывать четыре случая:

  1. Узлы являются смежными, и первый узел является начальным узлом.
  2. Узлы являются смежными, и первый узел не является начальным узлом.
  3. Узлы не являются соседними, и первый узел является начальным узлом.
  4. Узлы не являются соседними, и первый узел не является начальным узлом.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

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

struct Node {

    int data;

    Node* next;

};

  
// Сервисная функция для создания
// новый узел связанного списка

Node* newNode(int val)

{

    Node* temp = new Node;

  

    temp->data = val;

  

    temp->next = NULL;

  

    return temp;

}

  
// Функция сортировки связанного списка с использованием выделения
// сортируем алгоритм, меняя местами следующие указатели
Node* selectionSort(Node* head)
{

    Node *a, *b, *c, *d, *r;

  

    a = b = head;

  

    // Пока b не последний узел

    while (b->next) {

  

        c = d = b->next;

  

        // Пока d указывает на действительный узел

        while (d) {

  

            if (b->data > d->data) {

  

                // Если d появляется сразу после b

                if (b->next == d) {

  

                    // Случай 1: b - заголовок связанного списка

                    if (b == head) {

  

                        // Переместить d до b

                        b->next = d->next;

                        d->next = b;

  

                        // Поменять местами указатели b и d

                        r = b;

                        b = d;

                        d = r;

  

                        c = d;

  

                        // Обновляем голову

                        head = b;

  

                        // Перейти к следующему элементу

                        // как уже в порядке

                        d = d->next;

                    }

  

                    // Случай 2: b не является заголовком связанного списка

                    else {

  

                        // Переместить d до b

                        b->next = d->next;

                        d->next = b;

                        a->next = d;

  

                        // Поменять местами указатели b и d

                        r = b;

                        b = d;

                        d = r;

  

                        c = d;

  

                        // Перейти к следующему элементу

                        // как уже в порядке

                        d = d->next;

                    }

                }

  

                // Если b и d имеют ненулевое значение

                // количество узлов между ними

                else {

  

                    // Случай 3: b - заголовок связанного списка

                    if (b == head) {

  

                        // Поменять местами b-> next и d-> next

                        r = b->next;

                        b->next = d->next;

                        d->next = r;

                        c->next = b;

  

                        // Поменять местами указатели b и d

                        r = b;

                        b = d;

                        d = r;

  

                        c = d;

  

                        // Перейти к следующему элементу

                        // как уже в порядке

                        d = d->next;

  

                        // Обновляем голову

                        head = b;

                    }

  

                    // Случай 4: b не является заголовком связанного списка

                    else {

  

                        // Поменять местами b-> next и d-> next

                        r = b->next;

                        b->next = d->next;

                        d->next = r;

                        c->next = b;

                        a->next = d;

  

                        // Поменять местами указатели b и d

                        r = b;

                        b = d;

                        d = r;

  

                        c = d;

  

                        // Перейти к следующему элементу

                        // как уже в порядке

                        d = d->next;

                    }

                }

            }

            else {

  

                // Обновление c и переход к следующему элементу

                // как уже в порядке

                c = d;

                d = d->next;

            }

        }

  

        a = b;

        b = b->next;

    }

  

    return head;

}

  
// Функция для печати списка

void printList(Node* head)

{

    while (head) {

        cout << head->data << " ";

        head = head->next;

    }

}

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

int main()

{

    Node* head = newNode(5);

    head->next = newNode(4);

    head->next->next = newNode(3);

  

    head = selectionSort(head);

  

    printList(head);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG {

  

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

    static class Node {

        int data;

        Node next;

    };

  

    // Сервисная функция для создания

    // новый узел связанного списка

    static Node newNode(int val)

    {

        Node temp = new Node();

  

        temp.data = val;

  

        temp.next = null;

  

        return temp;

    }

  

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

    // сортируем алгоритм, меняя местами следующие указатели

    static Node selectionSort(Node head)

    {

        Node a, b, c, d, r;

  

        a = b = head;

  

        // Пока b не последний узел

        while (b.next != null) {

  

            c = d = b.next;

  

            // Пока d указывает на действительный узел

            while (d != null) {

  

                if (b.data > d.data) {

  

                    // Если d появляется сразу после b

                    if (b.next == d) {

  

                        // Случай 1: b - заголовок связанного списка

                        if (b == head) {

  

                            // Переместить d до b

                            b.next = d.next;

                            d.next = b;

  

                            // Поменять местами указатели b и d

                            r = b;

                            b = d;

                            d = r;

  

                            c = d;

  

                            // Обновляем голову

                            head = b;

  

                            // Перейти к следующему элементу

                            // как уже в порядке

                            d = d.next;

                        }

  

                        // Случай 2: b не является заголовком связанного списка

                        else {

  

                            // Переместить d до b

                            b.next = d.next;

                            d.next = b;

                            a.next = d;

  

                            // Поменять местами указатели b и d

                            r = b;

                            b = d;

                            d = r;

  

                            c = d;

  

                            // Перейти к следующему элементу

                            // как уже в порядке

                            d = d.next;

                        }

                    }

  

                    // Если b и d имеют ненулевое значение

                    // количество узлов между ними

                    else {

  

                        // Случай 3: b - заголовок связанного списка

                        if (b == head) {

  

                            // Поменять местами b.next и d.next

                            r = b.next;

                            b.next = d.next;

                            d.next = r;

                            c.next = b;

  

                            // Поменять местами указатели b и d

                            r = b;

                            b = d;

                            d = r;

  

                            c = d;

  

                            // Перейти к следующему элементу

                            // как уже в порядке

                            d = d.next;

  

                            // Обновляем голову

                            head = b;

                        }

  

                        // Случай 4: b не является заголовком связанного списка

                        else {

  

                            // Поменять местами b.next и d.next

                            r = b.next;

                            b.next = d.next;

                            d.next = r;

                            c.next = b;

                            a.next = d;

  

                            // Поменять местами указатели b и d

                            r = b;

                            b = d;

                            d = r;

  

                            c = d;

  

                            // Перейти к следующему элементу

                            // как уже в порядке

                            d = d.next;

                        }

                    }

                }

                else {

  

                    // Обновление c и переход к следующему элементу

                    // как уже в порядке

                    c = d;

                    d = d.next;

                }

            }

  

            a = b;

            b = b.next;

        }

  

        return head;

    }

  

    // Функция для печати списка

    static void printList(Node head)

    {

        while (head != null) {

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

            head = head.next;

        }

    }

  

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

    public static void main(String args[])

    {

        Node head = newNode(5);

        head.next = newNode(4);

        head.next.next = newNode(3);

  

        head = selectionSort(head);

  

        printList(head);

    }

}

  
// Этот код предоставлен Арнабом Кунду

python3

# Python3 реализация подхода

  
# Узел связанного списка

class Node:

      

    def __init__(self, val):

        self.data = val

        self.next = None

  
# Функция для сортировки связанного списка
# используя алгоритм сортировки выбора
# путем замены следующих указателей

def selectionSort(head): 

  

    a = b = head 

  

    # Пока b не последний узел

    while b.next

  

        c = d = b.next

  

        # Пока d указывает на действительный узел

        while d: 

  

            if b.data > d.data: 

  

                # Если d появляется сразу после b

                if b.next == d: 

  

                    # Случай 1: б - голова

                    № связанного списка

                    if b == head: 

  

                        # Переместить d до b

                        b.next = d.next

                        d.next =

  

                        # Поменяйте местами указатели b и d

                        b, d = d, b 

                        c =

  

                        # Обновить голову

                        head =

  

                        # Перейти к следующему элементу

                        # как уже в порядке

                        d = d.next

                      

                    # Случай 2: б не голова

                    № связанного списка

                    else

  

                        # Переместить d до b

                        b.next = d.next

                        d.next =

                        a.next =

  

                        # Поменяйте местами указатели b и d

                        b, d = d, b 

                        c =

  

                        # Перейти к следующему элементу

                        # как уже в порядке

                        d = d.next

                      

                # Если b и d имеют ненулевое значение

                # количество узлов между ними

                else:

  

                    # Случай 3: б - голова

                    № связанного списка

                    if b == head: 

  

                        # Поменяйте местами b.next и d.next

                        r = b.next

                        b.next = d.next

                        d.next =

                        c.next =

  

                        # Поменяйте местами указатели b и d

                        b, d = d, b 

                        c =

  

                        # Перейти к следующему элементу

                        # как уже в порядке

                        d = d.next

  

                        # Обновить голову

                        head =

                      

                    # Случай 4: б не голова

                    № связанного списка

                    else

  

                        # Поменяйте местами b.next и d.next

                        r = b.next

                        b.next = d.next

                        d.next =

                        c.next =

                        a.next =

  

                        # Поменяйте местами указатели b и d

                        b, d = d, b 

                        c =

  

                        # Перейти к следующему элементу

                        # как уже в порядке

                        d = d.next

                      

            else:

  

                # Обновить c и перейти к следующему элементу

                # как уже в порядке

                c =

                d = d.next

  

        a =

        b = b.next

      

    return head 

  
# Функция для печати списка

def printList(head): 

  

    while head: 

        print(head.data, end = " "

        head = head.next

  
Код водителя

if __name__ == "__main__":

  

    head = Node(5

    head.next = Node(4

    head.next.next = Node(3

  

    head = selectionSort(head) 

  

    printList(head) 

  
# Этот код добавлен
# от Rituraj Jain

C #

// C # реализация подхода

using System;

  

class GFG {

  

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

    public class Node {

        public int data;

        public Node next;

    };

  

    // Сервисная функция для создания

    // новый узел связанного списка

    static Node newNode(int val)

    {

        Node temp = new Node();

  

        temp.data = val;

  

        temp.next = null;

  

        return temp;

    }

  

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

    // сортируем алгоритм, меняя местами следующие указатели

    static Node selectionSort(Node head)

    {

        Node a, b, c, d, r;

  

        a = b = head;

  

        // Пока b не последний узел

        while (b.next != null) {

  

            c = d = b.next;

  

            // Пока d указывает на действительный узел

            while (d != null) {

  

                if (b.data > d.data) {

  

                    // Если d появляется сразу после b

                    if (b.next == d) {

  

                        // Случай 1: b - заголовок связанного списка

                        if (b == head) {

  

                            // Переместить d до b

                            b.next = d.next;

                            d.next = b;

  

                            // Поменять местами указатели b и d

                            r = b;

                            b = d;

                            d = r;

  

                            c = d;

  

                            // Обновляем голову

                            head = b;

  

                            // Перейти к следующему элементу

                            // как уже в порядке

                            d = d.next;

                        }

  

                        // Случай 2: b не является заголовком связанного списка

                        else {

  

                            // Переместить d до b

                            b.next = d.next;

                            d.next = b;

                            a.next = d;

  

                            // Поменять местами указатели b и d

                            r = b;

                            b = d;

                            d = r;

  

                            c = d;

  

                            // Перейти к следующему элементу

                            // как уже в порядке

                            d = d.next;

                        }

                    }

  

                    // Если b и d имеют ненулевое значение

                    // количество узлов между ними

                    else {

  

                        // Случай 3: b - заголовок связанного списка

                        if (b == head) {

  

                            // Поменять местами b.next и d.next

                            r = b.next;

                            b.next = d.next;

                            d.next = r;

                            c.next = b;

  

                            // Поменять местами указатели b и d

                            r = b;

                            b = d;

                            d = r;

  

                            c = d;

  

                            // Перейти к следующему элементу

                            // как уже в порядке

                            d = d.next;

  

                            // Обновляем голову

                            head = b;

                        }

  

                        // Случай 4: b не является заголовком связанного списка

                        else {

  

                            // Поменять местами b.next и d.next

                            r = b.next;

                            b.next = d.next;

                            d.next = r;

                            c.next = b;

                            a.next = d;

  

                            // Поменять местами указатели b и d

                            r = b;

                            b = d;

                            d = r;

  

                            c = d;

  

                            // Перейти к следующему элементу

                            // как уже в порядке

                            d = d.next;

                        }

                    }

                }

                else {

  

                    // Обновление c и переход к следующему элементу

                    // как уже в порядке

                    c = d;

                    d = d.next;

                }

            }

  

            a = b;

            b = b.next;

        }

  

        return head;

    }

  

    // Функция для печати списка

    static void printList(Node head)

    {

        while (head != null) {

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

            head = head.next;

        }

    }

  

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

    public static void Main(String[] arg)

    {

        Node head = newNode(5);

        head.next = newNode(4);

        head.next.next = newNode(3);

  

        head = selectionSort(head);

  

        printList(head);

    }

}

  
// Этот код предоставлен Rajput-Ji

Выход:

3 4 5

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

Итеративный выбор сортировки для связанного списка

0.00 (0%) 0 votes