Kol3

Program SortowanieListy;

uses CRT, Math;

type
  ElementP = ^Element;

Element = record
  Nr : integer;
  Wartosc : double;
  Nast : ^Element;
  Pop : ^Element;
end;

//Funkcja wypisujaca liste od wskazanego elementu
function wypiszOd(wsk : ElementP) : ElementP;
begin
  if wsk <> NIL then
  begin
    Writeln('Nr: ', wsk^.Nr, '  Warosc: ', wsk^.Wartosc:5:1);
    while wsk^.Nast <> NIL do
    begin
      wsk := wsk^.Nast;
      Writeln('Nr: ', wsk^.Nr, '  Warosc: ', wsk^.Wartosc:5:1);
    end;
  end;
end;

//Funkcja dodajaca element po wskazanym
function dodajPo(var wsk : ElementP) : ElementP;
var nowy : ElementP;
begin
  if wsk = NIL then
  begin
    new(wsk);
    wsk^.Nast := NIL;
    wsk^.Pop := NIL;
    dodajPo := wsk;
  end else
  begin
    new(nowy);
    nowy^.Pop := wsk;
    nowy^.Nast := wsk^.Nast;
    wsk^.Nast := nowy;
    dodajPo := nowy;
  end;
end;

//Funkcja dodajaca element na koncu
function dodajK(var wsk : ElementP) : ElementP;
var pomocniczy : ElementP;
begin
  if wsk = NIL then
  begin
    dodajPo(wsk);
    dodajK := wsk;
  end
  else begin
    //Wskaznik pomocniczy jest nam potrzebny, by nie zmienic ustawienia wskaznika przekazanego do funkcj
    pomocniczy := wsk;

    //Szukamy ostatniego elementu
    while pomocniczy^.Nast <> NIL do
    begin
      pomocniczy := pomocniczy^.Nast;
    end;

    //Dla niego wywolujemy funkcje dodajace element po wskazanym
    pomocniczy := dodajPo(pomocniczy);
    dodajK := pomocniczy;
  end;
end;

Function zamienE(wsk1, wsk2 : ElementP) : ElementP;
var przejscie1, przejscie2 : ElementP; czySasiaduja : boolean;
begin
  //Sprawdzamy, czy elementy ze soba somsiaduja
  czySasiaduja := (wsk1^.Nast <> wsk2) and (wsk1^.Pop <> wsk2);

  //Dbamy o elementy dalsze:
  if wsk1^.Pop <> NIL then wsk1^.Pop^.Nast := wsk2;
  if wsk2^.Nast <> NIL then wsk2^.Nast^.Pop := wsk1;

  //Gdy elementy ze soba nie sasiaduja:
  if czySasiaduja then
  begin
    if wsk1^.Nast <> NIL then wsk1^.Nast^.Pop := wsk2;
    if wsk2^.Pop <> NIL then wsk2^.Pop^.Nast := wsk1;
  end;

  //Zachowujemy wskaznik do nastepnego elementu:
  przejscie1 := wsk1^.Nast;
  //Writeln('Nr: ', pomocniczy^.Nr, '  Warosc: ', pomocniczy^.Wartosc:5:1);

  //Zachowujemy to, co bedziemy zmieniali:
  //przejscie3 := pomocniczy^.Pop;
  przejscie2 := wsk1^.Pop;

  if czySasiaduja then wsk1^.Pop := wsk2^.Pop else wsk1^.Pop := wsk1^.Nast;

  wsk1^.Nast := wsk2^.Nast;
  //Writeln('Nr: ', pomocniczy^.Nr, '  Warosc: ', pomocniczy^.Wartosc:5:1);

  if czySasiaduja then
  begin
    wsk2^.Pop := przejscie2;
    wsk2^.Nast := przejscie1;
  end else
  begin
    przejscie1^.Nast := wsk1;
    przejscie1^.Pop := przejscie2;
  end;

  zamienE := wsk2;
