Sortowanie listy przez podział

0
type
     TKey = integer;
     PNode = ^TNode;
     TNode = record
                          key:TKey;
                         next:PNode;
             end;

function getTail(head:PNode):PNode;
var tail:PNode;
begin
  tail := head;
  while (tail <> NIL)and(tail^.next <> NIL)do
     tail := tail^.next;
  getTail := tail;
end;

procedure tailins(rec:PNode;var first,last:PNode);
begin
  if first = NIL then
     first := rec
  else
     last^.next := rec;
  last := rec;
end;

function quickSort(r:PNode;var last:PNode):PNode;
var lowf,lowl,midf,midl,highf,highl:PNode;
begin
   if r = NIL then
   begin
       last :=NIL;
       quickSort := r
   end
   else
   begin
       lowf := NIL;
       midf := NIL;
       highf := NIL;
        tailins(r,midf,midl);
        r := r^.next;
       while r <> NIL do
       begin
           if r^.key < midf^.key then
                     tailins(r,lowf,lowl)
           else if r^.key = midf^.key then
                   tailins(r,midf,midl)
          else
                 tailins(r,highf,highl);
          r := r^.next
    end;
    if lowf <> NIL then
    begin
          lowl^.next := NIL;
          quickSort := quickSort(lowf,last);
          last^.next := midf
    end
    else
       quickSort := midf;
    if highf <> NIL then
        highl^.next := NIL;
    midl^.next := quickSort(highf,last);
    if last = NIL then
        last := midl
  end;
end;

Przypuśćmy że chcemy dopisać do rekordu węzła wskaźnik na poprzednika
Jak ustawić wskaźniki na poprzedników aby funkcja sortowała także listę dwukierunkową ?
Ustawianie poprzedników powinno być zrealizowane przez funkcję sortującą
Jeśli chodzi o ustawienie wskaźników na poprzedników w funkcji wstawiającej istniejący węzeł na koniec listy to
podejrzałem kod przykładowej listy dwukierunkowej i tam proponują do procedury tailins
dopisać instrukcję rec^.prev := last w bloku else zaraz po instrukcji last^.next := rec

   else
   begin
      last^.next := rec;
      rec^.prev := last
   end;

Jeśli chodzi o ustawienie wskaźników na poprzedników w funkcji sortującej to
próbowałem powstawiać instrukcję

if x^.next <> nil then
   x^.next^.prev := x;

w różne miejsca kodu ale nie dawało to oczekiwanego rezultatu

1

Quick sort absolutnie nie nadaje się do sortowania list, ani jednokierunkowych, ani dwukierunkowych, bo wykorzystuje ich słaby punkt – wolny czas losowego dostępu. Najlepszym rozwiązaniem dla list jest merge sort.

Jeśli mimo wszystko chcesz użyć sortowania szybkiego, to nie dotykaj wskaźników konstruujących listę – sortuj wyłącznie dane (czyli liczby z pól Key). O wiele mniej kodu i o wiele mniej instrukcji do wykonania. Poza tym, jeśli źle napiszesz kod sortujący, to co najwyżej pogubisz dane, ale w dalszym ciągu lista będzie posiadać poprawną budowę.

0

https://www.geeksforgeeks.org/quicksort-for-linked-list/
https://www.geeksforgeeks.org/quicksort-on-singly-linked-list/

Dla pierwszego opis:

Time complexity of the above implementation is same as time complexity of QuickSort() for arrays.

0

@furious programming tak ja też uważam że merge sort lepiej pasuje do sortowania list
ale Merge sorta już mam napisanego
Jakoś udało mi się samemu w nim ustawić wskaźniki na poprzedników w algorytmie Merge Sort
Znalazłem też funkcje do BST sorta tyle że dwie funkcje pomocnicze są rekurencyjne i jedynie główna funkcja sortująca była napisana iteracyjnie
Chciałem też dla porównania mieć Quick Sorta ale znalazłem go tylko dla listy jednokierunkowej i chciałbym wiedzieć jak ustawić wskaźniki na poprzedników
Z ustawieniem tych wskaźników poza funkcją sortującą nie byłoby problemu ale uważam że lepiej te wskaźniki ustawić wewnątrz funkcji sortującej
Co do sortowania danych
Tutaj może tego nie widać ale gdybyśmy chcieli sortowania użyć do otoczki wypukłej czy wyszukiwania części wspólnej dwóch plików
to część danych miałaby więcej niż jedną składową
(w przypadku wczytywania pliku do pamięci część danych może zawierać całkowitoliczbowy numer linii oraz łańcuchową linie, albo cały rekord
zależnie od formatu danych zapisanych w pliku , w przypadku otoczki danymi będą współrzędne punktu)
Jakoś mimo tego że nie działa dobrze na listach Shalom mimo to go proponuje
Powyższy kod znalazłem w książce o algorytmach której współautorem jest pewien Chilijczyk
vpiotr tak widziałem ten kod geeksów ale bardziej mi się podobał kod który tutaj przedstawiłem

