MergeSort - przepisanie funkcji rekurencyjnej na postać iteracyjną

0
 struct node* SortedMerge(struct node* a, struct node* b)
{
  struct node* result = NULL;
 
  /* Base cases */
  if (a == NULL)
     return(b);
  else if (b==NULL)
     return(a);
 
  /* Pick either a or b, and recur */
  if (a->data <= b->data)
  {
     result = a;
     result->next = SortedMerge(a->next, b);
  }
  else
  {
     result = b;
     result->next = SortedMerge(a, b->next);
  }
  return(result);
}
 

Jak przepisać tę funkcję iteracyjnie ?
Iteracyjna wersja powinna zachować dość ważną własność algorytmu jaką jest stabilność
Dobrze by było wywalić obecnie zwracaną wartość do listy parametrów
Łatwiej mi byłoby wtedy przepisać ten kod na inny język

0

Trochę dziwne te twoje sortowanie przez scalanie, ani zbioru nie dzielisz, ani nie scalasz, tylko co najwyżej zamieniasz miejscami sąsiadujące elementy.
Jak chcesz normalnie posortować listę to zacznij od sortowania bąbelkowego:
https://4programmers.net/Forum/C_i_C++/264087-sortowanie_listy_jednokierunkowej_c
ewentualnie poszukać innej metody sortowania.
Jeśli jednak się upierasz na sortowanie przez scalanie to algorytm znajdziesz tutaj:
http://eduinf.waw.pl/inf/alg/001_search/0097.php
Ale raczej wątpię żeby ktoś przepisał iteracyjnie algorytm sortowania przez scalanie (a nawet jak się da to nawet nie wiem po co) który w dodatku nie działa.

0

@nowy121105 co to pokazałeś to jest jakiś rekurencyjny bubble sort. Generalnie masakra i z merge sortem nie ma nic wspólnego. Merge sort polega na:

  1. Podziel tablicę na 2 części
  2. Posortuj każdą część osobno merge sortem
  3. Scal obie części

Porównaj to z tym co napisałeś...

0

To jest tylko funkcja scalająca dwie posortowane listy ale napisana w sposób rekurencyjny
i właśnie chciałbym aby to ona była przepisana na postać iteracyjną
Funkcje dzielącą i sortującą rekurencyjne mam napisane
Po co przepisywać na algorytm iteracyjny - np po to aby uniknąć korzystania ze stosu albo aby pominąć etap dzielenia
ale wystarczy mi przepisanie tej funkcji w sposób iteracyjny tak aby była zachowana oryginalna kolejność powtarzających się kluczy

@czaffik widziałem ten kod Wałaszka i byłby nawet niezły gdyby nie zastosowanie wartownika co może przeszkadzać

Funkcja dzieląca u Wałaszka jest tak napisana że powoduje niestabilność algorytmu

0

Scalanie iteracyjne:

  • dopóki któraś lista nie jest pusta
    • porównaj pierwsze elementy obu list
    • mniejszy element przepnij do listy wynikowej
    • przesuń sie na kolejny element listy z której odpinałeś
  • jeśli jedna z listy jest pusta, przepnij pozostałość drugiej listy na koniec listy wynikowej
0
type tline=
          record
                number:integer;
                line:string;
          end;
    PNode=^TNode;
    TNode=
          record
                data:tline;
                next:PNode;
          end;

function sortedMerge(a:PNode;b:PNode):PNode;
var result:PNode;
    begin
     result:=nil;
     while ((a<>nil)and(b<>nil)) do
     begin
          if(a^.data.number<=b^.data.number) then
          begin
               result:=a;
               a:=a^.next;
          end
          else
          begin
               result:=b;
               b:=b^.next;
          end;
          result:=result^.next;
     end;
     if(a=nil) then result:=b
     else result:=a;
     sortedMerge:=result;
end;

