Sorting algorithms/Cocktail sort with shifting bounds: Difference between revisions
PatGarrett (talk | contribs) (→{{header|360 Assembly}}: a correction) |
m (elided the __TOC__ statement from the task's epilogue.) |
||
Line 83:
:* [https://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort cocktail sort]
<br><br>
=={{header|360 Assembly}}==
|
Revision as of 20:58, 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
360 Assembly
For maximum compatibility, this program uses only the basic instruction set. The program uses also HLASM structured macros (DO,ENDDO,IF,ELSE,ENDIF) for readability and two ASSIST/360 macros (XDECO,XPRNT) to keep the code as short as possible. <lang 360asm>* Cocktail sort with shifting bounds 10/05/2020 COCKSHIS CSECT
USING COCKSHIS,R13 base register B 72(R15) skip savearea DC 17F'0' savearea SAVE (14,12) save previous context ST R13,4(R15) link backward ST R15,8(R13) link forward LR R13,R15 set addressability
- Sort
LA R0,1 1 ST R0,BEGIDX begIdx=LBound(A) L R0,N n BCTR R0,0 n-1 ST R0,ENDIDX endIdx=UBound(A)-1 L R1,BEGIDX begIdx DO WHILE=(C,R1,LE,ENDIDX) while begIdx<=endIdx MVC NWBEGIDX,ENDIDX nwbegIdx=endIdx MVC NWENDIDX,BEGIDX nwendIdx=begIdx L RI,BEGIDX i=begIdx DO WHILE=(C,RI,LE,ENDIDX) do i=1 to endIdx LR R1,RI i SLA R1,2 . LA R2,A-4(R1) @a(i) LA R3,A(R1) @a(i+1) L R4,0(R2) r4=a(i) L R5,0(R3) r5=a(i+1) IF CR,R4,GT,R5 THEN if a(i)>a(i+1) then ST R5,0(R2) a(i)=r5 ST R4,0(R3) a(i+1)=r4 ST RI,NWENDIDX nwendIdx=i ENDIF , end if LA RI,1(RI) i=i+1 ENDDO , end do L R1,NWENDIDX nwendIdx BCTR R1,0 -1 ST R1,ENDIDX endIdx=nwendIdx-1 LR RI,R1 endIdx DO WHILE=(C,RI,GE,BEGIDX) do i=endIdx to begIdx by -1 LR R1,RI i SLA R1,2 . LA R2,A-4(R1) @a(i) LA R3,A(R1) @a(i+1) L R4,0(R2) r4=a(i) L R5,0(R3) r5=a(i+1) IF CR,R4,GT,R5 THEN if a(i)>a(i+1) then ST R5,0(R2) a(i)=r5 ST R4,0(R3) a(i+1)=r4 ST RI,NWBEGIDX nwbegIdx=i ENDIF , end if BCTR RI,0 i=i-1 ENDDO , end do L R1,NWBEGIDX nwbegIdx LA R1,1(R1) +1 ST R1,BEGIDX begIdx=nwbegIdx+1 ENDDO , endwhile
- Display sorted list
LA R3,PG pgi=0 LA RI,1 i=1 DO WHILE=(C,RI,LE,N) do i=1 to n LR R1,RI i SLA R1,2 . L R2,A-4(R1) a(i) XDECO R2,XDEC edit a(i) MVC 0(4,R3),XDEC+8 output a(i) LA R3,4(R3) pgi=pgi+4 LA RI,1(RI) i=i+1 ENDDO , end do XPRNT PG,L'PG print buffer L R13,4(0,R13) restore previous savearea pointer RETURN (14,12),RC=0 restore registers from calling save
A DC F'4',F'65',F'2',F'-31',F'0',F'99',F'2',F'83'
DC F'782',F'1',F'45',F'82',F'69',F'82',F'104',F'58' DC F'88',F'112',F'89',F'74'
N DC A((N-A)/L'A) number of items of a PG DC CL80' ' buffer XDEC DS CL12 temp for xdeco BEGIDX DS F begIdx ENDIDX DS F endIdx NWBEGIDX DS F nwbegIdx NWENDIDX DS F nwendIdx
REGEQU
RI EQU 6 i
END COCKSHIS </lang>
- Output:
-31 0 1 2 2 4 45 58 65 69 74 82 82 83 88 89 99 104 112 782
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