C++ - sortowanie elementów listy jednokierunkowej

Dla specjalistów Programowanie
#21

anntoinet napisała mi na PW prośbę o wyjaśnienie algorytmu. Postanowiłem jednak odpowiedzieć tu bo może się to przydać również innym.

Rospisałem trochę kod i dodałem komentarze(na forum wygląda troche nieczytelnie, lepiej wkleić w jakiś edytor z kolorowaniem składni)

void sortuj(SLista* &lista) //wskaźnik do początku listy przekazywany jest przez referencję, to znaczy, że funkcja może modyfikować zmienną wskaźnikową znajdującą się na zewnątrz niej

{

   SLista* posortowana = 0; //lista posortowana jest początkowo pusta

   while(lista != 0) //elementy będą przenoszone z pierwotnej listy do posortowanej, dopóki pierwotna lista nie jest pusta

   {

      SLista *max = lista, //przyjmujemy na początek, że największym elementem jest pierwszy

             *przed_max = 0; //ponieważ lista jest jednokierunkowa to musimy zapamiętać też wskaźnik na poprzedni element

                             //przed pierwszym elementem nie ma innego elementu, dlatego pusty wskaźnik

      for(SLista *p = lista, *i = lista->next; // (i) przeszukiwanie zaczynamy od drugiego elementu bo pierwszy już został uznany tymczasowo za największy

                                               // (p) potrzebny jest też wskaźnik do poprzedniego elementu, przed drugim elementem znajduje się pierwszy element ;)

         i != 0; //dopóki nie dojdziemy do końca listy

         p = i, i = i->next) //obecny element staje się poprzednim, a następny obecnym

      {

         if(i->x2 >= max->x2) //jeśli obecny element jest wiekszy lub równy od poprzednio uznanego za największy

         {

            max = i; //to uznajemy obecny za największy

            przed_max = p; //i zapamiętujemy też jego poprzednika

         }

      }

      //usuwanie największego z pierwotnej listy

      if(przed_max != 0) //jeśli jest element poprzedni względem największego

         przed_max->next = max->next; //to jako następnik poprzednika ustawiamy następnik naszego największego, największy element już nie należy do pierwotnej listy

      else //element nie ma poprzednika tylko jeśli jest pierwszy

         lista = max->next; //więc jako początek pierwotnej listy ustawiamy drugi element; może być też 'lista = lista->next;' bo w tym przypadku max jest równe lista

      //wstawienie największego elementu na początek posortowanej listy

      max->next = posortowana; //następnikiem najwiekszego będzie obecny pierwszy posortowanej

      posortowana = max; //a na początek posortowanej ustawimy nasz największy

   }

   lista = posortowana; //na koniec jako początek listy ustawiamy początek posortowanej

}

Jest to właściwie ten sam algorytm, którego opis podałaś w pierwszym poście. Ogólnie taka metoda nazywa się sortowaniem przez wybór.

Ponieważ kolejne elementy dodawane są na początek listy posortowanej to trafiają tam w odwrotnej kolejności.

W wyszukiwaniu największego elementu jest warunek “większy lub równy”, przez co wybierany jest ostatni największy, dzięki czemu elementy o tej samej wartości znajdują się w liście posortowanej w tej samej kolejności w jakiej znajdowały się w pierwotnej (sortowanie stabilne). Gdyby był użyty warunek “większy” to elementy o tej samej wartości byłyby w odwrotnej kolejności (ogólnie gdy elementy o tej samej wartości po posortowaniu mogą znajdować się w innej kolejności to sortowanie określa się jako niestabilne).

Gdyby kolejne elementy były dodawana na koniec listy posortowanej to należałoby wyszukiwać najmniejszy element aby lista była sortowana rosnąco.

#22

Rolek0 , dziękuję Ci serdecznie za pomoc i tak szczegółowe rozpisanie algorytmu. Program działa jak należy, a co najważniejsze teraz już rozumiem krok po kroku schemat postępowania i wiem co z czego wynika. Jeszcze raz wielkie dzięki!

#23

I tu grubo się mylisz, nie dasz rady tego powtórzyć bez podglądania.

#24

Niech zgadnę schemat postępowania pochodzi z forum elektroda.pl

