Rosetta Code

Sorting algorithms/Cocktail sort with shifting bounds: Difference between revisions

Page Discussion

Sorting algorithms/Cocktail sort with shifting bounds (view source)

Revision as of 11:33, 8 February 2024

11,128 bytes added ,  4 months ago
m
→‎{{header|Wren}}: Minor tidy
m (syntax highlighting fixup automation)
m (→‎{{header|Wren}}: Minor tidy)
 
(6 intermediate revisions by 3 users not shown)
Line 558:
6 92 61 64 73 3 81 28 62 67 83 33 77 14 16 23 47 19 33 78
3 6 14 16 19 23 28 33 33 47 61 62 64 67 73 77 78 81 83 92
</pre>
 
=={{header|ALGOL 68}}==
Based on the pseudo-code with test cases from the Action! sample.
<syntaxhighlight lang="algol68">
BEGIN # cocktail sort with shifting bounds #
 
# sorts data, using a cocktail sort with shifting bounds #
# a reference to the sorted data is returned #
# - defined as an operator as Algol 68 has operator overloading but not #
# procedure overloading #
# (similar operators with the same name could be defined for other types #
# of array) #
OP COCKTAILSORTSB = ( []INT data )REF[]INT:
BEGIN
# make a copy of the data #
REF[]INT a := HEAP[ LWB data : UPB data ]INT := data;
# `beginIdx` and `endIdx` marks the first and last index to check. #
INT begin idx := LWB a;
INT end idx := UPB a - 1;
 
WHILE begin idx <= end idx DO
INT new begin idx := end idx;
INT new end idx := begin idx;
FOR ii FROM begin idx TO end idx DO
IF a[ ii ] > a[ ii + 1 ] THEN
INT aii = a[ ii ];
a[ ii ] := a[ ii + 1 ];
a[ ii + 1 ] := aii;
new end idx := ii
FI
OD;
 
# decreases `endIdx` because the elements after `newEndIdx` are in correct order #
end idx := new end idx - 1;
 
FOR ii FROM end idx BY -1 TO begin idx DO
IF a[ ii ] > a[ ii + 1 ] THEN
INT aii = a[ ii ];
a[ ii ] := a[ ii + 1 ];
a[ ii + 1 ] := aii;
new begin idx := ii
FI
OD;
 
# increases `beginIdx` because the elements before `newBeginIdx` are in correct order. #
begin idx := new begin idx + 1
OD;
a
END # COCKTAILSORTSB # ;
 
# test the COCKTAILSORTSB operator #
PROC test cocktail sort with shifting bounds = ( []INT data )VOID:
BEGIN
REF[]INT sorted := COCKTAILSORTSB data;
print( ( "[" ) );
FOR i FROM LWB data TO UPB data DO print( ( " ", whole( data[ i ], 0 ) ) ) OD;
print( ( " ]", newline, " -> [" ) );
FOR i FROM LWB sorted TO UPB sorted DO print( ( " ", whole( sorted[ i ], 0 ) ) ) OD;
print( ( " ]", newline ) )
END # test cocktail sort with shifting bounds # ;
 
# test cases from the Action! sample #
test cocktail sort with shifting bounds( ( 1, 4, -1, 0, 3, 7, 4, 8, 20, -6 ) );
test cocktail sort with shifting bounds( ( 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10
)
);
test cocktail sort with shifting bounds( ( 101, 102, 103, 104, 105, 106, 107, 108 ) );
test cocktail sort with shifting bounds( ( 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1 ) );
# additional test cases #
test cocktail sort with shifting bounds( ( 1, 1, 1, 1, 1, 1 ) );
test cocktail sort with shifting bounds( ( 0 ) );
test cocktail sort with shifting bounds( () )
END
</syntaxhighlight>
{{out}}
<pre>
[ 1 4 -1 0 3 7 4 8 20 -6 ]
-> [ -6 -1 0 1 3 4 4 7 8 20 ]
[ 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 ]
-> [ -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 ]
[ 101 102 103 104 105 106 107 108 ]
-> [ 101 102 103 104 105 106 107 108 ]
[ 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ]
-> [ -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 ]
[ 1 1 1 1 1 1 ]
-> [ 1 1 1 1 1 1 ]
[ 0 ]
-> [ 0 ]
[ ]
-> [ ]
</pre>
 
