Sorting algorithms/Cocktail sort with shifting bounds: Difference between revisions
PatGarrett (talk | contribs) (→{{header|VBScript}}: Better indentation) |
PatGarrett (talk | contribs) m (→{{header|Visual Basic .NET}}: Better comment) |
||
| Line 366: | Line 366: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{works with|Visual Basic .NET|9.0}} |
{{works with|Visual Basic .NET|9.0}} |
||
<lang vbnet>' |
<lang vbnet>' Sorting algorithms/Cocktail sort with shifting bounds - VB.Net |
||
Private Sub Cocktail_Shaker_Sort() |
Private Sub Cocktail_Shaker_Sort() |
||
Dim A(20), tmp As Long 'or Integer Long Single Double String |
Dim A(20), tmp As Long 'or Integer Long Single Double String |
||
Revision as of 15:51, 10 May 2020
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
| This page uses content from Wikipedia. The original article was at Cocktail sort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
The cocktail sort is an improvement on the Bubble Sort.
A cocktail sort is also known as:
- cocktail shaker sort
- happy hour sort
- bidirectional bubble sort
- a bubble sort variation
- a selection sort variation
- ripple sort
- shuffle sort
- shuttle sort
The improvement is basically that values "bubble" both directions through the
array, because on each iteration the cocktail sort bubble sorts once
forwards and once backwards.
After ii passes, the first ii and the last ii elements in the array are in their correct positions, and don't to be checked (again).
By shortening the part of the array that is sorted each time, the number of comparisons can be halved.
Pseudocode for the 2nd algorithm (from
Wikipedia) with an added comment and changed indentations:
<lang matlab>function A = cocktailShakerSort(A)
% `beginIdx` and `endIdx` marks the first and last index to check.
beginIdx = 1;
endIdx = length(A) - 1;
while beginIdx <= endIdx
newBeginIdx = endIdx;
newEndIdx = beginIdx;
for ii = beginIdx:endIdx
if A(ii) > A(ii + 1)
[A(ii+1), A(ii)] = deal(A(ii), A(ii+1));
newEndIdx = ii;
end
end
% decreases `endIdx` because the elements after `newEndIdx` are in correct order endIdx = newEndIdx - 1;
% (FOR (below) decrements the II index by -1.
for ii = endIdx:-1:beginIdx
if A(ii) > A(ii + 1)
[A(ii+1), A(ii)] = deal(A(ii), A(ii+1));
newBeginIdx = ii;
end
end
% increases `beginIdx` because the elements before `newBeginIdx` are in correct order. beginIdx = newBeginIdx + 1; end
end</lang> % indicates a comment, and deal indicates a swap.
- Task
Implement a cocktail sort and optionally show the sorted output here on this page.
See the discussion page for some timing comparisons.
- Related task
ALGOL 60
<lang algol60>begin
comment Sorting algorithms/Cocktail sort - Algol 60;
integer array A[1:20]; integer nA;
procedure cocktailsort(lb,ub);
value lb,ub; integer lb,ub;
begin
integer i,lbx,ubx;
boolean swapped;
lbx:=lb; ubx:=ub-1; swapped :=true;
for i:=1 while swapped do begin
procedure swap(i); value i; integer i;
begin
integer temp;
temp :=A[i];
A[i] :=A[i+1];
A[i+1]:=temp;
swapped:=true
end swap;
swapped:=false;
for i:=lbx step 1 until ubx do if A[i]>A[i+1] then swap(i);
if swapped
then begin
for i:=ubx step -1 until lbx do if A[i]>A[i+1] then swap(i);
ubx:=ubx-1; lbx:=lbx+1
end
end
end cocktailsort;
procedure inittable(lb,ub);
value lb,ub; integer lb,ub;
begin
integer i;
for i:=lb step 1 until ub do A[i]:=entier(rand*100)
end inittable;
procedure writetable(lb,ub);
value lb,ub; integer lb,ub;
begin
integer i;
for i:=lb step 1 until ub do outinteger(1,A[i]);
outstring(1,"\n")
end writetable;
nA=20;
inittable(1,nA);
writetable(1,nA);
cocktailsort(1,nA);
writetable(1,nA)
end </lang>
- Output:
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
Phix
Averages 7 or 8% better than Sorting_algorithms/Cocktail_sort#Phix which already shifted the bounds, however this shifts >1 (sometimes). <lang Phix>function cocktailShakerSort(sequence s)
integer beginIdx = 1,
endIdx = length(s)-1
while beginIdx <= endIdx do
integer newBeginIdx = endIdx,
newEndIdx = beginIdx
for ii=beginIdx to endIdx do
if s[ii]>s[ii+1] then
{s[ii+1],s[ii]} = {s[ii], s[ii+1]}
newEndIdx = ii
end if
end for
-- elements after `newEndIdx` are now in correct order
endIdx = newEndIdx - 1
for ii=endIdx to beginIdx by -1 do
if s[ii]>s[ii+1] then
{s[ii+1],s[ii]} = {s[ii],s[ii+1]}
newBeginIdx = ii
end if
end for
-- elements before `newBeginIdx` are now in correct order.
beginIdx = newBeginIdx + 1
end while
return s
end function sequence s = shuffle(tagset(12)) ?{s,cocktailShakerSort(s)} s = {"one","two","three","four"} ?{s,cocktailShakerSort(s)}</lang>
- Output:
{{12,2,1,9,4,10,8,5,3,11,6,7},{1,2,3,4,5,6,7,8,9,10,11,12}}
{{"one","two","three","four"},{"four","one","three","two"}}
REXX
This REXX version can handle array elements that may contain blanks or spaces,
and uses an improved algorithm that uses shifting bounds.
<lang rexx>/*REXX program sorts an array using the cocktail─sort method with shifting bounds. */
call gen /*generate some array elements. */
call show 'before sort' /*show unsorted array elements. */
say copies('█', 101) /*show a separator line (a fence). */
call cocktailSort # /*invoke the cocktail sort subroutine. */ call show ' after sort' /*show sorted array elements. */ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ cocktailSort: procedure expose @.; parse arg N /*N: is number of items. */
end$= N - 1; beg$= 1
do while beg$ <= end$
beg$$= end$; end$$= beg$
do j=beg$ to end$; jp= j + 1
if @.j>@.jp then do; _=@.j; @.j=@.jp; @.jp=_; end$$=j; end
end /*j*/
end$= end$$ - 1
do k=end$ to beg$ by -1; kp= k + 1
if @.k>@.kp then do; _=@.k; @.k=@.kp; @.kp=_; beg$$=k; end
end /*k*/
beg$= beg$$ + 1
end /*while*/
return
/*──────────────────────────────────────────────────────────────────────────────────────*/ gen: @.= /*assign a default value for the stem. */
@.1 = '---the 22 card tarot deck (larger deck has 56 additional cards in 4 suits)---'
@.2 = '==========symbol====================pip======================================'
@.3 = 'the juggler ◄─── I'
@.4 = 'the high priestess [Popess] ◄─── II'
@.5 = 'the empress ◄─── III'
@.6 = 'the emperor ◄─── IV'
@.7 = 'the hierophant [Pope] ◄─── V'
@.8 = 'the lovers ◄─── VI'
@.9 = 'the chariot ◄─── VII'
@.10= 'justice ◄─── VIII'
@.11= 'the hermit ◄─── IX'
@.12= 'fortune [the wheel of] ◄─── X'
@.13= 'strength ◄─── XI'
@.14= 'the hanging man ◄─── XII'
@.15= 'death [often unlabeled] ◄─── XIII'
@.16= 'temperance ◄─── XIV'
@.17= 'the devil ◄─── XV'
@.18= 'lightning [the tower] ◄─── XVI'
@.18= 'the stars ◄─── XVII'
@.20= 'the moon ◄─── XVIII'
@.21= 'the sun ◄─── XIX'
@.22= 'judgment ◄─── XX'
@.23= 'the world ◄─── XXI'
@.24= 'the fool [often unnumbered] ◄─── XXII'
do #= 1 until @.#==; end; #= #-1 /*find how many entries in the array. */
return /* [↑] adjust for DO loop advancement.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/ show: w= length(#); do j=1 for # /*#: is the number of items in @. */
say 'element' right(j, w) arg(1)":" @.j
end /*j*/ /* ↑ */
return /* └─────max width of any line.*/</lang>
- output when using the internal default inputs:
(Shown at three-quarter size.)
element 1 before sort: ---the 22 card tarot deck (larger deck has 56 additional cards in 4 suits)--- element 2 before sort: ==========symbol====================pip====================================== element 3 before sort: the juggler ◄─── I element 4 before sort: the high priestess [Popess] ◄─── II element 5 before sort: the empress ◄─── III element 6 before sort: the emperor ◄─── IV element 7 before sort: the hierophant [Pope] ◄─── V element 8 before sort: the lovers ◄─── VI element 9 before sort: the chariot ◄─── VII element 10 before sort: justice ◄─── VIII element 11 before sort: the hermit ◄─── IX element 12 before sort: fortune [the wheel of] ◄─── X element 13 before sort: strength ◄─── XI element 14 before sort: the hanging man ◄─── XII element 15 before sort: death [often unlabeled] ◄─── XIII element 16 before sort: temperance ◄─── XIV element 17 before sort: the devil ◄─── XV element 18 before sort: the stars ◄─── XVII █████████████████████████████████████████████████████████████████████████████████████████████████████ element 1 after sort: ---the 22 card tarot deck (larger deck has 56 additional cards in 4 suits)--- element 2 after sort: ==========symbol====================pip====================================== element 3 after sort: death [often unlabeled] ◄─── XIII element 4 after sort: fortune [the wheel of] ◄─── X element 5 after sort: justice ◄─── VIII element 6 after sort: strength ◄─── XI element 7 after sort: temperance ◄─── XIV element 8 after sort: the chariot ◄─── VII element 9 after sort: the devil ◄─── XV element 10 after sort: the emperor ◄─── IV element 11 after sort: the empress ◄─── III element 12 after sort: the hanging man ◄─── XII element 13 after sort: the hermit ◄─── IX element 14 after sort: the hierophant [Pope] ◄─── V element 15 after sort: the high priestess [Popess] ◄─── II element 16 after sort: the juggler ◄─── I element 17 after sort: the lovers ◄─── VI element 18 after sort: the stars ◄─── XVII
VBA
<lang vb>' Sorting algorithms/Cocktail sort with shifting bounds - VBA
Function cocktailShakerSort(ByVal A As Variant) As Variant
beginIdx = LBound(A)
endIdx = UBound(A) - 1
Do While beginIdx <= endIdx
newBeginIdx = endIdx
newEndIdx = beginIdx
For ii = beginIdx To endIdx
If A(ii) > A(ii + 1) Then
tmp = A(ii): A(ii) = A(ii + 1): A(ii + 1) = tmp
newEndIdx = ii
End If
Next ii
endIdx = newEndIdx - 1
For ii = endIdx To beginIdx Step -1
If A(ii) > A(ii + 1) Then
tmp = A(ii): A(ii) = A(ii + 1): A(ii + 1) = tmp
newBeginIdx = ii
End If
Next ii
beginIdx = newBeginIdx + 1
Loop
cocktailShakerSort = A
End Function 'cocktailShakerSort
Public Sub main()
Dim B(20) As Variant
For i = LBound(B) To UBound(B)
B(i) = Int(Rnd() * 100)
Next i
Debug.Print Join(B, ", ")
Debug.Print Join(cocktailShakerSort(B), ", ")
End Sub</lang>
- Output:
52, 76, 5, 59, 46, 29, 62, 64, 26, 27, 82, 82, 58, 98, 91, 22, 69, 98, 24, 53, 10 5, 10, 22, 24, 26, 27, 29, 46, 52, 53, 58, 59, 62, 64, 69, 76, 82, 82, 91, 98, 98
VBScript
<lang vb>' Sorting algorithms/Cocktail sort with shifting bounds - VBScript
Function cocktailShakerSort(ByVal A)
beginIdx = Lbound(A)
endIdx = Ubound(A)-1
Do While beginIdx <= endIdx
newBeginIdx = endIdx
newEndIdx = beginIdx
For ii = beginIdx To endIdx
If A(ii) > A(ii+1) Then
tmp=A(ii) : A(ii)=A(ii+1) : A(ii+1)=tmp
newEndIdx = ii
End If
Next
endIdx = newEndIdx - 1
For ii = endIdx To beginIdx Step -1
If A(ii) > A(ii+1) Then
tmp=A(ii) : A(ii)=A(ii+1) : A(ii+1)=tmp
newBeginIdx = ii
End If
Next
beginIdx = newBeginIdx+1
Loop
cocktailShakerSort=A
End Function 'cocktailShakerSort
Dim B(20) For i=Lbound(B) To Ubound(B)
B(i)=Int(Rnd()*100)
Next Wscript.Echo Join(cocktailShakerSort(B)," ")
</lang>
- Output:
1 4 5 28 30 36 37 41 53 57 70 70 76 77 79 81 86 87 94 96
Visual Basic .NET
<lang vbnet>' Sorting algorithms/Cocktail sort with shifting bounds - VB.Net
Private Sub Cocktail_Shaker_Sort()
Dim A(20), tmp As Long 'or Integer Long Single Double String
Dim i, beginIdx, endIdx, newBeginIdx, newEndIdx As Integer
'Generate the list
For i = LBound(A) To UBound(A)
A(i) = Int(Rnd() * 100)
Next i
'Sort the list
beginIdx = LBound(A)
endIdx = UBound(A) - 1
Do While beginIdx <= endIdx
newBeginIdx = endIdx
newEndIdx = beginIdx
For ii = beginIdx To endIdx
If A(ii) > A(ii + 1) Then
tmp = A(ii) : A(ii) = A(ii + 1) : A(ii + 1) = tmp
newEndIdx = ii
End If
Next ii
endIdx = newEndIdx - 1
For ii = endIdx To beginIdx Step -1
If A(ii) > A(ii + 1) Then
tmp = A(ii) : A(ii) = A(ii + 1) : A(ii + 1) = tmp
newBeginIdx = ii
End If
Next ii
beginIdx = newBeginIdx + 1
Loop
'Display the sorted list
Debug.Print(String.Join(", ", A))
End Sub 'Cocktail_Shaker_Sort </lang>
- Output:
1, 4, 5, 28, 30, 36, 37, 41, 52, 53, 57, 70, 70, 76, 77, 79, 81, 86, 87, 94, 96