Jeśli rekurencja to ogonowa - według mnie jest to zapis pętli w tym schemacie

Tutaj koleś nawet nie czytał wpisu tej anntoinet

“Rozdziel problem na mniejsze problemy.”

Właśnie rozdzieliła podając schemat

“Najpierw sobie dopisz do swojej struktury danych (listy jednokierunkowej) metodę zamiany elementów na liście”

Po co jej była zamiana elementów skoro ze schematu wynika że miała użyć

1 - wyszukiwania elementów
(tutaj największego - przy czym wyszukiwanie powinno odbywać się dwoma wskaźnikami
bo będziemy potrzebować także poprzednika szukanego elementu)
2 - operacji wstawiania (tutaj wystarczy wstawianie na początek)
3 - operacji usuwania

Ciekawe dlaczego alex twierdzi że nie dałaby rady tego mapisać bez podglądania

Mnie też programowanie aż tak dobrze nie wychodzi ale wydaje mi się że mógłbym
skomentować sortowanie listy przez wstawianie

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

procedure initialize(var L:PNode);
begin
  L := NIL;
end;

function isEmpty(L:PNode):boolean;
begin
  isEmpty:=L = NIL;
end;

procedure push(var L:PNode;k:TKey);
var x:PNode;
begin
  new(x);
  x^.key := k;
  x^.next := L;
  L := x;
end;

procedure pop(var L:PNode);
var x:PNode;
begin
  if L <> NIL then
  begin
    x := L;
    L := L^.next;
    dispose(x);
  end;
end;


procedure insertionSort(var L:PNode);
var h, x, xs, y, z:PNode;
begin
  (* Wskaźnik pokazujący na głowe posortowanej listy 
   na razie ustawiamy go na NIL *)
  h := NIL;
  (*wskaźnik do przeglądania sortowanej listy*) 
  x := L;
  while x <> NIL do
  begin
    (*Zapamiętujemy wskaźnik następnika ponieważ będzie 
     on modyfikowany podczas wstawiania i moglibyśmy go 
     zgubić gdybyśmy go nie zapamiętali*)
    xs := x^.next;
    (*Inicjujemy wskaźniki użyte do znalezienia miejsca w które 
      chcemy wstawić węzeł listy *)                  
    y := h;
    z :=NIL;
    while (y <> NIL)and(x^.key > y^.key)do
    begin
      z := y;
      y := y^.next;
    end;
    (*Ustawiamy następnik wstawianemu elementowi*)
    x^.next := y;
    (* Sprawdzamy czy poprzednik pokazuje na jakiś węzeł 
      Jeśli tak to ustawiamy poprzednikowi następnik 
      będzie to wstawiany węzeł,
       w przeciwnym razie wstawiamy węzeł na początek listy *)
    if z <> NIL then
      z^.next := x
    else
      h := x;
    (* Pobieramy następnik sortowanej listy, 
         Mamy do niego dostęp ponieważ go zapamiętaliśmy*)
    x := xs;
  end;
  (* Przypisujemy głowie listy sortowanej głowę listy posortowanej
      To jest nadal ta sama lista tyle że z przestawionymi wskaźnikami *)
  L := h;
end;


procedure printNodes(L:PNode);
var x:PNode;
begin
  x := L;
  while x <> NIL do
  begin
    write(x^.key,' ');
    x := x^.next;
  end;
  writeln;
  writeln;
end;

var L:PNode;
    k:TKey;
    ch:integer;
    esc:char;

begin
  clrscr;
  Initialize(L);
  repeat
    writeln('1. Wstaw element na poczatek listy');
    writeln('2. Usun element z poczatku listy');
    writeln('3. Posortuj liste ');
    writeln('4. Wypisz elementy listy');
    readln(ch);
    case ch of
      1:
      begin
        writeln('Podaj jaki element chcesz wstawic');
        readln(k);
        push(L,k);
      end;
      2:
      begin
        pop(L);
      end;
      3:
      begin
        insertionSort(L);
      end;
      4:
      begin
        printNodes(L);
      end
      else
        writeln('Brak operacji');
    end;
    esc := readkey;
  until esc = #27;
end.
#25

Ładny odkop, ale jeszcze nie rekordowy :slight_smile: Co najwyżej brązowa łopata