Wynik działania tej funkcji wygląda tak jakby w pętli while przesuwał tylko wskaźniki łączonych list
natomiast nie przypisywał wskaźnikowi result żadnej wartości
Ta ostatnia instrukcja warunkowa if wygląda jakby działała dobrze

0
type
  PNode = ^TNode;
  TNode = record
    Data: record
      Number: Integer;
      Line: String;
    end;
    Next: PNode;
  end;

Krótszy zapis, a w działaniu identyczny - i tak nie używasz osobno rekordów typu TLine, więc typ ten jest zbędny; W przeciwnym razie zignoruj powyższe;

var result:PNode;

Co to do licha? Nie wiesz, że każda funkcja posiada ukrytą zmienną Result?

Poprawiony (a raczej sformatowany) kod niżej:

function MergeSort(A, B: PNode): PNode;
begin
  while ((A <> nil) and (B <> nil)) do
  begin
    if (A^.Data.Number <= B^.Data.Number) then
    begin
      Result := A;
      A := A^.Next;
    end
    else
    begin
      Result := B;
      B := B^.Next;
    end;

    Result := Result^.Next;
  end;

  if (A = nil) then
    Result := B
  else
    Result := A;
end;

Teraz już można się bawić w szukanie błędów.

0

Z twojej pierwszej uwagi chyba nie skorzystam bo procedury wstawiające ,usuwające itp miałyby więcej parametrów
Z tą zmienną result to w środowiskach które używam twój pomysł daje idenifier not found result (w tych w których zadziała będę tego używał)
To jest tylko procedura scalająca dwie posortowane listy więc czy nie będzie kolizji nazw z procedurą sortującą ?

Próbowałem zapisać ten opis algorytmu który podał Shalom i ne wiem dlaczego kod nie działa jak powinien

 struct Node
{
    int data;
    struct Node* next;
};
 struct Node* SortedMerge(struct Node* a,struct Node* b)
{
    struct Node* result=NULL;
    while(a!=NULL&&b!=NULL)
    {
        if(a->data<=b->data)
        {
            result=a;
            a=a->next;
        }
        else
        {
            result=b;
            b=b->next;
        }
        result=result->next;
    }
    if(a==NULL) result=b;
    else result=a;
    return result;
}
0

Z twojej pierwszej uwagi chyba nie skorzystam bo procedury wstawiające ,usuwające itp miałyby więcej parametrów

Pozostałych procedur nie podałeś, więc to była luźna sugestia i przyznam szczerze, że nie wiem w jaki sposób złączenie dwóch rekordów miało by wydłużyć listy parametrów; Ale to nieważne;

Z tą zmienną result to w środowiskach które używam twój pomysł daje idenifier not found result [...]

Strach zapytać się w czym piszesz ten kod, skoro ta zmienna istniała już w ubiegłym tysiącleciu...

[...] (w tych w których zadziała będę tego używał)

Wystarczy Lazarus - nawet jakiś bardzo stary, skoro czegoś nowego nie chcesz/nie możesz użyć;

To jest tylko procedura scalająca dwie posortowane listy więc czy nie będzie kolizji nazw z procedurą sortującą ?

To nazwij je odpowiednio - nie będzie problemu; Poza tym w życiu bym nie wpadł na to, że ta procedura ma scalać dwie listy... W każdym razie potrzebujesz:

  • znaleźć ostatni węzeł listy A (z zachowaniem A),
  • do A^.Next wpisać B,
  • zwrócić A (nietknięte przez iterację);

Teraz zobacz co Twój kod robi i zastanów się dlaczego dzieją się cuda; Funkcja scalająca dwie listy jednokierunkowe i zwracająca głowę scalonej listy, powinna wyglądać tak jak poniżej (kod dla FPC):

function MergeLists(A, B: PNode): PNode;
begin
  if A = nil then Exit(B);
  if B = nil then Exit(A);
  
  Result := A;
  
  while Result^.Next <> nil do
    Result := Result^.Next;
    
  Result^.Next := B;
  Result := A;
end;

