Sorting Algorithms/Circle Sort: Difference between revisions
(added FreeBASIC) |
m (comprehensive odd list length test inserted.) |
||
Line 1: | Line 1: | ||
{{draft task|Sorting Algorithms}}{{Sorting Algorithm}} |
{{draft task|Sorting Algorithms}}{{Sorting Algorithm}} |
||
Sort an array of integers (of any convenient size) into ascending order using Circlesort. In short, compare the first element to the last element, then the second element to the second last element, etc. Then split the array in two and recurse until there is only one single element in the array, like this: |
|||
Sort an array of integers (of any convenient size) into ascending order using Circlesort. |
|||
In short, compare the first element to the last element, then the second element to the second last element, etc. |
|||
Then split the array in two and recurse until there is only one single element in the array, like this: |
|||
Before: |
Before: |
||
'''6''' ''7'' 8 9 2 5 3 ''4'' '''1''' |
'''6''' ''7'' 8 9 2 5 3 ''4'' '''1''' |
||
Line 11: | Line 6: | ||
'''1''' ''4'' 3 5 2 9 8 ''7'' '''6''' |
'''1''' ''4'' 3 5 2 9 8 ''7'' '''6''' |
||
Show both the initial, unsorted list and the final sorted list. (Intermediate steps during sorting are optional.) Optimizations (like doing ''0.5 log2(n)'' iterations and then continue with an [[Insertion sort]]) are optional. |
|||
Repeat this procedure until quiescence (i.e. until there are no swaps). |
|||
Show both the initial, unsorted list and the final sorted list. (Intermediate steps during sorting are optional.) |
|||
Optimizations (like doing ''0.5 log2(n)'' iterations and then continue with an [[Insertion sort]]) are optional. <br> |
|||
Pseudo code: |
Pseudo code: |
||
Line 44: | Line 35: | ||
'''while''' circlesort (0, '''sizeof'''(array)-1, 0) |
'''while''' circlesort (0, '''sizeof'''(array)-1, 0) |
||
For more information on Circle sorting, see [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge]. |
|||
__FORCETOC__ |
|||
;See also: |
|||
* For more information on Circle sorting, see [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge]. |
|||
<br><br> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
<lang c>#include <stdio.h> |
<lang c>#include <stdio.h> |
||
int |
int cir_sort_inner(int *x, int n) |
||
{ |
{ |
||
int |
int i, j, t, swaps; |
||
if ( |
if (n < 2) return 0; |
||
for (swaps = i = 0, j = n - 1; i < j; i++, j--) |
|||
// funny "||" on next line is for the center element of odd-lengthed array |
|||
if (x[i] > x[j]) |
|||
for (swapped = 0, p = start, q = end; p<q || (p==q && ++q); p++, q--) |
|||
t=x[i], x[i]=x[j], x[j]=t, swaps++; |
|||
if (*p > *q) |
|||
t = *p, *p = *q, *q = t, swapped = 1; |
|||
return swaps + cir_sort_inner(x, j + 1) + cir_sort_inner(x + i, n - i); |
|||
// q == p-1 at this point |
|||
return swapped | circle_sort_inner(start, q) | circle_sort_inner(p, end); |
|||
} |
} |
||
//helper function to show arrays before each call |
//helper function to show arrays before each call |
||
void |
void cir_sort(int *x, int n) |
||
{ |
{ |
||
int i, s; |
|||
do { |
do { |
||
for (i = 0; i < n; i++) |
|||
int i; |
|||
printf("%d ", x[i]); |
|||
printf(": %d swaps\n", s = cir_sort_inner(x, n)); |
|||
putchar('\n'); |
|||
} while ( |
} while (s); |
||
} |
} |
||
int main(void) |
int main(void) |
||
{ |
{ |
||
int x[] = {5, -1, 101, -4, 0, 1, 8, 6, 2, 3}; |
int x[] = { 5, -1, 101, -4, 0, 1, 8, 6, 2, 3 }; |
||
cir_sort(x, sizeof(x)/sizeof(x[0])); |
|||
return 0; |
return 0; |
||
Line 86: | Line 75: | ||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
5 -1 101 -4 0 1 8 6 2 3 |
5 -1 101 -4 0 1 8 6 2 3 : 9 swaps |
||
-4 -1 |
-4 0 -1 3 6 1 2 5 8 101 : 6 swaps |
||
-4 -1 0 1 2 3 5 6 8 101 |
-4 -1 0 1 2 3 5 6 8 101 : 0 swaps |
||
</pre> |
</pre> |
||
Line 183: | Line 172: | ||
console: -1,0,1,3,2,5,4,8,6,7,9,12,10,11,13,14 |
console: -1,0,1,3,2,5,4,8,6,7,9,12,10,11,13,14 |
||
console: -1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14</pre> |
console: -1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14</pre> |
||
=={{header|Elixir}}== |
|||
<lang elixir>defmodule Sort do |
|||
def circle_sort(data) do |
|||
List.to_tuple(data) |
|||
|> circle_sort(0, length(data)-1) |
|||
|> Tuple.to_list |
|||
end |
|||
defp circle_sort(data, lo, hi) do |
|||
case circle_sort(data, lo, hi, 0) do |
|||
{result, 0} -> result |
|||
{result, _} -> circle_sort(result, lo, hi) |
|||
end |
|||
end |
|||
defp circle_sort(data, lo, lo, swaps), do: {data, swaps} |
|||
defp circle_sort(data, lo, hi, swaps) do |
|||
mid = div(lo + hi, 2) |
|||
{data, swaps} = do_circle_sort(data, lo, hi, swaps) |
|||
{data, swaps} = circle_sort(data, lo, mid, swaps) |
|||
circle_sort(data, mid+1, hi, swaps) |
|||
end |
|||
def do_circle_sort(data, lo, hi, swaps) when lo>=hi do |
|||
if lo==hi and elem(data, lo) > elem(data, hi+1), |
|||
do: {swap(data, lo, hi+1), swaps+1}, |
|||
else: {data, swaps} |
|||
end |
|||
def do_circle_sort(data, lo, hi, swaps) do |
|||
if elem(data, lo) > elem(data, hi), |
|||
do: do_circle_sort(swap(data, lo, hi), lo+1, hi-1, swaps+1), |
|||
else: do_circle_sort(data, lo+1, hi-1, swaps) |
|||
end |
|||
defp swap(data, i, j) do |
|||
vi = elem(data, i) |
|||
vj = elem(data, j) |
|||
data |> put_elem(i, vj) |> put_elem(j, vi) |
|||
end |
|||
end |
|||
data = [6, 7, 8, 9, 2, 5, 3, 4, 1] |
|||
IO.puts "before sort: #{inspect data}" |
|||
IO.puts " after sort: #{inspect Sort.circle_sort(data)}"</lang> |
|||
{{out}} |
|||
<pre> |
|||
before sort: [6, 7, 8, 9, 2, 5, 3, 4, 1] |
|||
after sort: [1, 2, 3, 4, 5, 6, 7, 8, 9] |
|||
</pre> |
|||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
<lang>defer precedes ( addr addr -- flag ) |
|||
This one features the newest version of the algorithm on [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge]. |
|||
variable (swaps) \ keeps track of swaps |
|||
<lang>[UNDEFINED] cell- [IF] : cell- 1 cells - ; [THEN] |
|||
[UNDEFINED] cell- [IF] : cell- 1 cells - ; [THEN] |
|||
defer precedes ( addr addr -- flag ) |
|||
variable (sorted?) \ is the array sorted? |
|||
: (compare) ( a1 a2 -- a1 a2) |
: (compare) ( a1 a2 -- a1 a2) |
||
over @ over @ precedes \ |
over @ over @ precedes \ if swapped, increment (swaps) |
||
if over over over @ over @ swap rot ! swap ! |
if over over over @ over @ swap rot ! swap ! 1 (swaps) +! then |
||
; |
; |
||
: (circlesort) ( |
: (circlesort) ( a n --) |
||
dup 1 > if |
|||
over over = if drop drop exit then \ quit if indexes are equal |
|||
over over |
over over ( array len) |
||
1- cells over + swap ( 'end 'begin) |
|||
begin |
|||
begin |
|||
over over > \ as long as middle isn't passed |
|||
over over > \ if we didn't pass the middle |
|||
while |
|||
while \ check and swap opposite elements |
|||
(compare) swap cell- swap cell+ |
|||
repeat rot recurse recurse \ split array and recurse |
|||
repeat \ check if there's a middle element |
|||
over over = if cell- (compare) then drop drop |
|||
over over 2/ recurse \ sort first partition |
|||
dup 2/ cells rot + swap dup 2/ - recurse exit |
|||
then \ sort second partition |
|||
drop drop \ nothing to sort |
|||
; |
; |
||
: sort begin 0 (swaps) ! over over (circlesort) (swaps) @ 0= until drop drop ; |
|||
: sort ( a n --) |
|||
1- cells over + \ calculate addresses |
|||
begin true (sorted?) ! over over (circlesort) (sorted?) @ until drop drop |
|||
; |
|||
:noname < ; is precedes |
:noname < ; is precedes |
||
10 constant /sample |
10 constant /sample |
||
create sample 5 , -1 , 101 , -4 , 0 , 1 , 8 , 6 , 2 , 3 , |
create sample 5 , -1 , 101 , -4 , 0 , 1 , 8 , 6 , 2 , 3 , |
||
: .sample sample /sample cells bounds do i ? 1 cells +loop ; |
: .sample sample /sample cells bounds do i ? 1 cells +loop ; |
||
sample /sample sort .sample</lang> |
sample /sample sort .sample</lang> |
||
=={{header|FreeBASIC}}== |
|||
<lang freebasic>' version 21-10-2016 |
|||
' compile with: fbc -s console |
|||
' for boundry checks on array's compile with: fbc -s console -exx |
|||
' converted pseudo code into FreeBASIC code |
|||
' shared variables need to be declared before first use |
|||
Dim Shared As Long cs(-7 To 7) |
|||
Function circlesort(lo As Long, hi As Long, swaps As ULong) As ULong |
|||
' array is declared shared |
|||
' sort from lower bound to the highter bound |
|||
' array's can have subscript range from -2147483648 to +2147483647 |
|||
If lo = hi Then Return swaps |
|||
Dim As Long high = hi |
|||
Dim As Long low = lo |
|||
Dim As Long mid_ = (hi - lo) \ 2 |
|||
While lo < hi |
|||
If cs(lo) > cs(hi) Then |
|||
Swap cs(lo), cs(hi) |
|||
swaps += 1 |
|||
End If |
|||
lo += 1 |
|||
hi -= 1 |
|||
Wend |
|||
If lo = hi Then |
|||
If cs(lo) > cs(hi +1) Then |
|||
Swap cs(lo), cs(hi +1) |
|||
swaps += 1 |
|||
End If |
|||
End If |
|||
swaps = circlesort(low , low + mid_, swaps) |
|||
swaps = circlesort(low + mid_ +1, high, swaps) |
|||
Return swaps |
|||
End Function |
|||
' ------=< MAIN >=------ |
|||
Dim As Long i, a = LBound(cs), b = UBound(cs) |
|||
Randomize Timer |
|||
For i = a To b : cs(i) = i : Next |
|||
For i = a To b ' little shuffle |
|||
Swap cs(i), cs(Int(Rnd * (b - a +1)) + a) |
|||
Next |
|||
Print "unsorted "; |
|||
For i = a To b : Print Using "####"; cs(i); : Next : Print |
|||
' sort the array, loop until sorted |
|||
While circlesort(a, b, 0) : Wend |
|||
Print " sorted "; |
|||
For i = a To b : Print Using "####"; cs(i); : Next : Print |
|||
' empty keyboard buffer |
|||
While InKey <> "" : Wend |
|||
Print : Print "hit any key to end program" |
|||
Sleep |
|||
End</lang> |
|||
{{out}} |
|||
<pre>unsorted -4 -1 1 0 5 -7 -2 4 -6 -3 2 6 3 7 -5 |
|||
sorted -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7</pre> |
|||
=={{header|J}}== |
|||
Of more parsing and atomic data, or less parsing with large data groups the latter produces faster J programs. Consequently each iteration laminates the original with its reverse. It joins the recursive call to the pairwise minima of the left block to the recursive call of the pairwise maxima of the right block, repeating the operations while the output changes. This is sufficient for power of 2 length data. The pre verb adjusts the data length. And post recovers the original data. This implementation discards the "in place" property described at the sourceforge link. |
|||
<lang J> |
|||
circle_sort =: post power_of_2_length@pre NB. the main sorting verb |
|||
power_of_2_length =: even_length_iteration^:_ NB. repeat while the answer changes |
|||
even_length_iteration =: (<./ (,&$: |.) >./)@(-:@# ({. ,: |.@}.) ])^:(1<#) |
|||
pre =: , (-~ >.&.(2&^.))@# # >./ NB. extend data to next power of 2 length |
|||
post =: ({.~ #)~ NB. remove the extra data |
|||
</lang> |
|||
Examples: |
|||
<lang J> |
|||
show =: [ smoutput |
|||
8 ([: circle_sort&.>@show ;&(?~)) 13 NB. sort lists length 8 and 13 |
|||
┌───────────────┬────────────────────────────┐ |
|||
│0 6 7 3 4 5 2 1│3 10 1 4 7 8 5 6 2 0 9 11 12│ |
|||
└───────────────┴────────────────────────────┘ |
|||
┌───────────────┬────────────────────────────┐ |
|||
│0 1 2 3 4 5 6 7│0 1 2 3 4 5 6 7 8 9 10 11 12│ |
|||
└───────────────┴────────────────────────────┘ |
|||
8 ([: circle_sort&.>@show ;&(1 }. 2 # ?~)) 13 NB. data has repetition |
|||
┌─────────────────────────────┬──────────────────────────────────────────────────────┐ |
|||
│2 3 3 5 5 1 1 7 7 6 6 4 4 0 0│12 11 11 4 4 3 3 9 9 7 7 10 10 6 6 2 2 1 1 5 5 8 8 0 0│ |
|||
└─────────────────────────────┴──────────────────────────────────────────────────────┘ |
|||
┌─────────────────────────────┬──────────────────────────────────────────────────────┐ |
|||
│0 0 1 1 2 3 3 4 4 5 5 6 6 7 7│0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12│ |
|||
└─────────────────────────────┴──────────────────────────────────────────────────────┘ |
|||
</lang> |
|||
=={{header|Java}}== |
|||
<lang java>import java.util.Arrays; |
|||
public class CircleSort { |
|||
public static void main(String[] args) { |
|||
circleSort(new int[]{2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1}); |
|||
} |
|||
public static void circleSort(int[] arr) { |
|||
if (arr.length > 0) |
|||
do { |
|||
System.out.println(Arrays.toString(arr)); |
|||
} while (circleSortR(arr, 0, arr.length - 1, 0) != 0); |
|||
} |
|||
private static int circleSortR(int[] arr, int lo, int hi, int numSwaps) { |
|||
if (lo == hi) |
|||
return numSwaps; |
|||
int high = hi; |
|||
int low = lo; |
|||
int mid = (hi - lo) / 2; |
|||
while (lo < hi) { |
|||
if (arr[lo] > arr[hi]) { |
|||
swap(arr, lo, hi); |
|||
numSwaps++; |
|||
} |
|||
lo++; |
|||
hi--; |
|||
} |
|||
if (lo == hi && arr[lo] > arr[hi + 1]) { |
|||
swap(arr, lo, hi + 1); |
|||
numSwaps++; |
|||
} |
|||
numSwaps = circleSortR(arr, low, low + mid, numSwaps); |
|||
numSwaps = circleSortR(arr, low + mid + 1, high, numSwaps); |
|||
return numSwaps; |
|||
} |
|||
private static void swap(int[] arr, int idx1, int idx2) { |
|||
int tmp = arr[idx1]; |
|||
arr[idx1] = arr[idx2]; |
|||
arr[idx2] = tmp; |
|||
} |
|||
}</lang> |
|||
<pre>[2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1] |
|||
[-1, 1, 0, 4, 3, 8, 12, 2, 7, 6, 11, 5, 13, 14] |
|||
[-1, 0, 1, 3, 2, 4, 7, 5, 6, 8, 12, 11, 13, 14] |
|||
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14]</pre> |
|||
=={{header|jq}}== |
|||
{{works with|jq|1.4}} |
|||
With kudos to [[#Perl 6]]. |
|||
"circlesort" as defined in this section can be used to sort any JSON array. In case your jq does not have "until" as a builtin, here is its definition: |
|||
<lang jq>def until(cond; next): |
|||
def _until: if cond then . else (next|_until) end; |
|||
_until;</lang> |
|||
<lang jq>def circlesort: |
|||
def swap(i;j): .[i] as $t | .[i] = .[j] | .[j] = $t; |
|||
# state: [lo, hi, swaps, array] |
|||
def cs: |
|||
# increment lo, decrement hi, and if they are equal, increment hi again |
|||
# i.e. ++hi if --hi == $lo |
|||
def next: # [lo, hi] |
|||
.[0] += 1 | .[1] -= 1 | (if .[0] == .[1] then .[1] += 1 else . end) ; |
|||
.[0] as $start | .[1] as $stop |
|||
| if $start < $stop then |
|||
until(.[0] >= .[1]; |
|||
.[0] as $lo | .[1] as $hi | .[3] as $array |
|||
| if $array[$lo] > $array[$hi] then |
|||
.[3] = ($array | swap($lo; $hi)) |
|||
| .[2] += 1 # swaps++ |
|||
else . |
|||
end |
|||
| next) |
|||
| .[0] as $lo | .[1] as $hi |
|||
| [$start, $hi, .[2], .[3]] | cs |
|||
| [$lo, $stop, .[2], .[3]] | cs |
|||
else . |
|||
end ; |
|||
[0, length-1, 0, .] | cs |
|||
| .[2] as $swaps |
|||
| .[3] |
|||
| if $swaps == 0 then . |
|||
else circlesort |
|||
end ;</lang> |
|||
'''Example:''' |
|||
<lang jq>"The quick brown fox jumps over the lazy dog" | split(" ") | circlesort</lang> |
|||
{{out}} |
|||
<lang sh>$ jq -n -c -f -M circleSort.jq |
|||
["The","brown","dog","fox","jumps","lazy","over","quick","the"]</lang> |
|||
=={{header|PARI/GP}}== |
|||
This follows the pseudocode pretty closely. |
|||
<lang parigp>circlesort(v)= |
|||
{ |
|||
local(v=v); \\ share with cs |
|||
while (cs(1, #v),); |
|||
v; |
|||
} |
|||
cs(lo, hi)= |
|||
{ |
|||
if (lo == hi, return (0)); |
|||
my(high=hi,low=lo,mid=(hi-lo)\2,swaps); |
|||
while (lo < hi, |
|||
if (v[lo] > v[hi], |
|||
[v[lo],v[hi]]=[v[hi],v[lo]]; |
|||
swaps++ |
|||
); |
|||
lo++; |
|||
hi-- |
|||
); |
|||
if (lo==hi && v[lo] > v[hi+1], |
|||
[v[lo],v[hi+1]]=[v[hi+1],v[lo]]; |
|||
swaps++ |
|||
); |
|||
swaps + cs(low,low+mid) + cs(low+mid+1,high); |
|||
} |
|||
print(example=[6,7,8,9,2,5,3,4,1]); |
|||
print(circlesort(example));</lang> |
|||
{{out}} |
|||
<pre>[6, 7, 8, 9, 2, 5, 3, 4, 1] |
|||
[1, 2, 3, 4, 5, 6, 7, 8, 9]</pre> |
|||
=={{header|Perl 6}}== |
|||
The given algorithm can be simplified in several ways. There's no need to compute the midpoint, since the hi/lo will end up there. The extra swap conditional can be eliminated by incrementing hi at the correct moment inside the loop. There's no need to |
|||
pass accumulated swaps down the call stack. |
|||
This does generic comparisons, so it works on any ordered type, including numbers or strings. |
|||
<lang perl6>sub circlesort (@x, $beg, $end) { |
|||
my $swaps = 0; |
|||
if $beg < $end { |
|||
my ($lo, $hi) = $beg, $end; |
|||
repeat { |
|||
if @x[$lo] after @x[$hi] { |
|||
@x[$lo,$hi] .= reverse; |
|||
++$swaps; |
|||
} |
|||
++$hi if --$hi == ++$lo |
|||
} while $lo < $hi; |
|||
$swaps += circlesort(@x, $beg, $hi); |
|||
$swaps += circlesort(@x, $lo, $end); |
|||
} |
|||
$swaps; |
|||
} |
|||
say my @x = (-100..100).roll(20); |
|||
say @x while circlesort(@x, 0, @x.end); |
|||
say @x = <The quick brown fox jumps over the lazy dog.>; |
|||
say @x while circlesort(@x, 0, @x.end);</lang> |
|||
{{out}} |
|||
<pre>16 35 -64 -29 46 36 -1 -99 20 100 59 26 76 -78 39 85 -7 -81 25 88 |
|||
-99 -78 16 20 36 -81 -29 46 25 59 -64 -7 39 26 88 -1 35 85 76 100 |
|||
-99 -78 -29 -81 16 -64 -7 20 -1 39 25 26 36 46 59 35 76 88 85 100 |
|||
-99 -81 -78 -64 -29 -7 -1 16 20 25 26 35 36 39 46 59 76 85 88 100 |
|||
The quick brown fox jumps over the lazy dog. |
|||
The brown fox jumps lazy dog. quick over the |
|||
The brown dog. fox jumps lazy over quick the</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
The doctest passes with odd and even length lists |
The doctest passes with odd and even length lists. Please see circle_sort.__doc__ for example use and output. |
||
<lang python> |
<lang python> |
||
#python3 |
#python3 |
||
Line 555: | Line 221: | ||
def circle_sort_backend(A:list, L:int, R:int)->'sort A in place, returning the number of swaps': |
def circle_sort_backend(A:list, L:int, R:int)->'sort A in place, returning the number of swaps': |
||
''' |
''' |
||
>>> |
>>> import itertools |
||
>>> |
>>> LR7 = list(range(7)) |
||
>>> for T in itertools.permutations(LR7): |
|||
3 |
|||
... L = list(T) |
|||
... junk = circle_sort(L) |
|||
... if L != LR7: |
|||
... print(L) |
|||
... |
|||
>>> L = [3, 2, 8, 28,] |
>>> L = [3, 2, 8, 28,] |
||
>>> circle_sort(L) |
>>> circle_sort(L) |
||
Line 602: | Line 271: | ||
print(L) |
print(L) |
||
</lang> |
</lang> |
||
=={{header|Racket}}== |
|||
By default this sorts with the numeric <code><</code> but any other |
|||
(diadic) function can be used to compare... e.g. <code>string<?</code>. |
|||
<lang racket>#lang racket |
|||
(define (circle-sort v0 [<? <]) |
|||
(define v (vector-copy v0)) |
|||
(define (swap-if l r) |
|||
(define v.l (vector-ref v l)) |
|||
(define v.r (vector-ref v r)) |
|||
(and (<? v.r v.l) |
|||
(begin (vector-set! v l v.r) (vector-set! v r v.l) #t))) |
|||
(define (inr-cs! L R) |
|||
(cond |
|||
[(>= L (- R 1)) #f] ; covers 0 or 1 vectors |
|||
[else |
|||
(define M (quotient (+ L R) 2)) |
|||
(define I-moved? |
|||
(for/or ([l (in-range L M)] [r (in-range (- R 1) L -1)]) |
|||
(swap-if l r))) |
|||
(define M-moved? (and (odd? (- L R)) (> M 0) (swap-if (- M 1) M))) |
|||
(define L-moved? (inr-cs! L M)) |
|||
(define R-moved? (inr-cs! M R)) |
|||
(or I-moved? L-moved? R-moved? M-moved?)])) |
|||
(let loop () (when (inr-cs! 0 (vector-length v)) (loop))) |
|||
v) |
|||
(define (sort-random-vector) |
|||
(define v (build-vector (+ 2 (random 10)) (λ (i) (random 100)))) |
|||
(define v< (circle-sort v <)) |
|||
(define sorted? (apply <= (vector->list v<))) |
|||
(printf " ~.a\n-> ~.a [~a]\n\n" v v< sorted?)) |
|||
(for ([_ 10]) (sort-random-vector)) |
|||
(circle-sort '#("table" "chair" "cat" "sponge") string<?)</lang> |
|||
{{out}} |
|||
<pre> |
|||
#(36 94 63 51 33) |
|||
-> #(33 36 51 63 94) [#t] |
|||
#(73 74 20 20 79) |
|||
-> #(20 20 73 74 79) [#t] |
|||
#(83 42) |
|||
-> #(42 83) [#t] |
|||
#(53 95 43 33 66 47 1 61 28 96) |
|||
-> #(1 28 33 43 47 53 61 66 95 96) [#t] |
|||
#(71 85) |
|||
-> #(71 85) [#t] |
|||
#(36 85 50 19 88 17 2 53 21) |
|||
-> #(2 17 19 21 36 50 53 85 88) [#t] |
|||
#(5 97 62 21 99 73 17 16 37 28) |
|||
-> #(5 16 17 21 28 37 62 73 97 99) [#t] |
|||
#(12 60 89 90 2 95 9 28) |
|||
-> #(2 9 12 28 60 89 90 95) [#t] |
|||
#(50 32 30 47 63 74) |
|||
-> #(30 32 47 50 63 74) [#t] |
|||
#(63 41) |
|||
-> #(41 63) [#t] |
|||
'#("cat" "chair" "sponge" "table") |
|||
</pre> |
|||
=={{header|REXX}}== |
|||
This REXX version will work with any numbers that REXX supports, including negative and/or floating point numbers. |
|||
<lang rexx>/*REXX program uses a circle sort algorithm to sort an array (or list) of numbers. */ |
|||
parse arg x /*obtain optional arguments from the CL*/ |
|||
if x='' | x="," then x= 6 7 8 9 2 5 3 4 1 /*Not specified? Then use the default.*/ |
|||
call make_array 'before sort:' /*display the list and make an array. */ |
|||
call circleSort # /*invoke the circle sort subroutine. */ |
|||
call make_list ' after sort:' /*make a list and display it to console*/ |
|||
exit /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
circleSort: do while .circleSrt(1, arg(1), 0)\==0; end; return |
|||
make_array: #=words(x); do i=1 for #; @.i=word(x, i); end; say arg(1) x; return |
|||
make_list: y=@.1; do j=2 to #; y=y @.j; end; say arg(1) y; return |
|||
.swap: parse arg a,b; parse value @.a @.b with @.b @.a; swaps=swaps+1; return |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
.circleSrt: procedure expose @.; parse arg lo,hi,swaps /*obtain LO & HI arguments.*/ |
|||
if lo==hi then return swaps /*1 element? Done with sort.*/ |
|||
high=hi; low=lo; mid=(hi-lo) % 2 /*assign some indices. */ |
|||
/* [↓] sort a section of #'s*/ |
|||
do while lo<hi /*sort within a section. */ |
|||
if @.lo>@.hi then call .swap lo,hi /*are numbers out of order ? */ |
|||
lo=lo+1; hi=hi-1 /*add to LO; shrink the HI. */ |
|||
end /*while ··· */ /*just process one section. */ |
|||
_=hi+1 /*point to HI plus one. */ |
|||
if lo==hi & @.lo>@._ then call .swap lo, _ /*numbers still out of order?*/ |
|||
swaps=.circleSrt(low, low+mid, swaps) /*sort the lower section. */ |
|||
swaps=.circleSrt(low+mid+1, high, swaps) /* " " higher " */ |
|||
return swaps /*the section sorting is done*/</lang> |
|||
'''output''' when using the default input: |
|||
<pre> |
|||
before sort: 6 7 8 9 2 5 3 4 1 |
|||
after sort: 1 2 3 4 5 6 7 8 9 |
|||
</pre> |
|||
'''output''' when using the input of: <tt> 2 3 3 5 5 1 1 7 7 6 6 4 4 0 0 </tt> |
|||
<pre> |
|||
before sort: 2 3 3 5 5 1 1 7 7 6 6 4 4 0 0 |
|||
after sort: 0 0 1 1 2 3 3 4 4 5 5 6 6 7 7 |
|||
</pre> |
|||
'''output''' when using the input of: <tt> 2 3 44 44 5.77 +1 -12345 -3 -3.9 1e7 9 </tt> |
|||
<pre> |
|||
before sort: 2 3 44 44 5.77 +1 -12345 -3 -3.9 1e7 0 |
|||
before sort: -12345 -3.9 -3 0 +1 2 3 5.77 44 44 1e7 |
|||
</pre> |
|||
'''output''' when using the input of: <tt> assinine donkey bovine cattle canine dog corvine crow equine horse feline cat hircine goat leporine hare lupine wolf murine rodent piscine fish porcine pig ursine bear vulpine fox </tt> |
|||
<pre> |
|||
before sort: assinine donkey bovine cattle canine dog corvine crow equine horse feline cat hircine goat leporine hare lupine wolf murine rodent piscine fish porcine pig ursine bear vulpine fox |
|||
after sort: assinine bear bovine canine cat cattle corvine crow dog donkey equine feline fish fox goat hare hircine horse leporine lupine murine pig piscine porcine rodent ursine vulpine wolf |
|||
</pre> |
|||
=={{header|Ruby}}== |
|||
<lang ruby>class Array |
|||
def circle_sort! |
|||
while _circle_sort!(0, size-1) > 0 |
|||
end |
|||
self |
|||
end |
|||
private |
|||
def _circle_sort!(lo, hi, swaps=0) |
|||
return swaps if lo == hi |
|||
low, high = lo, hi |
|||
mid = (lo + hi) / 2 |
|||
while lo < hi |
|||
if self[lo] > self[hi] |
|||
self[lo], self[hi] = self[hi], self[lo] |
|||
swaps += 1 |
|||
end |
|||
lo += 1 |
|||
hi -= 1 |
|||
end |
|||
if lo == hi && self[lo] > self[hi+1] |
|||
self[lo], self[hi+1] = self[hi+1], self[lo] |
|||
swaps += 1 |
|||
end |
|||
swaps + _circle_sort!(low, mid) + _circle_sort!(mid+1, high) |
|||
end |
|||
end |
|||
ary = [6, 7, 8, 9, 2, 5, 3, 4, 1] |
|||
puts "before sort: #{ary}" |
|||
puts " after sort: #{ary.circle_sort!}"</lang> |
|||
{{out}} |
|||
<pre> |
|||
before sort: [6, 7, 8, 9, 2, 5, 3, 4, 1] |
|||
after sort: [1, 2, 3, 4, 5, 6, 7, 8, 9] |
|||
</pre> |
|||
=={{header|Sidef}}== |
|||
<lang ruby>func circlesort(arr, beg=0, end=arr.end) { |
|||
var swaps = 0 |
|||
if (beg < end) { |
|||
var (lo, hi) = (beg, end) |
|||
do { |
|||
if (arr[lo] > arr[hi]) { |
|||
arr.swap(lo, hi) |
|||
++swaps |
|||
} |
|||
++hi if (--hi == ++lo) |
|||
} while (lo < hi) |
|||
swaps += circlesort(arr, beg, hi) |
|||
swaps += circlesort(arr, lo, end) |
|||
} |
|||
return swaps |
|||
} |
|||
var numbers = %n(2 3 3 5 5 1 1 7 7 6 6 4 4 0 0) |
|||
do { say numbers } while circlesort(numbers) |
|||
var strs = ["John", "Kate", "Zerg", "Alice", "Joe", "Jane", "Alice"] |
|||
do { say strs } while circlesort(strs)</lang> |
|||
{{out}} |
|||
<pre> |
|||
[2, 3, 3, 5, 5, 1, 1, 7, 7, 6, 6, 4, 4, 0, 0] |
|||
[0, 0, 1, 4, 1, 5, 3, 7, 2, 3, 4, 5, 6, 6, 7] |
|||
[0, 0, 1, 1, 2, 3, 3, 4, 4, 5, 5, 7, 6, 6, 7] |
|||
[0, 0, 1, 1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7] |
|||
["John", "Kate", "Zerg", "Alice", "Joe", "Jane", "Alice"] |
|||
["Alice", "Jane", "Alice", "Joe", "John", "Kate", "Zerg"] |
|||
["Alice", "Alice", "Jane", "Joe", "John", "Kate", "Zerg"] |
|||
</pre> |
|||
=={{header|uBasic/4tH}}== |
=={{header|uBasic/4tH}}== |
||
This one uses the optimized version featured at [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge]. |
|||
<lang>PRINT "Circle sort:" |
<lang>PRINT "Circle sort:" |
||
n = FUNC (_InitArray) |
n = FUNC (_InitArray) |
||
Line 812: | Line 282: | ||
END |
END |
||
_Circle PARAM (3) |
|||
IF a@ = b@ THEN RETURN (c@) |
|||
LOCAL (3) |
|||
c@ = a@ |
|||
d@ = b@ |
|||
e@ = 0 |
|||
LOCAL (3) |
|||
IF c@ = d@ THEN RETURN (0) |
|||
d@ = a@ |
|||
e@ = b@ |
|||
f@ = (b@-a@)/2 |
|||
DO WHILE |
DO WHILE a@ < b@ |
||
IF @( |
IF @(a@) > @(b@) THEN |
||
PUSH @(a@) |
|||
@(a@) = @(b@) |
|||
@(b@) = POP() |
|||
c@ = c@ + 1 |
|||
ENDIF |
|||
a@ = a@ + 1 |
|||
b@ = b@ - 1 |
|||
LOOP |
LOOP |
||
IF a@ = b@ THEN |
|||
e@ = e@ + FUNC (_InnerCircle (a@, d@)) |
|||
IF @(a@) > @(b@+1) THEN |
|||
PUSH @(a@) |
|||
RETURN (e@) |
|||
@(a@) = @(b@+1) |
|||
@(b@+1) = POP() |
|||
c@ = c@ + 1 |
|||
ENDIF |
|||
ENDIF |
|||
c@ = FUNC (_Circle (d@, d@+f@, c@)) |
|||
c@ = FUNC (_Circle (d@+f@+1, e@, c@)) |
|||
RETURN (c@) |
|||
_Circlesort PARAM(1) ' Circle sort |
_Circlesort PARAM(1) ' Circle sort |
||
DO WHILE FUNC (_InnerCircle (0, a@-1)) |
|||
DO WHILE FUNC (_Circle (0, a@-1, 0)) |
|||
LOOP |
LOOP |
||
RETURN |
|||
_Swap PARAM(2) ' Swap two array elements |
|||
PUSH @(a@) |
|||
@(a@) = @(b@) |
|||
@(b@) = POP() |
|||
RETURN |
RETURN |
||
Line 861: | Line 340: | ||
PRINT |
PRINT |
||
RETURN</lang> |
RETURN</lang> |
||
=={{header|zkl}}== |
|||
<lang zkl>fcn circleSort(list){ |
|||
csort:=fcn(list,lo,hi,swaps){ |
|||
if(lo==hi) return(swaps); |
|||
high,low,mid:=hi,lo,(hi-lo)/2; |
|||
while(lo<hi){ |
|||
if(list[lo]>list[hi]){ |
|||
list.swap(lo,hi); |
|||
swaps+=1; |
|||
} |
|||
lo+=1; hi-=1; |
|||
} |
|||
if(lo==hi) |
|||
if (list[lo]>list[hi+1]){ |
|||
list.swap(lo,hi+1); |
|||
swaps+=1; |
|||
} |
|||
swaps=self.fcn(list,low,low + mid,swaps); |
|||
swaps=self.fcn(list,low + mid + 1,high,swaps); |
|||
return(swaps); |
|||
}; |
|||
list.println(); |
|||
while(csort(list,0,list.len()-1,0)){ list.println() } |
|||
list |
|||
}</lang> |
|||
<lang zkl>circleSort(L(6,7,8,9,2,5,3,4,1)); |
|||
circleSort(L(5,-1,101,-4,0,1,8,6,2,3));</lang> |
|||
{{out}} |
|||
<pre> |
|||
L(6,7,8,9,2,5,3,4,1) |
|||
L(1,3,4,2,5,6,7,8,9) |
|||
L(1,2,3,4,5,6,7,8,9) |
|||
L(5,-1,101,-4,0,1,8,6,2,3) |
|||
L(-4,-1,0,3,6,1,2,8,5,101) |
|||
L(-4,-1,0,1,2,3,5,6,8,101) |
|||
</pre> |
|||
=={{header|ZX Spectrum Basic}}== |
|||
A language like ZX BASIC is not the most obvious choice for a routine which depends on local variables and recursion. This program proves that it can be implemented quite efficiently using arrays and global variables. The '''b''' and '''e''' variables are set up in such a way that they can be used for the first recursive call. The variables for the next recursion are saved in array '''s()''' which serves as a stack together with stack pointer '''p'''. |
|||
The size of the stack is determined by the amount of memory on the ZX Spectrum, which is 64KB (or 2<sup>16</sup> bytes). Each call requires two array elements. Note the size of a ZX Spectrum floating point number is 5 bytes, so this stack is slightly oversized. The somewhat strange indexing between both recursions is due to an stack pointer adjustment which was optimized away. |
|||
This version of Circle sort was based on the optimized version on [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge]. It will also show a few asterisks while running, because it will take some time to finish (about two minutes). |
|||
<lang zxbasic> |
|||
10 DIM a(100): DIM s(32): RANDOMIZE : LET p=1: GO SUB 3000: GO SUB 2000: GO SUB 4000 |
|||
20 STOP |
|||
1000 IF b=e THEN RETURN |
|||
1010 LET s(p)=b: LET s(p+1)=e |
|||
1020 IF a(s(p))>a(e) THEN LET t=a(s(p)): LET a(s(p))=a(e): LET a(e)=t: LET c=1 |
|||
1030 LET s(p)=s(p)+1: LET e=e-1: IF s(p)<e THEN GO TO 1020 |
|||
1040 LET p=p+2: GO SUB 1000: LET b=s(p-2): LET e=s(p-1): GO SUB 1000: LET p=p-2: RETURN |
|||
2000 PRINT "*";: LET b=1: LET e=100: LET c=0: GO SUB 1000: IF c>0 THEN GO TO 2000 |
|||
2010 CLS : RETURN |
|||
3000 FOR x=1 TO 100: LET a(x)=RND: NEXT x: RETURN |
|||
4000 FOR x=1 TO 100: PRINT x,a(x): NEXT x: RETURN |
|||
</lang> |
Revision as of 08:09, 17 February 2017
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
Sort an array of integers (of any convenient size) into ascending order using Circlesort. In short, compare the first element to the last element, then the second element to the second last element, etc. Then split the array in two and recurse until there is only one single element in the array, like this:
Before: 6 7 8 9 2 5 3 4 1 After: 1 4 3 5 2 9 8 7 6
Show both the initial, unsorted list and the final sorted list. (Intermediate steps during sorting are optional.) Optimizations (like doing 0.5 log2(n) iterations and then continue with an Insertion sort) are optional.
Pseudo code:
function circlesort (index lo, index hi, swaps) { if lo == hi return (swaps) high := hi low := lo mid := int((hi-lo)/2) while lo < hi { if (value at lo) > (value at hi) { swap.values (lo,hi) swaps++ } lo++ hi-- } if lo == hi if (value at lo) > (value at hi+1) { swap.values (lo,hi+1) swaps++ } swaps := circlesort(low,low+mid,swaps) swaps := circlesort(low+mid+1,high,swaps) return(swaps) } while circlesort (0, sizeof(array)-1, 0)
For more information on Circle sorting, see Sourceforge.
C
<lang c>#include <stdio.h>
int cir_sort_inner(int *x, int n) { int i, j, t, swaps;
if (n < 2) return 0;
for (swaps = i = 0, j = n - 1; i < j; i++, j--) if (x[i] > x[j]) t=x[i], x[i]=x[j], x[j]=t, swaps++;
return swaps + cir_sort_inner(x, j + 1) + cir_sort_inner(x + i, n - i); }
//helper function to show arrays before each call void cir_sort(int *x, int n) { int i, s;
do { for (i = 0; i < n; i++) printf("%d ", x[i]); printf(": %d swaps\n", s = cir_sort_inner(x, n)); } while (s); }
int main(void) { int x[] = { 5, -1, 101, -4, 0, 1, 8, 6, 2, 3 }; cir_sort(x, sizeof(x)/sizeof(x[0]));
return 0; }</lang>
- Output:
5 -1 101 -4 0 1 8 6 2 3 : 9 swaps -4 0 -1 3 6 1 2 5 8 101 : 6 swaps -4 -1 0 1 2 3 5 6 8 101 : 0 swaps
D
<lang d>import std.stdio, std.algorithm, std.array, std.traits;
void circlesort(T)(T[] items) if (isMutable!T) {
uint inner(size_t lo, size_t hi, uint swaps) { if (lo == hi) return swaps; auto high = hi; auto low = lo; immutable mid = (hi - lo) / 2;
while (lo < hi) { if (items[lo] > items[hi]) { swap(items[lo], items[hi]); swaps++; } lo++; hi--; }
if (lo == hi && items[lo] > items[hi + 1]) { swap(items[lo], items[hi + 1]); swaps++; } swaps = inner(low, low + mid, swaps); swaps = inner(low + mid + 1, high, swaps); return swaps; }
if (!items.empty) while (inner(0, items.length - 1, 0)) {}
}
void main() {
import std.random, std.conv;
auto a = [5, -1, 101, -4, 0, 1, 8, 6, 2, 3]; a.circlesort; a.writeln; assert(a.isSorted);
// Fuzzy test. int[30] items; foreach (immutable _; 0 .. 100_000) { auto data = items[0 .. uniform(0, items.length)]; foreach (ref x; data) x = uniform(-items.length.signed * 3, items.length.signed * 3); data.circlesort; assert(data.isSorted); }
}</lang>
- Output:
[-4, -1, 0, 1, 2, 3, 5, 6, 8, 101]
CoffeeScript
<lang>circlesort = (arr, lo, hi, swaps) ->
if lo == hi return (swaps)
high = hi low = lo mid = Math.floor((hi-lo)/2)
while lo < hi if arr[lo] > arr[hi] t = arr[lo] arr[lo] = arr[hi] arr[hi] = t swaps++ lo++ hi--
if lo == hi if arr[lo] > arr[hi+1] t = arr[lo] arr[lo] = arr[hi+1] arr[hi+1] = t swaps++
swaps = circlesort(arr,low,low+mid,swaps) swaps = circlesort(arr,low+mid+1,high,swaps)
return(swaps)
VA = [2,14,4,6,8,1,3,5,7,9,10,11,0,13,12,-1]
while circlesort(VA,0,VA.length-1,0)
console.log VA</lang>
Output:
console: -1,1,0,3,4,5,8,12,2,9,6,10,7,13,11,14 console: -1,0,1,3,2,5,4,8,6,7,9,12,10,11,13,14 console: -1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14
Forth
<lang>defer precedes ( addr addr -- flag ) variable (swaps) \ keeps track of swaps
[UNDEFINED] cell- [IF] : cell- 1 cells - ; [THEN]
- (compare) ( a1 a2 -- a1 a2)
over @ over @ precedes \ if swapped, increment (swaps) if over over over @ over @ swap rot ! swap ! 1 (swaps) +! then
- (circlesort) ( a n --)
dup 1 > if over over ( array len) 1- cells over + swap ( 'end 'begin) begin over over > \ if we didn't pass the middle while \ check and swap opposite elements (compare) swap cell- swap cell+ repeat \ check if there's a middle element over over = if cell- (compare) then drop drop over over 2/ recurse \ sort first partition dup 2/ cells rot + swap dup 2/ - recurse exit then \ sort second partition drop drop \ nothing to sort
- sort begin 0 (swaps) ! over over (circlesort) (swaps) @ 0= until drop drop ;
- noname < ; is precedes
10 constant /sample create sample 5 , -1 , 101 , -4 , 0 , 1 , 8 , 6 , 2 , 3 ,
- .sample sample /sample cells bounds do i ? 1 cells +loop ;
sample /sample sort .sample</lang>
Python
The doctest passes with odd and even length lists. Please see circle_sort.__doc__ for example use and output. <lang python>
- python3
- tests: expect no output.
- doctest with python3 -m doctest thisfile.py
- additional tests: python3 thisfile.py
def circle_sort_backend(A:list, L:int, R:int)->'sort A in place, returning the number of swaps':
>>> import itertools >>> LR7 = list(range(7)) >>> for T in itertools.permutations(LR7): ... L = list(T) ... junk = circle_sort(L) ... if L != LR7: ... print(L) ... >>> L = [3, 2, 8, 28,] >>> circle_sort(L) 1 >>> print(L) [2, 3, 8, 28] n = R-L if n < 2: return 0 swaps = 0 m = n//2 for i in range(m): if A[R-(i+1)] < A[L+i]: (A[R-(i+1)], A[L+i],) = (A[L+i], A[R-(i+1)],) swaps += 1 if (n & 1) and (A[L+m] < A[L+m-1]): (A[L+m-1], A[L+m],) = (A[L+m], A[L+m-1],) swaps += 1 return swaps + circle_sort_backend(A, L, L+m) + circle_sort_backend(A, L+m, R)
def circle_sort(L:list)->'sort A in place, returning the number of swaps':
swaps = 0 s = 1 while s: s = circle_sort_backend(L, 0, len(L)) swaps += s return swaps
- more tests!
if __name__ == '__main__':
from random import shuffle for i in range(309): L = list(range(i)) M = L[:] shuffle(L) N = L[:] circle_sort(L) if L != M: print(len(L)) print(N) print(L)
</lang>
uBasic/4tH
<lang>PRINT "Circle sort:"
n = FUNC (_InitArray) PROC _ShowArray (n) PROC _Circlesort (n) PROC _ShowArray (n)
END
_Circle PARAM (3)
IF a@ = b@ THEN RETURN (c@)
LOCAL (3) d@ = a@ e@ = b@ f@ = (b@-a@)/2
DO WHILE a@ < b@ IF @(a@) > @(b@) THEN PUSH @(a@) @(a@) = @(b@) @(b@) = POP() c@ = c@ + 1 ENDIF a@ = a@ + 1 b@ = b@ - 1 LOOP
IF a@ = b@ THEN IF @(a@) > @(b@+1) THEN PUSH @(a@) @(a@) = @(b@+1) @(b@+1) = POP() c@ = c@ + 1 ENDIF ENDIF
c@ = FUNC (_Circle (d@, d@+f@, c@)) c@ = FUNC (_Circle (d@+f@+1, e@, c@))
RETURN (c@)
_Circlesort PARAM(1) ' Circle sort
DO WHILE FUNC (_Circle (0, a@-1, 0)) LOOP
RETURN
_InitArray ' Init example array
PUSH 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
FOR i = 0 TO 9 @(i) = POP() NEXT
RETURN (i)
_ShowArray PARAM (1) ' Show array subroutine
FOR i = 0 TO a@-1 PRINT @(i), NEXT
RETURN</lang>