Suppose we have an algorithm that, given the sequence a[p],a[p+1]....a[u], gives a[p] a position k, by interchanging the elements of the sequence, so that a[s]<=a[k]<=a[t], for s in {p,...k-1} and t in {k+1,..u}. Then we can continue sorting the sequences a[p]...a[k-1] and a[k+1]...a[u] independently from one another.

 

Pascal Program:

var v:array[1..1000] of integer;

i,j,n,m:integer;

f:text;

procedure poz(li,ls:byte; var k:byte);

var i,j,di,dj,aux1:shortint;

aux2:integer;

begin

i:=li;

j:=ls;

di:=0;

dj:=-1;

while i<j do

begin

if v[i]>v[j] then

begin

aux2:=v[i];

v[i]:=v[j];

v[j]:=aux2;

aux1:=-di;

di:=-dj;

dj:=aux1;

end;

i:=i+di;

j:=j+dj;

end;

k:=i;

end;

procedure quick(li,ls:byte);

var m:byte;

begin if li<ls then

begin

m:=(li+ls) div 2;

poz(li,ls,m);

quick(li,m-1);

quick(m+1,ls);

end;

end;

begin

assign(f,'mediana.in');

reset(f);

readln(f,n);

for i:=1 to n do

read(f,v[i]);

quick(1,n);

writeln;

for i:=1 to n do

write(v[i],' ');

readln

end.

 

C++ Program:

#include<iostream.h>

int v[100],i,j,n,m,k;

void poz (int li, int ls)

{

int i,j,di,dj,aux1,aux2;

i=li;

j=ls;

di=0;

dj=-1;

while (i<j)

{if v[i]>v[j])

{

aux2=v[i];

v[i]=v[j];

v[j]=aux2;

aux1=-di;

di=-dj;

dj=aux1;

}

i=i+di;

j=j+dj;

}

k=i;

}

void quick(int li, int ls)

{

if (li<ls)

{

k=(li+ls)/2;

poz(li,ls);

quick(li,k-1);

quick(k+1,ls);

}

}

void main()

{

cin>>n;

for(i=1;i<=n;i++)

cin>>v[i];

quick(1,n);

for(i=1;i<=n;i++)

cout<<v[i]<<" ";

}

Time: O(log2(n))

In order to use this method of sorting one needs to know recursivity. Quick sort uses Divide et Impera method. If you don't already know these things, you should get back to this sort method after you learn them.