To powinno bez problemu działać - w razie czego dodeklaruj sobie Result, jeśli w standardzie go nie masz.

0

Tak ale scalona lista ma także być posortowana
Chodzi o zapisanie algorytmu którego kroki podał Shalom w języku programowania takim jak Pascal czy C
Jak widać próbowałem w pętli while dać warunek if w którym następuje wybieranie elementów do scalonej listy a gdy wybierzemy wszystkie elementy z jednej z list to dołączamy elementy listy która została
elementy z pozostałej listy

0

Tak ale scalona lista ma także być posortowana

Napisałeś, że:

To jest tylko procedura scalająca dwie posortowane listy więc czy nie będzie kolizji nazw z procedurą sortującą ?

więc przyjąłem, że procedurka ma połączyć dwie listy, bez sortowania; W takim razie trzeba się za to zabrać zupełnie z innej strony; Choć równie dobrze mógłbyś połączyć te dwie listy tak jak pokazałem, a jak już je połączysz to posortować same dane, bez ruszania struktury listy (węzłów).

1

Piszę jako nowy post, coby było wiadomo, że coś się w wątku dzieje; Miałem chwilkę, więc zmierzyłem się z problemem;

Podana niżej funkcja działa prawidłowo - przynajmniej nie udało mi się wykazać, że scala i/lub sortuje błędnie; Można do niej podać dwie dowolne listy - obie niepuste, jedną pustą a drugą nie, a także obie puste, w każdym przypadku działa prawidłowo; Poniżej kod dla FPC:

function MergeLists(ALeft, ARight: PNode): PNode;
var
  LLast: PNode;
begin
  if ALeft  = nil then Exit(ARight);
  if ARight = nil then Exit(ALeft);

  if ALeft^.Data < ARight^.Data then
  begin
    LLast := ALeft;
    ALeft := ALeft^.Next;
  end
  else
  begin
    LLast := ARight;
    ARight := ARight^.Next;
  end;

  Result := LLast;

  while (ALeft <> nil) and (ARight <> nil) do
  begin
    if ALeft^.Data < ARight^.Data then
    begin
      LLast^.Next := ALeft;
      ALeft := ALeft^.Next;
    end
    else
    begin
      LLast^.Next := ARight;
      ARight := ARight^.Next;
    end;

    LLast := LLast^.Next;
  end;

  if ALeft <> nil then
    LLast^.Next := ALeft
  else
    LLast^.Next := ARight;
end;

  1. Pierwsze dwa warunki służą do sprawdzenia, czy któraś lista jest pusta i jeśli tak - zwracają tę drugą; Jeśli obie są puste to funkcja zwraca nil;
  2. Kolejny warunek służy do określenia głowy nowej listy; W warunku tym sprawdzane jest to który węzeł posiada mniejszą wartość i jego pointer określany jest jako bieżący (LCurr);
  3. Do Result wpisywany jest wskaźnik na pierwszy węzeł listy (pozyskanu w poprzednim punkcie) - to jest konieczne, bo funkcja musi zwrócić wskaźnik na głowę połączonej listy, dlatego zostaje on zapamiętany;
  4. Właściwa pętla while - w niej wykonywane jest porównywanie danych węzłow i odpowiednie przerzucanie ich do nowej listy; Pętla działa do opróżnienia całej jednej listy (dowolnej);
  5. Ostatnia drabinka ifów służy do sprawdzenia, która lista jeszcze nie została opróżniona i tę resztkę doczepia na koniec listy wynikowej; Któryś z tych warunków zawsze zostanie spełniony, dlatego że główna pętla while zawsze opróżnia tylko jedną listę - w tej drugiej pozostaje co najmniej jeden węzeł, więc jego trzeba dokleić;

Cały kod aplikacji testowej znajduje się tutaj - http://ideone.com/1BRqub

