You can write merge sort , partition sort , tree sort and compare results
It is quite easy to write tree sort if you allow some extra space
For tree sort each node of linked list must have two pointers even if we sort
singly linked list
In linked list i prefer inserting and deleting instead of swapping
Hoare partition can be done only for doubly linked list
program untitled;
type TData = longint;
PNode = ^TNode;
TNode = record
data:TData;
prev:PNode;
next:PNode;
end;
procedure ListInit(var head:PNode);
begin
head := NIL;
end;
function ListIsEmpty(head:PNode):boolean;
begin
ListIsEmpty := head = NIL;
end;
function ListSearch(var head:PNode;k:TData):PNode;
var x:PNode;
begin
x := head;
while (x <> NIL)and(x^.data <> k)do
x := x^.next;
ListSearch := x;
end;
procedure ListInsert(var head:PNode;k:TData);
var x:PNode;
begin
new(x);
x^.data := k;
x^.next := head;
if head <> NIL then
head^.prev := x;
head := x;
x^.prev := NIL;
end;
procedure ListDelete(var head:PNode;k:TData);
var x:PNode;
begin
x := ListSearch(head,k);
if x <> NIL then
begin
if x^.prev <> NIL then
x^.prev^.next := x^.next
else
head := x^.next;
if x^.next <> NIL then
x^.next^.prev := x^.prev;
dispose(x);
end;
end;
procedure ListPrint(head:PNode);
var x:PNode;
counter:longint;
begin
x := head;
counter := 0;
while x <> NIL do
begin
write(x^.data,' -> ');
x := x^.next;
counter := counter + 1;
end;
writeln('NIL');
writeln('Liczba elementow listy : ',counter);
end;
procedure BSTinsert(x:PNode;var t:PNode);
begin
if t = NIL then
t := x
else
if t^.data = x^.data then
BSTinsert(x,t^.prev)
else if t^.data < x^.data then
BSTinsert(x,t^.next)
else
BSTinsert(x,t^.prev);
end;
procedure BSTtoDLL(t:PNode;var L:PNode);
begin
if t <> NIL then
begin
BSTtoDLL(t^.next,L);
ListInsert(L,t^.data);
BSTtoDLL(t^.prev,L);
end;
end;
procedure BSTdispose(t:PNode);
begin
if t <> NIL then
begin
BSTdispose(t^.prev);
BSTdispose(t^.next);
dispose(t);
end;
end;
procedure BSTsort(var L:PNode);
var T,S:PNode;
x,xs:PNode;
begin
T := NIL;
S := NIL;
x := L;
while x <> NIL do
begin
xs := x^.next;
x^.prev := NIL;
x^.next := NIL;
BSTinsert(x,t);
x := xs;
end;
BSTtoDLL(T,S);
BSTdispose(T);
L := S;
end;
var i : byte;
head:PNode;
k:TData;
BEGIN
ListInit(head);
repeat
writeln('0. Wyjscie');
writeln('1. Wstaw element na poczatek listy');
writeln('2. Usun element listy');
writeln('3. Posortuj elementy drzewem binarnym');
writeln('4. Wypisz elementy listy');
readln(i);
case i of
0:
begin
while not ListIsEmpty(head) do
ListDelete(head,head^.data);
end;
1:
begin
writeln('Podaj element jaki chcesz wstawic');
readln(k);
ListInsert(head,k);
end;
2:
begin
writeln('Podaj element jaki chcesz usunac');
readln(k);
ListDelete(head,k);
end;
3:
begin
BSTsort(head);
end;
4:
begin
ListPrint(head);
end
else
writeln('Brak operacji podaj inny numer');
end;
until i = 0;
END.
This code needs some improvements
Firstly we should limit extra storage to the recursion needs
then we should try to replace recursion with iteration
If we want to improve algorithm further we should use self balancing tree