=={{header|ALGOL W}}==
Based on the pseudo-code - test code based on the Algol 68 test code.
<syntaxhighlight lang="algolw">
begin % cocktail sort with shifting bounds %
 
% sorts in-place a using a cocktail sort with shifting bounds %
% the bounds of a must be specified in lb and ub %
procedure cocktailSortWithShiftingBounds ( integer array a ( * )
; integer value lb, ub
);
begin
% `beginIdx` and `endIdx` marks the first and last index to check. %
integer beginIdx, endIdx;
beginIdx := lb;
endIdx := ub - 1;
 
while beginIdx <= endIdx do begin
integer newBeginIdx, newEndIdx;
newBeginIdx := endIdx;
newEndIdx := beginIdx;
for ii := beginIdx until endIdx do begin
integer aii;
if a( ii ) > a( ii + 1 ) then begin
integer aii;
aii := a( ii );
a( ii ) := a( ii + 1 );
a( ii + 1 ) := aii;
newEndIdx := ii
end
end for_ii ;
 
% decreases `endIdx` because the elements after `newEndIdx` are in correct order %
endIdx := newEndIdx - 1;
 
for ii := endIdx step -1 until beginIdx do begin
if a( ii ) > a( ii + 1 ) then begin
integer aii;
aii := a( ii );
a( ii ) := a( ii + 1 );
a( ii + 1 ) := aii;
newBeginIdx := ii
end
end for_ii ;
 
% increases `beginIdx` because the elements before `newBeginIdx` are in correct order. %
beginIdx := newBeginIdx + 1
 
end while_beginIdx_le_endIdx
 
end coctailSortWithShiftingBounds ;
 
% test the cocktailSortWithShiftingBounds procedure %
begin
 
integer procedure inc ( integer value result i ) ;
begin
i := i + 1;
i
end inc ;
 
procedure testCocktailSortWithShiftingBounds( integer array data ( * )
; integer value lb, ub
);
begin
i_w := 1; s_w := 0; % set formatting %
write( "[" );
for i := lb until ub do writeon( " ", data( i ) );
writeon( " ]" );
cocktailSortWithShiftingBounds( data, lb, ub );
write( " -> [" );
for i := lb until ub do writeon( " ", data( i ) );
writeon( " ]" )
end testCocktailSortWithShiftingBounds ;
 
integer array t ( 1 :: 32 );
integer tPos;
 
% test cases from the Action! sample %
tPos := 0;
for d := 1, 4, -1, 0, 3, 7, 4, 8, 20, -6 do t( inc( tPos ) ) := d;
testCocktailSortWithShiftingBounds( t, 1, tPos );
tPos := 0;
for d := 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10
do t( inc( tPos ) ) := d;
testCocktailSortWithShiftingBounds( t, 1, tPos );
tPos := 0;
for d := 101, 102, 103, 104, 105, 106, 107, 108 do t( inc( tPos ) ) := d;
testCocktailSortWithShiftingBounds( t, 1, tPos );
tPos := 0;
for d := 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1 do t( inc( tPos ) ) := d;
testCocktailSortWithShiftingBounds( t, 1, tPos );
% additional test cases %
tPos := 0;
for d := 1, 1, 1, 1, 1, 1 do t( inc( tPos ) ) := d;
testCocktailSortWithShiftingBounds( t, 1, tPos );
tPos := 0;
for d := 0 do t( inc( tPos ) ) := d;
testCocktailSortWithShiftingBounds( t, 1, tPos );
tPos := 0;
testCocktailSortWithShiftingBounds( t, 1, tPos );
end
end.
</syntaxhighlight>
{{out}}
<pre>
[ 1 4 -1 0 3 7 4 8 20 -6 ]
-> [ -6 -1 0 1 3 4 4 7 8 20 ]
[ 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 ]
-> [ -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 ]
[ 101 102 103 104 105 106 107 108 ]
-> [ 101 102 103 104 105 106 107 108 ]
[ 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ]
-> [ -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 ]
[ 1 1 1 1 1 1 ]
-> [ 1 1 1 1 1 1 ]
[ 0 ]
-> [ 0 ]
[ ]
-> [ ]
</pre>
 