W wywołaniach funkcji MergeLists możesz wpisać na sztywno nil zamiast LLeft i/lub LRight, jeśli potrzebujesz samemu sprawdzić jej działanie; W każdym razie to tylko testowy program, więc ewentualnie możesz sobie pozmieniać nazewnictwo identyfikatorów i dostosować kod do własnego typu danych, trzymanych w węzłach;

Testowy program powoduje wycieki pamięci, bo już nie chciało mi się pisać kodu zwalniającego listy;


W C wyglądałoby to mniej więcej tak:

struct node* merge_lists(struct node* left, struct node* right)
{
  if(left == null)  return right;
  if(right == null) return left;
  
  struct node* head, last;
  
  if(left->data < right->data)
  {
    head = last = left;
    left = left->next;
  }
  else
  {
    head = last = right;
    right = right->next;
  }
  
  while(left != null && right != null)
  {
    if(left->data < right->data)
    {
      last->next = left;
      left = left->next;
    }
    else
    {
      last->next = right;
      right = right->next;
    }
    
    last = last->next;
  }
  
  last->next = left != null ? left : right;
  return head;
}

Ale mogę się mylić, bo dawno nie pisałem w tym języku.

0

W sieci znalazłem kiedyś procedury scalające iteracyjnie ale jednia nie zachowywała kolejności powtarzających się kluczy
a druga była podobna do twojej ale bez opisu
O co chodzi z tymi wyciekami pamięci ?
Czy to nie jest tak, że nie tworzymy nowej listy tylko pokazujemy wskaźnikami na te listy których głowy są przekazywane jako parametry do funkcji bądź procedury

0

O co chodzi z tymi wyciekami pamięci ?

Już wyjaśniłem - nie chciało mi się pisać zwalniania zaalokowanej pamięci po listach, stąd wyciek; Ty w swoim programie na pewno masz jakąś funkcję, która zwalnia pamięć po wszystkich węzłach listy, więc nie ma się czym przejmować; To co podałem to na szybko napisana aplikacja testowa, której zadaniem jest jedynie przetestowanie funkcji scalającej i to działa jak najbardziej poprawnie;

Dlatego też możesz sobie skopiować kod funkcji MergeLists/merge_lists, a resztę olej;

Czy to nie jest tak, że nie tworzymy nowej listy tylko pokazujemy wskaźnikami na te listy których głowy są przekazywane jako parametry do funkcji bądź procedury

No dokładnie - na wejściu funkcja dostaje dwie listy już istniejące w pamięci, a na wyjściu wypluwa listę utworzoną z istniejących węzłów; Nie ma w niej alokowania nowej pamięci, a tylko odpowiednie ustawianie pól Next/next w istniejących węzłach;

Natomiast wycieki powstają dlatego, że w mojej testowej aplikacji, w głównym bloku kodu, alokowana jest pamięć dla dwóch list (za pomocą CreateList), w dalszej części listy te są łączone funkcją MergeLists i tyle; Nigdzie nie zapisałem sobie np. funkcji DisposeList, która by zwolniła zaalokowaną pamięć;


Aha, i najważniejsze - po złączeniu list, poprzednie wskaźniki na ich głowy (które przekazałeś do funkcji scalającej) po pierwsze nie są już potrzebne, a po drugie, nie należy ich już używać; To co funkcja wypluje, zawierać będzie prawidłowe wskazania na wszystkie węzły list wejściowych (w postaci jednej listy); Dlatego też pilnuj wskaźnika na wyplutą z funkcji listę i tego wskaźnika użyj do zwolnienia zaalokowanej pamięci;

Dzięki temu będziesz miał pewność, że Twój program nie będzie powodował wycieków.

0

Gdybym chciał wykorzystać tę funkcję do scalania list dwukierunkowych to trzeba by było jeszcze ustawić wskaźniki na poprzedni węzeł ?
Na listach jednokierunkowych procedurę dzielącą piszemy tak że ustawiamy dwa pomocnicze wskaźniki i w każdej iteracji jeden przesuwamy raz a drugi dwa razy
a na listach dwukierunkowych jeden wskaźnik ustawiamy na głowę i przesuwamy wskaźnik pokazujący na następnik a drugi wskaźnik ustawiamy na ogon i przesuwamy wskaźnik pokazujący na poprzednika
dopóki te wskaźniki się nie spotkają