0
nowy121105 napisał(a):

Chciałem też dla porównania mieć Quick Sorta ale znalazłem go tylko dla listy jednokierunkowej i chciałbym wiedzieć jak ustawić wskaźniki na poprzedników […]

Nie rozumiesz – sortowanie szybkie list jedno- i dwukierunkowych nie polega na reorganizacji węzłów listy, bo jest to zbyt skomplikowane przy jednoczesnym braku jakichkolwiek zalet.

Co do sortowania danych
Tutaj może tego nie widać ale gdybyśmy chcieli sortowania użyć do otoczki wypukłej czy wyszukiwania części wspólnej dwóch plików to część danych miałaby więcej niż jedną składową (w przypadku wczytywania pliku do pamięci część danych może zawierać całkowitoliczbowy numer linii oraz łańcuchową linie, albo cały rekord

W przypadku gdy jeden węzeł listy ma za zadanie przechowywać wiele/mnóstwo danych, te dane grupuje się i wystawia pointer lub referencję, tak aby swap danych sprowadzić do swapu raptem dwóch liczb (adresów). Dzięki temu czas sortowania (nie złożoność!) nie jest zależny od ilości danych zawartych w węzłach.

vpiotr tak widziałem ten kod geeksów ale bardziej mi się podobał kod który tutaj przedstawiłem

W jakim sensie „podoba Ci się” ten kod? Spory overcoding, nie działa prawidłowo, do tego zawiera mało mówiące identyfikatory i nie jest nawet sformatowany (patrz m.in. na randomowe wcięcia).

Zwróć uwagę na kod podany w zasugerowanym artykule – konstrukcja listy nie jest zmieniana, swap dotyczy wyłącznie danych (funkcja swap pobiera wskaźniki na dwie liczby, nie na dwa węzły).

0

@furious jeśli uważasz że kod nie działa nawet dla list jednokierunkowych napisz do Ricardo Baeza-Yatesa to on jest współautorem
książki z której wziąłem kod
Mnie wyśmiewasz bo wiesz że nie jestem programistą (miałem tylko podstawy programowania i to ponad 15 lat temu)
ale ciekawy jestem czy uda ci się wyśmiać tego Ricardo

Wspominałeś Merge sorta

Na upartego procedury tailins można użyć też do scalania list
i proponowana zmiana wystarczy aby działała także dla list dwukierunkowych

Kiedyś wyśmiewałeś to iterowanie wskaźników
ale węzeł po którym rozdzielamy listę jakoś trzeba znaleźć
i algorytm sortowania przez scalanie zakłada żeby był to węzeł środkowy

Próbujesz wyśmiać nazewnictwo z tym też do Ricardo

Sortowanie przez podział i sortowanie przez scalanie są do siebie podobne

W sortowaniu przez podział wybieramy element rozdzielający
(najszybszy dostęp mamy do tych węzłów do których pamiętamy wskaźnik najczęściej jest to głowa lub ogon , w tym kodzie jest to głowa)
Tutaj sortowana lista jest dzielona na trzy podlisty
lowf (low first) głowa listy zawierającej węzły o wartościach pól kluczowych mniejszych od wartości pola kluczowego elementu rozdzielającego
lowl (low last) ogon listy zawierającej węzły o wartościach pól kluczowych mniejszych od wartości pola kluczowego elementu rozdzielającego
midf (middle first) głowa listy zawierającej węzły o wartościach pól kluczowych równych co do wartości pola kluczowego elementu rozdzielającego
midl (middle last) ogon listy zawierającej węzły o wartościach pól kluczowych równych co do wartości pola kluczowego elementu rozdzielającego
highf (high first) głowa listy zawierającej węzły o wartościach pól kluczowych większych od wartości pola kluczowego elementu rozdzielającego
highl (high last) ogon listy zawierającej węzły o wartościach pól kluczowych większych od wartości pola kluczowego elementu rozdzielającego

Wstawiamy węzły do tych podlist (do tego używamy pomocniczej procedury tailins - tail insert )
i rekursywnie wywołujemy funkcje sortującą na podliście zawierającej klucze mniejsze od klucza węzła rozdzielającego
oraz na podliście zawierającej klucze większe od klucza węzła rozdzielającego

Następnie scalamy podlisty przy czym scalanie powinno zredukować się do konkatenacji

last - ogon posortowanej listy (w oryginalnym kodzie był globalny)
r - głowa sortowanej listy i na upartego tylko ten wskaźnik mógłby nazywać

Jeśli chodzi o sortowanie przez scalanie to

W przypadku jeśli lista posiada więcej niż jeden element
(sprawdzamy czy głowa i jej następnik nie są puste)
dzielimy listę mniej więcej na połowę (aby znaleźć węzeł po którym należy przerwać listę stosujemy wyśmiewane przez ciebie iterowanie wskaźników)
rekursywnie sortujemy obydwie połowy
scalamy posortowane podlisty (tutaj też możemy użyć pomocniczej procedury tailins do wstawiania węzłów wtedy kod będzie przypominał nieco scalanie tablic)

procedure tailins(rec:PNode;var first,last:PNode);
begin
  if first = NIL then
     first := rec
  else
  begin
    last^.next := rec;
    rec^.prev := last;
  end;
  last := rec;
end;

procedure split(head:PNode;var front,back:PNode);
var slow,fast:PNode;
begin
  if (head = NIL)or(head^.next = NIL)then
  begin
    front := head;
    back := NIL;
  end
  else
  begin
    slow := head;
    fast := head^.next;
    while fast <> NIL do
    begin
      fast := fast^.next;
      if fast <> NIL then
      begin
        slow := slow^.next;
        fast := fast^.next;
      end;
    end;
    front := head;
    back := slow^.next;
    back^.prev := NIL;
    slow^.next := NIL;
  end;
end;

procedure merge(var head:PNode;A,B:PNode);
var headS,tailS:PNode;
begin
  headS:=NIL;
  tailS:=NIL;
  while (A <> NIL)and (B <> NIL)do
  begin
    if A^.data <= B^.data then
    begin
      tailins(A,headS,tailS);
      A := A^.next;
    end
    else
    begin
      tailins(B,headS,tailS);
      B := B^ .next;
    end;
  end;
  while A <> NIL do
  begin
    tailins(A,headS,tailS);
    A := A^.next;
  end;
  while B <> NIL do
  begin
    tailins(B,headS,tailS);
    B := B^.next;
  end;
  head := headS;
end;

procedure mergesort(var head:PNode);
var h1,h2:PNode;
begin
  if (head <> NIL) and (head^.next <> NIL) then
  begin
    split(head,h1,h2);
    mergesort(h1);
    mergesort(h2);
    merge(head,h1,h2);
  end;
end;

Gdy wstawiłem ten kod do listy to sortowanie (przez scalanie) działało
zatem poprawka dla pomocniczej procedury wstawiającej jest dobra
Problemem może być ustawienie wskaźników na poprzedniki podczas konkatenacji

0

Hej,
z całym szacunkiem, ale zajmij się może czymś bardziej praktycznym... :) W całym swoim życiu nie poświęciłem więcej niż parędziesiąt godzin na sortowanie...z czego chyba z 90% na merge sort... :) Nie krytykuję, ale dobrze radzę, rozgrzebywanie różnych metod sortowania jest moim zdaniem bezproduktywne... :)

