Jump to content

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

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

Revision as of 18:03, 15 May 2021

7,300 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 1,225:
=={{header|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 sphixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
integer beginIdx = 1,
endIdx = length(s)-1
<span style="color: #008080;">function</span> <span style="color: #000000;">cocktailShakerSort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
while beginIdx <= endIdx do
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
integer newBeginIdx = endIdx,
<span style="color: #004080;">integer</span> <span style="color: #000000;">beginIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
newEndIdx = beginIdx
<span style="color: #000000;">endIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span>
for ii=beginIdx to endIdx do
<span style="color: #008080;">while</span> <span style="color: #000000;">beginIdx</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">endIdx</span> <span style="color: #008080;">do</span>
if s[ii]>s[ii+1] then
<span style="color: #004080;">integer</span> <span style="color: #000000;">newBeginIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">endIdx</span><span style="color: #0000FF;">,</span>
{s[ii+1],s[ii]} = {s[ii], s[ii+1]}
<span style="color: #000000;">newEndIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">beginIdx</span>
newEndIdx = ii
<span style="color: #008080;">for</span> <span style="color: #000000;">ii</span><span style="color: #0000FF;">=</span><span style="color: #000000;">beginIdx</span> <span style="color: #008080;">to</span> <span style="color: #000000;">endIdx</span> <span style="color: #008080;">do</span>
end if
<span style="color: #004080;">object</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">],</span>
end for
<span style="color: #000000;">sn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
-- elements after `newEndIdx` are now in correct order▼
<span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">></span><span style="color: #000000;">sn</span> <span style="color: #008080;">then</span>
endIdx = newEndIdx - 1
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sn</span>
for ii=endIdx to beginIdx by -1 do
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span>
if s[ii]>s[ii+1] then
<span style="color: #000000;">newEndIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ii</span>
{s[ii+1],s[ii]} = {s[ii],s[ii+1]}
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
newBeginIdx = ii
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end if
▲ <span style="color: #000080;font-style:italic;">-- elements after `newEndIdx` are now in correct order</span>
end for
<span style="color: #000000;">endIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newEndIdx</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">1</span>
-- elements before `newBeginIdx` are now in correct order.▼
<span style="color: #008080;">for</span> <span style="color: #000000;">ii</span><span style="color: #0000FF;">=</span><span style="color: #000000;">endIdx</span> <span style="color: #008080;">to</span> <span style="color: #000000;">beginIdx</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
beginIdx = newBeginIdx + 1
<span style="color: #004080;">object</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">],</span>
end while
<span style="color: #000000;">sn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
return s
<span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">></span><span style="color: #000000;">sn</span> <span style="color: #008080;">then</span>
end function
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sn</span>
sequence s = shuffle(tagset(12)) ?{s,cocktailShakerSort(s)}
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span>
s = {"one","two","three","four"} ?{s,cocktailShakerSort(s)}</lang>
<span style="color: #000000;">newBeginIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ii</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
▲ <span style="color: #000080;font-style:italic;">-- elements before `newBeginIdx` are now in correct order.</span>
<span style="color: #000000;">beginIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newBeginIdx</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">12</span><span style="color: #0000FF;">))</span> <span style="color: #0000FF;">?{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cocktailShakerSort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)}</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"one"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"two"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"three"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"four"</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">?{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cocktailShakerSort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)}</span>
<!--</lang>-->
{{out}}
<pre>
Line 1,257 ⟶ 1,268:
{{"one","two","three","four"},{"four","one","three","two"}}
</pre>
 
=={{header|Python}}==
<lang python>
Petelomax
7,805

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/300127"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information