1

Gdybym chciał wykorzystać tę funkcję do scalania list dwukierunkowych to trzeba by było jeszcze ustawić wskaźniki na poprzedni węzeł ?

Tak, w przeciwnym razie prawidłowo działało by jedynie iterowanie po węzłach od głowy do ogona, a iterowanie od ogona do głowy powodowałoby odwiedzanie losowych węzłów i/lub przedwczesne zakończenie iteracji; Jeśli pierwszy węzeł listy wejściowej trafiłby po posortowaniu na koniec listy wyjściowej, tak utworzona lista miałaby tylko jeden element, według iteracji ogonowej;

Na listach jednokierunkowych procedurę dzielącą piszemy tak że ustawiamy dwa pomocnicze wskaźniki i w każdej iteracji jeden przesuwamy raz a drugi dwa razy

Nie wiem co to znaczy, ale brzmi kosmicznie :]

Jeśli chodzi o listy jednokierunkowe to aby podzielić jedną listę na dwie, należy:

  1. zapamiętać wskaźnik na głowę listy wejściowej,
  2. znaleźć węzeł, który będzie ostatnim węzłem pierwszej listy docelowej,
  3. zapamiętać wskaźnik na Next węzła znalezionego w punkcie 2.,
  4. wpisać do Next wartość nil węzła znalezionego w punkcie 2.,
  5. zwrócić wskaźnik na węzeł zapamiętany w punkcie 1., jako wskaźnik na głowę pierwszej listy docelowej,
  6. zwrócić wskaźnik na węzeł zapamiętany w punkcie 3., jako wskaźnik na głowę drugiej listy docelowej;

To tyle - jak widać nie ma tutaj żadnego przesuwania;

a na listach dwukierunkowych jeden wskaźnik ustawiamy na głowę i przesuwamy wskaźnik pokazujący na następnik a drugi wskaźnik ustawiamy na ogon i przesuwamy wskaźnik pokazujący na poprzednika dopóki te wskaźniki się nie spotkają

To też brzmi kosmicznie :]

Dzielenie listy dwukierunkowej jest prawie takie samo jak dzielenie listy jednokierunkowej - z tą różnicą, że potrzebujemy głowie drugiej listy ustawić również Prev na nil; Ogólnie pisząc, lista kroków wygląda jak poniżej, czyli należy:

  1. zapamiętać wskaźnik na głowę listy wejściowej,
  2. znaleźć węzeł, który będzie ostatnim węzłem pierwszej listy docelowej,
  3. zapamiętać wskaźnik na Next węzła znalezionego w punkcie 2.,
  4. wpisać do Next wartość nil węzła znalezionego w punkcie 2.,
  5. wpisać do Prev wartość nil węzła zapamętanego w punkcie 3.,
  6. zwrócić wskaźnik na węzeł zapamiętany w punkcie 1., jako wskaźnik na głowę pierwszej listy docelowej,
  7. zwrócić wskaźnik na węzeł zapamiętany w punkcie 3., jako wskaźnik na głowę drugiej listy docelowej;

Jak sam widzisz, różnicą jest punkt 5., czyli dodatkowe wpisanie nil do Prev zapamiętanego węzła;

Dzięki punktowi 4., pierwsza lista zostanie poprawnie zakończona, a dzięki punktowi 6., głowa drugiej listy nie będzie umożliwiała przeskoczenia do ostatniego węzła tej pierwszej listy, czyli zostanie prawidłowo zapoczątkowana;

Nie ma tutaj potrzeby przesuwania jakichś pomocniczych wskaźników, a tym bardziej przesuwania o dwa pola.

1

A niech stracę - masz prezent:

