Quick Sort

Quicksort(l, r)

If r>l then {

¡@v:=a[r];¡@i:=l-1;¡@j:=r;

¡@repeat ¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@

¡@¡@repeat i:=i+1 until a[i]v; ¡@¡@¡@¡@¡@

¡@¡@repeat j:=j-1 until a[j]v;¡@¡@¡@¡@¡@¡@i:=partiton(l,r);

¡@¡@t:=a[i];¡@a[i]:=a[j];¡@a[j]:=t;

¡@until¡@ji;¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@<---until j<i;

¡@a[j]:=a[i];¡@a[i]:=a[r];¡@a[r]:=t;¡@¡@¡@¡@<---a[r]<--->a[i]

¡@quicksort(l,i-1);¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@<---quicksort(l,j);

¡@quicksort(i+1,r);

}

¡@

i:=Partition(l,r)

¡@ ¡@1¡@ 2¡@3¡@4 ¡@5¡@6¡@7¡@ 8¡@9¡@10¡@11¡@12¡@13¡@14¡@15

---------------------------------------------------------------------------------------------

-¡@A¡@S¡@O¡@R¡@T¡@I¡@N¡@G¡@E¡@X¡@ A¡@ M¡@ P¡@¡@L¡@E <---sentinel

¡@¡@ A¡@A¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@S¡@ M¡@ P¡@¡@ L¡@E

¡@¡@ A¡@A¡@E¡@¡@¡@¡@¡@¡@¡@¡@¡@O¡@X¡@S¡@ M¡@ P¡@¡@ L¡@E

¡@¡@ A¡@A¡@E¡@E¡@T¡@I¡@N¡@G¡@ O¡@X¡@S¡@ M¡@ P¡@¡@ L¡@R

¡@¡@|________|¡@¡@|___________________________________|

¡@¡@¡@a[i]¡@¡@ a[i] ¡@¡@¡@¡@¡@¡@¡@a[i]

Inefficiently on sorted file