end;


Function wstawPrzedE(wsk1, wsk2 : ElementP) : ElementP;
var przejscie1, przejscie2 : ElementP; czySasiaduja : boolean;
begin
  //Dbamy o elementy dalsze:
  if wsk1^.Pop <> NIL then wsk1^.Pop^.Nast := wsk2;

  //Dbamy o elementy dalsze:
  if wsk2^.Pop <> NIL then wsk2^.Pop^.Nast := wsk2^.Nast;
  if wsk2^.Nast <> NIL then wsk2^.Nast^.Pop := wsk2^.Pop;

  wsk2^.Nast := wsk1;
  wsk2^.Pop := wsk1^.Pop;

  wsk1^.Pop := wsk2;

  wstawPrzedE := wsk2;
end;

//Funkcja sortujaca elementy listy wzgledem pola 'Wartosc' poczynajac od wskazanego elementu
function SortujBL(wsk : ElementP) : ElementP;
var i : integer; pomocniczy, przejscie1, przejscie2, pierwszy, ostatni : ElementP;
begin
  ostatni := NIL;
  pierwszy := wsk;

  while pierwszy <> ostatni do
  begin
    pomocniczy := pierwszy;
    ostatni := pierwszy;
    i := 0;

    while (pomocniczy^.Nast <> NIL) do
    begin
      if pomocniczy^.Nast^.Wartosc < pomocniczy^.Wartosc then
      begin

        if i = 0 then pierwszy := pomocniczy^.Nast;

        //Zamieniamy elementy:

        //Dbamy o elementy dalsze:
        if pomocniczy^.Pop <> NIL then pomocniczy^.Pop^.Nast := pomocniczy^.Nast;
        if pomocniczy^.Nast^.Nast <> NIL then pomocniczy^.Nast^.Nast^.Pop := pomocniczy;

        //Zachowujemy wskaznik do nastepnego elementu:
        przejscie1 := pomocniczy^.Nast;
        //Writeln('Nr: ', pomocniczy^.Nr, '  Warosc: ', pomocniczy^.Wartosc:5:1);

        //Zachowujemy to, co bedziemy zmieniali:
        //przejscie3 := pomocniczy^.Pop;
        przejscie2 := pomocniczy^.Pop;

        pomocniczy^.Pop := pomocniczy^.Nast;
        pomocniczy^.Nast := pomocniczy^.Nast^.Nast;
        //Writeln('Nr: ', pomocniczy^.Nr, '  Warosc: ', pomocniczy^.Wartosc:5:1);

        przejscie1^.Nast := pomocniczy;
        przejscie1^.Pop := przejscie2;
        //Writeln('Nr: ', pomocniczy^.Nr, '  Warosc: ', pomocniczy^.Wartosc:5:1);

        //Tak jakby flaga chyba:
        ostatni := pomocniczy;
      end else if pomocniczy^.Nast <> NIL then pomocniczy := pomocniczy^.Nast;

      Inc(i);
    end;

    {Writeln();
    wypiszOd(pierwszy);
    Writeln('pierwszy--->Nr: ', pierwszy^.Nr, '  Warosc: ', pierwszy^.Wartosc:5:1);
    Writeln('ostatni--->Nr: ', ostatni^.Nr, '  Warosc: ', ostatni^.Wartosc:5:1);
    Readln(i);}
  end;

  sortujBL := pierwszy;
end;


