Связанный список. Как улучшить быструю сортировку?

Question

#include <iostream>
#include <time.h>

using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int data){
        this->data = data;
        next = nullptr;
    }
};

class List {
private:
    Node* root;
    int size;

    void qsortRec(Node* root, int start, int finish){
        int pivot = get((start + finish)/2)->data;
        int s = start;
        int f = finish;

        while(s <= f){
            while(get(s)->data < pivot) s++;
            while(get(f)->data > pivot) f--;
            if(s <= f){
                node_swap(s, f);
                s++;
                f--;
            }
        }

        if(start < f) qsortRec(root, start, f);
        if(s < finish) qsortRec(root, s, finish);
    }

    void node_swap(int i, int j){
        Node* ii = get(i);
        Node* jj = get(j);

        int t = ii->data;
        ii->data = jj->data;
        jj->data = t;
    }

public:
    List(){
        root = nullptr;
        size = 0;
    }

    void insert(int data){
        if(root == nullptr) root = new Node(data);
        else {
            Node* curr = root;
            while(curr->next != nullptr) curr = curr->next;
            curr->next = new Node(data);
        }
        size++;
    }

    void display(){
        Node* curr = root;
        while(curr != nullptr){
            cout << curr->data << " ";
            curr = curr->next;
        }
    }

    void qsort(){
        qsortRec(root, 0, size - 1);
    }

    Node* get(const int index){
        int count = 0;
        Node* curr = root;
        while(curr != nullptr){
            if(count == index)
                return curr;
            curr = curr->next;
            count++;
        }

        return nullptr;
    }
};

int main(){
    clock_t start = clock();

    List* list = new List();

    list->insert(4);
    list->insert(9);
    list->insert(1);
    list->insert(0);
    list->insert(7);

    cout << "Initial: ";
    list->display();

    list->qsort();

    cout << endl << "Sorted: ";
    list->display();

    clock_t end = clock();

    cout << endl << (end - start) << "ms" << endl;
}

Answer 1

У вас метод доступа с элементу реализуется с помощью цикла от начала списка до конца. Скорость вашего алгоритма становится квадратичной из-за этого. Пользоваться нужно не get, а сделать относительную функцию поиска.

...
private :
  // по относительному индексу с from
  Node* get(Node* from , int const index);
};

Node* List::get(Node* from , int const index) {
        int count = 0;
        Node* curr = from;
        while(curr != nullptr) {
            if(count == index)                return curr;
            curr = curr->next;
            count++;        }
        return nullptr;    }

Дальше у рекурсивной функции qsortRec аргумент root сделать указателем на Node с индексом start и именем firstNode. Вы всё равно этим аргументом не пользуетесь. И использовать относительный get примерно так:

int pivot = get(firstNode,(start + finish)/2)->data;
while(get(firstNode,s-start)->data < pivot) s++;
while(get(firstNode,f-start)->data > pivot) f--;
node_swap(firstNode,s,f); // ! тоже новый относительный метод 
if(start < f) qsortRec(firstNode, 0, f-start);
if(s < finish) qsortRec(get(firstNode,s-start), 0, finish-start);

После отладки убрать аргумент start , он всегда будет нулевым.

Для списков быстрая сортировка не подходит. Если можно, то нужно использовать сортировку слиянием. https://ru.wikipedia.org/wiki/Сортировка_слиянием

Answer 2

Вот пример quicksort для односвязного списка структур, аналогичных вашему примеру.

Данная программа выбирает в качестве разделяющего (pivot) элемента первый в списке и в среднем (при случайных данных) должна работать за время порядка N * log(N).

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

struct list_item {
  struct list_item *next;
  int v;
};

struct list_hdr {
  struct list_item *head, *tail;
  size_t size;
};


void
add_item_lst (struct list_item *p, struct list_hdr *h)
{
  if (h->tail) 
    h->tail->next = p;
  else
    h->head = p;
  h->tail = p;
  h->size++;
}

void
lst_qsort (struct list_hdr *h)
{
  //  printf("==> "); print_lst(h);

  if (h->head == h->tail)
    return;
  struct list_hdr llt = {0}, leq = {0}, lgt = {0};

  // use first list item as pivot
  // move it to `leq` list
  leq.head = leq.tail = h->head;
  leq.size = 1;
  h->head = h->head->next;

  // divide list to 3 parts
  while (h->head) {
    struct list_item *p = h->head;
    h->head = h->head->next;  // remove item

    // add it to `llt`, `leq` or `lgt` lists
    if (p->v < leq.head->v)
      add_item_lst(p, &llt);
    else if (p->v > leq.head->v)
      add_item_lst(p, &lgt);
    else
      add_item_lst(p, &leq);
  };

  // for speed reason, I not set pointer to next in the tail items
  // now correct them
  if (llt.tail)
    llt.tail->next = 0;
  leq.tail->next = 0;
  if (lgt.tail)
    lgt.tail->next = 0;

  //  print_lst(&llt);
  //  print_lst(&leq);
  //  print_lst(&lgt);
  //  puts("======");

  // sort by parts
  lst_qsort(&llt);
  lst_qsort(&lgt);

  // merge parts to source list
  if (llt.head) {
    h->head = llt.head;
    llt.tail->next = leq.head;
  } else 
    h->head = leq.head;
  h->tail = leq.tail;
  if (h->tail->next = lgt.head) 
    h->tail = lgt.tail;

  //  printf("<== "); print_lst(h);
}

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

БЛОГ НА HUSL

Связанный список. Как улучшить быструю сортировку?

Ответы (2 шт):