procedure SplitList(const ALeftHead: PNode; out ARightHead: PNode; ACutAfter: Integer);
var
  LLeftLast: PNode;
begin
  LLeftLast := ALeftHead;

  while ACutAfter > 0 do
  begin
    LLeftLast := LLeftLast^.Next;
    Dec(ACutAfter);
  end;

  ARightHead := LLeftLast^.Next;
  LLeftLast^.Next := nil;
end;

Tak wygląda kod procedury dzielącej jedną listę jednokierunkową na dwie;

W parametrze ALeftHead podaje się głowę listy wejściowej - parametr ten jest automatycznie wskaźnikiem na głowę pierwszej listy docelowej; W argumencie ARightHead podaje się pointer na głowę drugiej listy docelowej, a w ACutAfter indeks węzła, za którym lista zostanie ucięta, a dalsza część wydzielona do drugiej listy;

Powyższy kod nie zawiera zabezpieczeń przed podaniem zbyt dużego indeksu - to sobie dorób, jeśli potrzebujesz; W każdym razie, w ostatnim parametrze podać można indeks od wartości 0 (pierwsza lista otrzyma jeden węzeł, a druga pozostałe) do n-1 (pierwsza lista otrzyma wszystkie węzły, więc nic się nie zmieni), gdzie n to liczba węzłów w liście;

Aplikacja testowa - http://ideone.com/e2G0bX


Jeśli chodzi o podział listy dwukierunkowej to algorytm niewiele się różni od poprzedniego:

procedure SplitList(const ALeftHead: PNode; out ARightHead: PNode; ACutAfter: Integer);
var
  LLeftLast: PNode;
begin
  LLeftLast := ALeftHead;

  while ACutAfter > 0 do
  begin
    LLeftLast := LLeftLast^.Next;
    Dec(ACutAfter);
  end;

  ARightHead := LLeftLast^.Next;
  ARightHead^.Prev := nil;

  LLeftLast^.Next := nil;
end;

Jak widać doszła tylko jedna linijka - wpisanie nil do Prev; Kodu nie ma co drugi raz tłumaczyć, dlatego że implementuje dokładnie to samo co wyżej podany, tyle że dla listy dwukierunkowej; Zakres indeksów możliwych do podania w ostatnim parametrze również jest taki sam;

Dla sprawdzenia poprawności ustawień wskaźników w węzłach, wyświetlanie zawartości listy realizowane jest dwa razy - najpierw iterując od głowy do ogona listy, a następnie (w nowej linii) od ogona do głowy; Wszystko gra - nie ma co rozpisywać się;

Aplikacja testowa - http://ideone.com/eyny7f


Tym razem oba programy testowe sprzątają po sobie i robią to prawidłowo, więc wycieków pamięci ze strony testera nie ma; Sprawdziłem poprawność działania za pomocą modułu HeapTrc i wszystko gra.

0

Ja przepisałem funkcje z geeksforgeeks i tam nie mieli napisanej procedury scalającej w sposób zadowalający

Kody które podałem w poprzednich postach, są według mnie najszybszym możliwym sposobem na podzielenie listy na dwie części oraz na scalenie dwóch list w jedną; Obie można przerobić na procedury operujące na parametrach, albo na funkcje, zwracające dane; Również obie można wyposażyć w dodatkowe zabezpieczenia, ale to robota dodatkowa;

Jak ktoś zna szybsze sposoby dzielenia i scalania list to chętnie się z nimi zapoznam;

Wprowadziłeś zmienną typu całkowitego ?

Tak, bo jej rozmiar nie jest z góry określony - może mieć 32 lub 64 bity, w zależności m.in. od kompilatora; Jak wolisz liczbę naturalną to możesz sobie zmienić typ parametru, np. na UInt32 - kod nie jest na to wrażliwy, dlatego że pętla while nie dopuści do ustawienia indeksu poniżej 0;

Ciekawe czy prędzej przekroczymy zakres typu integer czy prędzej nam się skończy pamięć na węzły