//Funkcja sortujaca liste przez wstawianie:
Function SortujPrzezWstawianie(wsk : ElementP; dlugoscL : integer) : ElementP;
var i, j : integer; poczatek, pomocniczy1, pomocniczy2, pomocniczy3 : ElementP;
begin
  poczatek := wsk;
  i := 0;

  while i <= dlugoscL do
  begin
    j := 0;

    pomocniczy1 := wsk;
    pomocniczy2 := wsk^.Nast;

    pomocniczy3 := NIL;

    while j < i do
    begin
      pomocniczy1 := pomocniczy1^.Pop;
      if pomocniczy1^.Wartosc > wsk^.Wartosc then pomocniczy3 := pomocniczy1;

      Inc(j);
    end;

    //Jesli znalexlismy element o mniejszej wartosci to zamieniamy:
    if pomocniczy3 <> NIL then
    begin
      if pomocniczy3 = poczatek then poczatek := wsk;
      wstawPrzedE(pomocniczy3, wsk);
    end;

    Inc(i);
    wsk := pomocniczy2;
  end;

  SortujPrzezWstawianie := poczatek;
end;


//Funkcja sorujaca liste przez wybieranie:
Function sortujPrzezWybieranie(wsk : ElementP; dlugoscL : integer) : ElementP;
var i, j : integer; poczatek, pomocniczy1, pomocniczy2, pomocniczy3, pomocniczy4 : ElementP;
begin
  poczatek := wsk;
  i := 0;

  while i < dlugoscL - 1 do
  begin
    j := i;

    pomocniczy1 := wsk;
    pomocniczy2 := wsk^.Nast;

    //najmniejszy element:
    //na poczatku wskaznik ustawiamy na pierwszym z przeszykiwanych elementow:
    pomocniczy3 := pomocniczy1;
    Inc(j);

    pomocniczy4 := pomocniczy3;

    //Szukamy najmniejszego elementu:
    while j < dlugoscL do
    begin
      pomocniczy4 := pomocniczy4^.Nast;
      if pomocniczy3^.Wartosc > pomocniczy4^.Wartosc then pomocniczy3 := pomocniczy4;
      //Writeln('pierwszy--->Nr: ', pomocniczy4^.Nr, '  Warosc: ', pomocniczy4^.Wartosc:5:1);
      Inc(j);
    end;

    //Jesli znalexlismy element o mniejszej wartosci to zamieniamy:
    if pomocniczy3 <> NIL then
    begin
      if wsk = pomocniczy3 then wsk := wsk^.Nast;
      //Writeln('pierwszy--->Nr: ', wsk^.Nr, '  Warosc: ', wsk^.Wartosc:5:1);
      //Writeln();
      if wsk <> pomocniczy3 then wstawPrzedE(wsk, pomocniczy3);
      if i = 0 then poczatek := pomocniczy3;
      //wypiszOd(poczatek);
      //Writeln();

    end;

    Inc(i);
    //wsk := pomocniczy2;
  end;

  sortujPrzezWybieranie := poczatek;
end;


//Funkcja usuwajaca jeden, wskazany element listy


//Funkcja usuwajaca cala liste


var
  i : integer;
  poczatek, pomocniczy : ElementP;

begin
  poczatek := NIL;

  Randomize;

  for i := 0 to 20 do
  begin
    pomocniczy := dodajK(poczatek);
    pomocniczy^.Wartosc := Random(100);
    pomocniczy^.Nr := i;
  end;

  wypiszOd(poczatek);

  //poczatek := zamienE(poczatek, poczatek^.Nast^.Nast^.Nast^.Nast);
  //poczatek := SortujPrzezWstawianie(poczatek, 21 - 1);
  //poczatek := wstawPrzedE(poczatek, poczatek^.Nast^.Nast^.Nast^.Nast^.Nast^.Nast^.Nast^.Nast^.Nast^.Nast^.Nast^.Nast^.Nast^.Nast^.Nast^.Nast^.Nast^.Nast^.Nast^.Nast);
  //poczatek := wstawPrzedE(poczatek, poczatek^.Nast^.Nast);
  poczatek := sortujPrzezWybieranie(poczatek, 21);
  Writeln();
  wypiszOd(poczatek);

  //poczatek := SortujBL(poczatek);
  Writeln();

  //wypiszOd(poczatek);

  Readln(i);
end.