{ BubbleSort - DEMO fuer Datenstrukturen Vorlesung, SS03-Benn }
{ Autor: Dipl.-Ing. Thomas Speiser                            }
{ Source from: http://Codes.TurboTools.de                     }

{ BubbleSort auf einfach verkettete Listen                    }
{ DUMMY-Element eingefuegt, welches auf Kopfelement zeigt     }

program bubble_sort_demo;
uses Crt;
const n = 8;

type zeiger = ^element;
     element = record
      data: integer;
      next: zeiger;
     end;

var p: zeiger;
    d1,d2: integer;                    { Anzahl der Durchlaeufe }

procedure Out_List(p: zeiger);
begin
while (p <> nil) do begin
write('p: ',p^.data);
write(' -> ');
p:=p^.next;
end;
if p = nil then write('nil');
writeLN;
end;

{ STANDARD-Proceduren }
function Is_Empty(p: zeiger): boolean;
begin
is_Empty:=(p = nil);
{ if (p = nil) then writeLN('LISTE LEER!'); }
end;

procedure Ins_First(var p: zeiger; i: integer);
var h: zeiger;
begin
h:=p;
new(p);
p^.data:=i;
p^.next:=h;
end;

procedure ins_Last(var p: zeiger; i: integer);
var h: zeiger;
begin
if is_Empty(p) then ins_First(p,i) else begin
h:=p;
while h^.next <> nil do h:=h^.next;
new(h^.next);
h^.next^.data:=random(50)+1;
h^.next^.next:=nil;
end;
end;

procedure Del_First(var p: zeiger);
var h: zeiger;
begin
if not(is_empty(p)) then begin
h:=p^.next;
dispose(p);
p:=h;
end;
end;

procedure Make_List(var p: zeiger; count: integer);
var i: integer;
begin
for i:=1 to count do ins_last(p,i);
writeLN('Out_List:');
Out_List(p);
end;

{ Tauschen der Nachbaren }
procedure bubblesort(var p: zeiger);
var h0,h1,h2: zeiger;
    tausch  : boolean;

begin
{ DUMMY-Element wird eingefuegt }
ins_first(p,0);
repeat
 h0:=p;
 h1:=h0^.next;
 h2:=h1^.next;
 tausch:=false;
 inc(d1);
 while (h2 <> nil) do begin
 if (h1^.data > h2^.data) then
  begin
   tausch:=true;
   h0^.next:=h1^.next; h1^.next:=h2^.next; h2^.next:=h1;
  end;
  inc(d2);
  h0:=h0^.next; h1:=h0^.next; h2:=h1^.next;
 end;
until tausch = false;
{ DUMMY-Element wird entfernt }
del_first(p);
end;

begin
TextMode(CO80 xor Lo(LastMode)+Font8x8 xor LASTMODE);
ClrScr;
randomize;
writeLN('B U B B L E S O R T - D E M O ! ! !');
writeLN;
writeLN('ZUFAELLIGE LISTE:');
make_list(p,n);
writeLN('BUBBLESORT AUF LISTEN:');
bubblesort(p);
out_list(p);
writeLN('Durchlaeufe D1: ',d1,' D2: ',d2,' D1*D2 = ',d1*d2);
readLN;
end.