Let A be the vector that needs sorting. For each element A[i] of the vector we have to count the number of smaller numbers in the vector. This number represents the position of the element A[i] in the sorted vector( B below). We have to be careful when dealing with elements that repeat themselves in the vector.

Pascal program:

var a,b:array[1..100] of integer;

i,j,k,n:integer;

procedure sort;

begin

for i:=1 to n do

begin

k:=0;

for j:=1 to n do

if (a[j]<a[i]) or ((a[j]=a[i]) and (j<i)) then inc(k);

b[k+1]:=a[i];

end;

end;

 

begin

readln(n);

for i:=1 to n do

readln(a[i]);

sort;

for i:=1 to n do

write(b[i],' ');

writeln;

end.

 

 

C++ program:

#include<iostream.h>

int a[100],b[100],i,j,k,n;

void sort()

{

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

{ k=0;

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

if ((a[j]<a[i])|((a[j]=a[i])&(j<i))) k=k+1;

b[k+1]=a[i];

}

}

void main()

{

cin>>n;

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

cin>>a[i];

sort();

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

cout<<b[i]<" ";

cout<<endl;

}

 

Time: O(n^2)