0
nowy121105 napisał(a):

@furious jeśli uważasz że kod nie działa nawet dla list jednokierunkowych napisz do Ricardo Baeza-Yatesa to on jest współautorem

Twój kod sortujący nie działa prawidłowo dla list dwukierunkowych – o tym pisałem. A nie zadziała prawidłowo, jeśli nie rozwiążesz problemu z ustawianiem wskaźników na poprzedni węzeł. Lista musi mieć prawidłowo ustawione wskaźniki, inaczej wysypie się podczas iteracji i/lub spowoduje wycieki pamięci.

Mnie wyśmiewasz bo wiesz że nie jestem programistą (miałem tylko podstawy programowania i to ponad 15 lat temu)

Nie wiem kim jesteś, no bo skąd mam to wiedzieć? Poza tym nie wyśmiewam Cię, a jedynie krytykuję to co podałeś. Mam kłamać, że wszystko jest w porządku? Ok, wszystko gra – gratuluję rozwiązania.

Wspominałeś Merge sorta

Wspomniałem o tym, ale nie po to, aby robić off-top. Wątek dotyczy sortowania szybkiego na liście dwukierunkowej i o tym powinniśmy dyskutować.

Na upartego procedury tailins można użyć też do scalania list

Tu masz gotowy kod w C++https://www.geeksforgeeks.org/quicksort-for-linked-list/ – wystarczy go przepisać na Pascala oraz zmienić zawartość funkcji swap, tak aby zamieniała miejscami całe węzły. Mowa o tym fragmencie:

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(Node *root)
{
    while (root && root->next)
        root = root->next;
    return root;
}

Node* partition(Node *l, Node *h)
{
    int x  = h->data;
    Node *i = l->prev;

    for (Node *j = l; j != h; j = j->next)
    {
        if (j->data <= x)
        {
            i = (i == NULL)? l : i->next;
            swap(&(i->data), &(j->data));
        }
    }
    i = (i == NULL)? l : i->next;
    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);
    }
}

