%% syntaxe : array bubblesort --> array2 trie par ordre croissant
%% code de Bill Casselman
%% http://www.math.ubc.ca/people/faculty/cass/graphics/text/www/
/bubblesort {
4 dict begin
/a exch def
/n a length 1 sub def
n 0 gt {
% at this point only the n+1 items in the bottom of a remain to
% the sorted largest item in that blocks is to be moved up into
% position n
n {
0 1 n 1 sub {
/i exch def
a i get a i 1 add get gt {
% if a[i] > a[i+1] swap a[i] and a[i+1]
a i 1 add
a i get
a i a i 1 add get
% set new a[i] = old a[i+1]
put
% set new a[i+1] = old a[i]
put
} if
} for
/n n 1 sub def
} repeat
} if
a
end
} def
%% syntaxe : array1 doublebubblesort --> array2 array3, array3 est
%% trie par ordre croissant et array2 correspond a la position des
%% indices de depart, ie si array1 = [3 2 4 1], alors array2 = [3 1 0 2]
%% code de Bill Casselman, modifie par jpv, 15/08/2006
%% http://www.math.ubc.ca/people/faculty/cass/graphics/text/www/
/doublebubblesort {
5 dict begin
/table exch def
/n table length 1 sub def
/indices [ 0 1 n {} for ] def
n 0 gt {
% at this point only the n+1 items in the bottom of a remain to
% the sorted largest item in that blocks is to be moved up into
% position n
n {
0 1 n 1 sub {
/i exch def
table i get table i 1 add get gt {
% if a[i] > a[i+1] swap a[i] and a[i+1]
table i 1 add
table i get
table i table i 1 add get
% set new a[i] = old a[i+1]
put
% set new a[i+1] = old a[i]
put
indices i 1 add
indices i get
indices i indices i 1 add get
% set new a[i] = old a[i+1]
put
% set new a[i+1] = old a[i]
put
} if
} for
/n n 1 sub def
} repeat
} if
indices table
end
} def
|