Line 1,543 ⟶ 1,757:
abcdefghiijklmnopqrstuvwxyz
</pre>
 
=={{header|Quackery}}==
 
<syntaxhighlight lang="Quackery">
[ stack ] is limit ( --> s )
[ stack ] is offset ( --> s )
 
[ offset share +
2dup 1+ peek dip peek > ] is compare ( [ n --> b )
 
[ offset share +
dup 1+ unrot
2dup peek
dip
[ 2dup 1+ peek
unrot poke
swap ]
unrot poke ] is exchange ( [ n --> [ )
 
[ dup size 1 - limit put
0 offset put
[ 0 swap
limit share times
[ dup i^ compare if
[ i^ exchange
dip 1+ ] ]
over while
limit share times
[ dup i compare if
[ i exchange
dip 1+ ] ]
over while
-2 limit tally
1 offset tally
nip again ]
nip
limit release
offset release ] is cocktail ( [ --> [ )
 
randomise
[] 20 times [ 89 random 10 + join ]
dup echo cr
cocktail echo</syntaxhighlight>
 
{{out}}
 
<pre>[ 88 46 64 82 35 34 92 15 48 78 94 19 50 79 62 19 42 79 43 50 ]
[ 15 19 19 34 35 42 43 46 48 50 50 62 64 78 79 79 82 88 92 94 ]</pre>
 
=={{header|Raku}}==
Line 1,903 ⟶ 2,165:
 
Ratios are noticeably less than the Go example (more in keeping with the REXX results in the talk page) and vary more if the script is run a few times. Frankly, I don't know why this is.
<syntaxhighlight lang="ecmascriptwren">import "./fmt" for Fmt
import "random" for Random
 
Line 2,022 ⟶ 2,284:
20k 1.228
</pre>
 
=={{header|XPL0}}==
Translation of the pseudo code from Wikipedia.
<syntaxhighlight lang "XPL0">procedure CocktailShakerSort(A, Length);
integer A, Length;
integer BeginIdx, EndIdx; \mark the first and last index to check
integer NewBeginIdx, NewEndIdx, II, T;
begin
BeginIdx:= 0;
EndIdx:= Length - 1;
 
while BeginIdx <= EndIdx do
begin
NewBeginIdx:= EndIdx;
NewEndIdx:= BeginIdx;
for II:= BeginIdx to EndIdx - 1 do
begin
if A(II) > A(II + 1) then
begin
T:= A(II+1); A(II+1):= A(II); A(II):= T;
NewEndIdx:= II;
end;
end;
 
\Decreases EndIdx because the elements after NewEndIdx are in correct order
EndIdx:= NewEndIdx;
 
for II:= EndIdx downto BeginIdx - 1 do
begin
if A(II) > A(II + 1) then
begin
T:= A(II+1); A(II+1):= A(II); A(II):= T;
NewBeginIdx:= II;
end;
end;
 
\Increases BeginIdx because elements before NewBeginIdx are in correct order
BeginIdx:= NewBeginIdx + 1;
end;
end;
 
int Test, Len, I;
begin
Test:= [7, 6, 5, 9, 8, 4, 3, 1, 2, 0];
Len:= 10;
CocktailShakerSort(Test, Len);
for I:= 0 to Len-1 do
begin
IntOut(0, Test(I));
ChOut(0, ^ );
end;
end</syntaxhighlight>
{{out}}
<pre>
0 1 2 3 4 5 6 7 8 9 </pre>
PureFox
9,485

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/328438...354173"