void quickSort(struct Node *head)
{
    struct Node *h = lastNode(head);
    _quickSort(head, h);
}

Nie widzę tam potrzeby używania tego typu funkcji. Przy czym jeśli chcesz zamieniać miejscami całe węzły, to przygotuj się na to, że funkcja swap spuchnie tak ze cztery razy. Ale po raz kolejny przypominam – nie ma to żadnego sensu, bo w quick sorcie swap samych danych jest rozwiązaniem sensownym i optymalnym.

i proponowana zmiana wystarczy aby działała także dla list dwukierunkowych

Pokaż mi cały kod quick sorta na liście dwukierunkowej, nie merge sorta.

Kiedyś wyśmiewałeś to iterowanie wskaźników

Daj linka, bo nie przypominam sobie, abym ogólnie wyśmiewał jedyną możliwość przeglądania list. Zobaczymy co pisałem i w jakim kontekście.

Poza tym w dalszym ciągu uważam, że iterowanie po całej liście tylko po to, aby zwrócić wskaźnik na ostatni węzeł jest nadmiarowe. Zawsze utrzymuję, aby listę opisywać dwoma wskaźnikami – na głowę i na ogon – po to, aby nie tracić czasu na zbędne czynności.

Próbujesz wyśmiać nazewnictwo z tym też do Ricardo

Jeśli nazewnictwo elementów kodu jest złe, to jest złe i kropka. Pascal ma swoją konwencję nazewnictwa i każdy powinien się jej trzymać. A każdy fragment kodu jaki podałeś w tym wątku, mniej lub bardziej łamie te zasady.

Poza tym samo formatowania kodu nie jest jednolite – masz randomowe wcięcia i randomowo wstawiasz odstępy przed i po identyfikatorach, operatorach i innych specjalnych znakach (np. nawiasach).


Reszty posta nie komentuję, bo nie dotyczy ona pierwotnego problemu.

2

Dobra, odwaliłem robotę za Ciebie – niżej masz port dla Free Pascala, cały program testowy wrzucam na pastebin:

type
  TData = Integer;
  PData = ^TData;

type
  PNode = ^TNode;
  TNode = record
    Next: PNode;
    Prev: PNode;
    Data: PData;
  end;

type
  PList = ^TList;
  TList = record
    Head: PNode;
    Tail: PNode;
  end;

  procedure SwapNodesData(var ALow, AHigh: PData);
  var
    Temp: PData;
  begin
    Temp := ALow;
    ALow := AHigh;
    AHigh := Temp;
  end;

  function GetPivotNode(ALow, AHigh: PNode): PNode;
  var
    Data: PData;
    Left, Right: PNode;
  begin
    Data := AHigh^.Data;
    Left := ALow^.Prev;
    Right := ALow;

    while Right <> AHigh do
    begin
      if Right^.Data^ < Data^ then
      begin
        if Left = nil then
          Left := ALow
        else
          Left := Left^.Next;

        SwapNodesData(Left^.Data, Right^.Data);
      end;

      Right := Right^.Next;
    end;

    if Left = nil then
      Left := ALow
    else
      Left := Left^.Next;

    SwapNodesData(Left^.Data, AHigh^.Data);
    Result := Left;
  end;

  procedure QuickSortList(ALow, AHigh: PNode);
  var
    Pivot: PNode;
  begin
    if (AHigh <> nil) and (ALow <> AHigh) and (ALow <> AHigh^.Next) then
    begin
      Pivot := GetPivotNode(ALow, AHigh);

      QuickSortList(ALow, Pivot^.Prev);
      QuickSortList(Pivot^.Next, AHigh);
    end;
  end;

Listę opisują dwa wskaźniki – na głowę i ogon – zgrupowane w strukturkę, aby nie marnować czasu na szukanie ostatniego węzła listy. Dane przechowywane w węzłach nie mają znaczenia, bo opisuje je wskaźnik, więc czas sortowania nie zależy od objętości danych trzymanych w węzłach. Przykład ten nie pozwala na rozłączanie listy, bo jak wspominałem wcześniej, nie ma to najmniejszego sensu.

Przykładowe wyjście:

before sorting:

from head: 2 9 4 3 9 5 0 7 0 1 4 5 0 1 5 7
from tail: 7 5 1 0 5 4 1 0 7 0 5 9 3 4 9 2

after sorting:

from head: 0 0 0 1 1 2 3 4 4 5 5 5 7 7 9 9
from tail: 9 9 7 7 5 5 5 4 4 3 2 1 1 0 0 0

Kod działa prawidłowo i nie powoduje wycieków pamięci – tu masz test. Nie ma za co.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0