Nie problem policzyć :]

0

Jeśli chodzi o dzielenie to najlepiej podzielić na połowę a w przypadku nieparzystej liczby węzłów jedna podtablica miałaby o jeden element więcej Dlaczego sortowanie przez scalanie ma przewagę nad sortowaniem szybkim , w sortowaniu szybkim może się zdarzyć że większość podziałów będzie dawać podlistę jednoelementową poza tym sortowanie szybkie nie zachowuje kolejności kluczy . W przypadku średnim natomiast niewiele zyskamy na sortowaniu szybkim więc nie wiem czemu większość podnieca się tym sortowaniem szybkim

Jeżeli chodzi o iteracyjną wersję sortowania przez scalanie to z etapu dzielenia podobno można zrezygnować

Z sortowań O(n log n) to znam tylko sortowanie przez scalanie i stogowe , tzw sortowanie szybkie nie zawsze jest O(n log n)
Z czego sortowanie stogowe nadaje się chyba tylko do tablic
Sortowanie stogowe i tzw szybkie stosuje zamianę elementów i dlatego nie zachowuje kolejności kluczy
czy przyczyna takiego zachowania jest inna

0

Jeśli chodzi o dzielenie to najlepiej podzielić na połowę a w przypadku nieparzystej liczby węzłów jedna podtablica miałaby o jeden element więcej

To wiadome, przy czym jeśli lista wejściowa ma nieparzystą liczbę węzłow to siłą rzeczy nie da się jej podzielić na równe połówki; Do dzielenia listy na pół, możesz wykorzystać podany przeze mnie kod - wystarczy w ostatnim parametrze procedury SplitList podać środkowy indeks; W przypadku nieparzystej liczby węzłow wystarczy div;

W przypadku średnim natomiast niewiele zyskamy na sortowaniu szybkim więc nie wiem czemu większość podnieca się tym sortowaniem szybkim

Widać w większości typowych przypadków, sortowanie szybkie jest lepsze, natomiast implementacja algorytmu quick sortu jest o niebo prostsza od sortowania przez scalanie; Może dlatego :]

0

Widziałem że na upartego można napisać sortowanie szybkie dla list mimo iż jest ryzyko że algorytm zwolni do O(n^2) bo Σ_{k=0}^{n-1}k jest O(n^2)
Taka sytuacja wystąpi gdy większość podziałów da podlistę jednoelementową

"

Aha, i najważniejsze - po złączeniu list, poprzednie wskaźniki na ich głowy (które przekazałeś do funkcji scalającej) po pierwsze nie są już potrzebne, a po drugie, nie należy ich już używać; To co funkcja wypluje, zawierać będzie prawidłowe wskazania na wszystkie węzły list wejściowych (w postaci jednej listy); Dlatego też pilnuj wskaźnika na wyplutą z funkcji listę i tego wskaźnika użyj do zwolnienia zaalokowanej pamięci;

Dzięki temu będziesz miał pewność, że Twój program nie będzie powodował wycieków"

Myślałem że aby nie było wycieków pamięci wystarczy dla każdego wywołania procedury new wystarczy wywołać odpowiadającą jej procedure dispose
dlatego napisałem że w procedurze scalającej nie tworzymy nowej listy tylko ustawiamy wskaźniki na elementy list już istniejących

Z sortowań to jeszcze zostało sortowanie plików

0

Tak wlasciwie najwazniejsze w tym algorytmie bylo usuniecie rekurencji z procedury scalajacej bo to ona najbardziej obciazala stos (stwarzala ryzyko jego przepelnienia)
i wpis furiousa z 2016-12-22 00:51 tak wlasciwie rozwiazal problem dla list jednokierunkowych
W pozniejszych wpisach dal on tez kilka wskazowek jak zmodyfikowac kod aby dzialal tez dla list dwukierunkowych
Wpisy furiousa byly jak dotad pomocne

Funkcja sortujaca mimo iz takze jest rekurencyjna nie obciazy juz tak stosu jednak w pewnych sytuacjach wygodniejsza bedzie wersja iteracyjna algorytmu

Myslalem nad laczeniem naturalnym

Tutaj takze mielibysmy trzy procedury
Procedura rozdzielajaca serie na przemian pomiedzy dwie pomocnicze listy
Procedura laczaca serie z dwoch pomocniczych list
Procedura sortujaca

Jesli chodzi o wykrycie konca serii to przegladac liste z uzyciem dwoch wskaznikow (porownujac klucz z poprzedniego wezla z kluczem z biezacego wezla)
czy przegladac liste z uzyciem jednego wskaznika (porownujac klucz z biezacego wezla z kluczem z nastepnego wezla)

Jesli chodzi o procedure scalajaca to wyglada na to ze bedzie ona nieco bardziej skomplikowana niz w przypadku algorytmu rekurencyjnego
bo oprocz scalania dwoch list scala tez serie w tych listach

Ciekaw jestem waszych pomyslow

0
nowy121105 napisał(a):

Tak wlasciwie najwazniejsze w tym algorytmie bylo usuniecie rekurencji z procedury scalajacej bo to ona najbardziej obciazala stos (stwarzala ryzyko jego przepelnienia)

Każda funkcja/procedura rekurencyjna stwarza ryzyko przepełnienia stosu, bo go po prostu używa. Jeśli piszesz jakikolwiek algorytm rekurencyjny to zwróć uwagę na to ile danych na stosie ląduje i jeśli jest ich mnóstwo (wiele parametrów, przekazywanie przez wartość (sic!), tysiące rekurencyjnych wywołań) to zmień kod na iteracyjny (albo zoptymalizuj to co masz).

Nie ma też co robić w portki – żeby stos przepełnić to trzeba tego chcieć (albo nie wiedzieć co się robi).

W pozniejszych wpisach dal on tez kilka wskazowek jak zmodyfikowac kod aby dzialal tez dla list dwukierunkowych

Ilość ”kierunków” listy nie ma znaczenia w tym przypadku – to i tak wewnętrzne mechanizmy kontenera, sam algorytm sortujący nie ma do nich dostępu. o chyba że implementacja listy jest po prostu kupką globali (zmiennych i funkcji) to wtedy będzie lipa. Lista powinna być w coś opakowana (np. w klasę), tak aby móc jej normalnie używać, bez martwienia się o jej konstrukcję.

Jesli chodzi o procedure scalajaca to wyglada na to ze bedzie ona nieco bardziej skomplikowana niz w przypadku algorytmu rekurencyjnego bo oprocz scalania dwoch list scala tez serie w tych listach

Zaimplementuj listę jako klasę i używaj jej w ludzki sposób, a nie będziesz miał z niczym problemu. W przeciwnym razie będziesz musiał dłubać we wskaźnikach, zamiast zająć się poprawnością algorytmu sortującego.

0

Widzialem jak jeden nakrecil filmik o sortowaniu listy przez scalanie
(koles prawdopodobnie podejrzal kod od geeksow bo geeksy maja zblizony kod)
i jeden z widzow stwierdzil ze przy sortowaniu 1000 czy nawet 100000 wezlow dziala mu ok
a przy sortowaniu wiekszej liczby wezlow funkcja scalajaca przepelnia mu stos

Ponizsze zadania sprowadzaja sie do sortowania

  1. Mamy liste A oraz liste B
    Chcemy wypisac dane ktore znajduja sie na liscie A ale nie znajduja sie na liscie B

Tutaj rekurencyjna procedura sortujaca przez scalanie powinna wystarczyc

  1. Otoczka wypukla zbioru punktow plaszczyzny

Tutaj porownujemy polozenie dwoch punktow wzgledem trzeciego punktu i procedura iteracyjna moze byc wygodniejsza w uzyciu
Calkiem zgrabny pseudokod algorytmu Grahama jest u Cormena i reszty

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