Sorting algorithms/Cocktail sort
You are encouraged to solve this task according to the task description, using any language you may know.
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
The cocktail sort is an improvement on the Bubble 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. Pseudocode for the algorithm (from the wikipedia):
function cocktailSort( A : list of sortable items )
do
swapped := false
for each i in 0 to length( A ) - 2 do
if A[ i ] > A[ i+1 ] then // test whether the two
// elements are in the wrong
// order
swap( A[ i ], A[ i+1 ] ) // let the two elements
// change places
swapped := true;
if swapped = false then
// we can exit the outer loop here if no swaps occurred.
break do-while loop;
swapped := false
for each i in length( A ) - 2 down to 0 do
if A[ i ] > A[ i+1 ] then
swap( A[ i ], A[ i+1 ] )
swapped := true;
while swapped; // if no elements have been swapped,
// then the list is sorted
Ada
<lang Ada>with Ada.Text_Io; use Ada.Text_Io;
procedure Cocktail_Sort_Test is
procedure Cocktail_Sort (Item : in out String) is
procedure Swap(Left, Right : in out Character) is
Temp : Character := Left;
begin
Left := Right;
Right := Temp;
end Swap;
Swapped : Boolean := False;
begin
loop
for I in 1..Item'Last - 1 loop
if Item(I) > Item(I + 1) then
Swap(Item(I), Item(I + 1));
Swapped := True;
end if;
end loop;
if not Swapped then
for I in reverse 1..Item'Last - 1 loop
if Item(I) > Item(I + 1) then
Swap(Item(I), Item(I + 1));
Swapped := True;
end if;
end loop;
end if;
exit when not Swapped;
Swapped := False;
end loop;
end Cocktail_Sort;
Data : String := "big fjords vex quick waltz nymph";
begin
Put_Line(Data); Cocktail_Sort(Data); Put_Line(Data);
end Cocktail_Sort_Test;</lang>
ALGOL 68
<lang algol68>MODE DATA = CHAR; PROC swap = (REF DATA a,b)VOID:(
DATA tmp:=a; a:=b; b:=tmp
);
PROC cocktail sort = (REF[]DATA a)VOID: (
WHILE
BOOL swapped := FALSE;
FOR i FROM LWB a TO UPB a - 1 DO
IF a[ i ] > a[ i + 1 ] THEN # test whether the two elements are in the wrong order #
swap( a[ i ], a[ i + 1 ] ); # let the two elements change places #
swapped := TRUE
FI
OD;
IF NOT swapped THEN
# we can exit the outer loop here if no swaps occurred. #
break do while loop
FI;
swapped := FALSE;
FOR i FROM UPB a - 1 TO LWB a DO
IF a[ i ] > a[ i + 1 ] THEN
swap( a[ i ], a[ i + 1 ] );
swapped := TRUE
FI
OD;
- WHILE # swapped # if no elements have been swapped, then the list is sorted #
DO SKIP OD; break do while loop: SKIP
);
[32]CHAR data := "big fjords vex quick waltz nymph"; cocktail sort(data); print(data)</lang>
Output:
abcdefghiijklmnopqrstuvwxyz
Alternatively - when the data records are large - the data can be manipulated indirectly, thus removing the need to actually swap large chunks of memory as only addresses are swapped. <lang algol68>MODE DATA = REF CHAR; PROC swap = (REF DATA a,b)VOID:(
DATA tmp:=a; a:=b; b:=tmp
);
PROC (REF[]DATA a)VOID cocktail sort;
[32]CHAR data := "big fjords vex quick waltz nymph"; [UPB data]DATA ref data; FOR i TO UPB data DO ref data[i] := data[i] OD; cocktail sort(ref data); FOR i TO UPB ref data DO print(ref data[i]) OD; print(new line); print((data))</lang>
Output:
abcdefghiijklmnopqrstuvwxyz big fjords vex quick waltz nymph
The above two routines both scan the entire width of the array, in both directions, even though the first and last elements of each sweep had already reached their final destination during the previous pass. The solution is to zig-zag, but have the sweeps shorten and converge on the centre element. This reduces the number of comparisons required by about 50%. <lang algol68>PROC odd even sort = (REF []DATA a)VOID: (
FOR offset FROM 0 DO
BOOL swapped := FALSE;
FOR i FROM LWB a + offset TO UPB a - 1 - offset DO
IF a[ i ] > a[ i + 1 ] THEN # test whether the two elements are in the wrong order #
swap( a[ i ], a[ i + 1 ] ); # let the two elements change places #
swapped := TRUE
FI
OD;
# we can exit the outer loop here if no swaps occurred. #
IF NOT swapped THEN break do od loop FI;
swapped := FALSE;
FOR i FROM UPB a - 1 - offset - 1 BY - 1 TO LWB a + offset DO
IF a[ i ] > a[ i + 1 ] THEN
swap( a[ i ], a[ i + 1 ] );
swapped := TRUE
FI
OD;
# if no elements have been swapped, then the list is sorted #
IF NOT swapped THEN break do od loop FI;
OD;
break do od loop: SKIP
);</lang>
AutoHotkey
contributed by Laszlo on the ahk forum <lang AutoHotkey>MsgBox % CocktailSort("") MsgBox % CocktailSort("xxx") MsgBox % CocktailSort("3,2,1") MsgBox % CocktailSort("dog,000000,xx,cat,pile,abcde,1,cat,zz,xx,z")
CocktailSort(var) { ; SORT COMMA SEPARATED LIST
StringSplit array, var, `, ; make array i0 := 1, i1 := array0 ; start, end
Loop { ; break when sorted
Changed =
Loop % i1-- -i0 { ; last entry will be in place
j := i0+A_Index, i := j-1
If (array%j% < array%i%) ; swap?
t := array%i%, array%i% := array%j%, array%j% := t
,Changed = 1 ; change has happened
}
IfEqual Changed,, Break
Loop % i1-i0++ { ; first entry will be in place
i := i1-A_Index, j := i+1
If (array%j% < array%i%) ; swap?
t := array%i%, array%i% := array%j%, array%j% := t
,Changed = 1 ; change has happened
}
IfEqual Changed,, Break
}
Loop % array0 ; construct string from sorted array
sorted .= "," . array%A_Index%
Return SubStr(sorted,2) ; drop leading comma
}</lang>
AWK
Sort the standard input and print it to standard output <lang awk>{
line[NR] = $0
} END { # sort it with cocktail sort
swapped = 0
do {
for(i=1; i < NR; i++) {
if ( line[i] > line[i+1] ) {
t = line[i] line[i] = line[i+1] line[i+1] = t swapped = 1
}
}
if ( swapped == 0 ) break
swapped = 0
for(i=NR-1; i >= 1; i--) {
if ( line[i] > line[i+1] ) {
t = line[i] line[i] = line[i+1] line[i+1] = t swapped = 1
}
}
} while ( swapped == 1 )
#print it
for(i=1; i <= NR; i++) {
print line[i]
}
}</lang>
C
<lang c>#include <stdio.h>
- include <stdbool.h>
- define COCKTSORT \
if ( a[i] > a[i+1] ) { \
int temp = a[i]; \ a[i] = a[i+1]; \ a[i+1] = temp; \ swapped = true; \
}
void cocktailsort(int *a, unsigned int l) {
bool swapped = false; int i;
do {
for(i=0; i < (l-1); i++) {
COCKTSORT;
}
if ( ! swapped ) break;
swapped = false;
for(i= l - 2; i >= 0; i--) {
COCKTSORT;
}
} while(swapped);
}</lang> <lang c>int array[10] = { 5, -1, 101, -4, 0, 1, 8, 6, 2, 3 };
int main() {
int i;
cocktailsort(array, 10);
for(i=0; i < 10; i++) {
printf("%d\n", array[i]);
}
}</lang>
C#
<lang csharp>public static void cocktailSort(int[] A)
{
bool swapped;
do
{
swapped = false;
for (int i = 0; i <= A.Length - 2; i++)
{
if (A[i] > A[i + 1])
{
//test whether the two elements are in the wrong order
int temp = A[i];
A[i] = A[i + 1];
A[i + 1] = temp;
swapped = true;
}
}
if (!swapped)
{
//we can exit the outer loop here if no swaps occurred.
break;
}
swapped = false;
for (int i = A.Length - 2; i >= 0; i--)
{
if (A[i] > A[i + 1])
{
int temp = A[i];
A[i] = A[i + 1];
A[i + 1] = temp;
swapped = true;
}
}
//if no elements have been swapped, then the list is sorted
} while (swapped);
}</lang>
Common Lisp
This version works on lists and vectors alike. The vector implementation is coded directly. The list version uses an intermediate vector.
<lang lisp>(defun cocktail-sort-vector (vector predicate &aux (len (length vector)))
(labels ((scan (start step &aux swapped)
(loop for i = start then (+ i step) while (< 0 i len) do
(when (funcall predicate (aref vector i)
(aref vector (1- i)))
(rotatef (aref vector i)
(aref vector (1- i)))
(setf swapped t)))
swapped))
(loop while (and (scan 1 1)
(scan (1- len) -1))))
vector)
(defun cocktail-sort (sequence predicate)
(etypecase sequence
(vector (cocktail-sort-vector sequence predicate))
(list (map-into sequence 'identity
(cocktail-sort-vector (coerce sequence 'vector)
predicate)))))</lang>
D
This is generic solution based on templates. Main function is quite similar to provided pseudo-code. <lang D>import tango.io.Stdout; import tango.core.Variant; import tango.core.Traits;
// objects must have opIndex method template GetItemType(T) { alias ReturnTypeOf!(T.opIndex) GetItemType; } // specialization for arrays template GetItemType(T : T[]) { alias T GetItemType; }
void cocktailSort(T)(T elements) {
static assert (isArray!(T) || isStaticArray!(T) || isObject!(T), "array or object required");
alias GetItemType!(T) _itemT; bool swapped;
void swap(T a, uint pos) {
_itemT temp = a[pos]; a[pos] = a[pos+1]; a[pos+1] = temp; swapped = true;
}
do {
swapped = false;
foreach (idx, ref elem; elements[0 .. elements.length-1]) {
if (elem > elements[idx+1])
swap (elements, idx);
}
if (!swapped) break;
swapped = false;
foreach_reverse (idx, ref elem; elements[0 .. elements.length-1]) {
if (elem > elements[idx+1])
swap (elements, idx);
}
} while(swapped);
}</lang>Sample usage:<lang D>class SampleContainer {
char[][] data;
public:
this () {
data ~= "John";
data ~= "Kate";
data ~= "Alice";
data ~= "Joe";
data ~= "Jane";
}
char[] opIndex(uint pos) { return data[pos]; }
char[] opIndexAssign(char[] s, uint pos) { return (data[pos] = s); }
char[][] opSlice(uint a, uint b) { return data[a..b]; }
uint length() { return data.length; }
char[] toString() {
char[] ret = "[";
foreach (elem; data) ret ~= elem ~ ", ";
return ret ~ "]";
}
}
void main() {
auto y = new SampleContainer; auto x = [5, 1, 7, 3, 6, 4, 2 ]; cocktailSort(x); Stdout (x).newline; cocktailSort(y); Stdout (y).newline;
}</lang>
Output:
[ 1, 2, 3, 4, 5, 6, 7 ] [Alice, Jane, Joe, John, Kate, ]
E
<lang e>/** Cocktail sort (in-place) */ def cocktailSort(array) {
def swapIndexes := 0..(array.size() - 2)
def directions := [swapIndexes, swapIndexes.descending()]
while (true) {
for direction in directions {
var swapped := false
for a ? (array[a] > array[def b := a + 1]) in direction {
def t := array[a]
array[a] := array[b]
array[b] := t
swapped := true
}
if (!swapped) { return }
}
}
}</lang>
Note that this solution contains no repeated code to handle the forward and reverse passes.
Fortran
<lang fortran>PROGRAM COCKTAIL
IMPLICIT NONE
INTEGER :: intArray(10) = (/ 4, 9, 3, -2, 0, 7, -5, 1, 6, 8 /)
WRITE(*,"(A,10I5)") "Unsorted array:", intArray CALL Cocktail_sort(intArray) WRITE(*,"(A,10I5)") "Sorted array :", intArray
CONTAINS
SUBROUTINE Cocktail_sort(a)
INTEGER, INTENT(IN OUT) :: a(:)
INTEGER :: i, bottom, top, temp
LOGICAL :: swapped
bottom = 1
top = SIZE(a) - 1
DO WHILE (bottom < top )
swapped = .FALSE.
DO i = bottom, top
IF (array(i) > array(i+1)) THEN
temp = array(i)
array(i) = array(i+1)
array(i+1) = temp
swapped = .TRUE.
END IF
END DO
IF (.NOT. swapped) EXIT
DO i = top, bottom + 1, -1
IF (array(i) < array(i-1)) THEN
temp = array(i)
array(i) = array(i-1)
array(i-1) = temp
swapped = .TRUE.
END IF
END DO
IF (.NOT. swapped) EXIT
bottom = bottom + 1
top = top - 1
END DO
END SUBROUTINE Cocktail_sort
END PROGRAM COCKTAIL</lang>
Haskell
<lang haskell>cocktailSort :: Ord a => [a] -> [a] cocktailSort l
| not swapped1 = l
| not swapped2 = reverse $ l1
| otherwise = cocktailSort l2
where (swapped1, l1) = swappingPass (>) (False, []) l
(swapped2, l2) = swappingPass (<) (False, []) l1
swappingPass :: Ord a => (a -> a -> Bool) -> (Bool, [a]) -> [a] -> (Bool, [a])
swappingPass op (swapped, l) (x1 : x2 : xs)
| op x1 x2 = swappingPass op (True, x2 : l) (x1 : xs)
| otherwise = swappingPass op (swapped, x1 : l) (x2 : xs)
swappingPass _ (swapped, l) [x] = (swapped, x : l)
swappingPass _ pair [] = pair</lang>
J
<lang j>bigToLeft=: (([ (>. , <.) {.@]) , }.@])/ smallToLeft=: (([ (<. , >.) {.@]) , }.@])/ cocktailSort=: |. @: (|. @: smallToLeft @: |. @: bigToLeft ^:_)</lang>
Test run:
<lang j> ?. 10 $ 10 4 6 8 6 5 8 6 6 6 9
cocktailSort ?. 10 $ 10
4 5 6 6 6 6 6 8 8 9</lang>
As is usual with J, /:~ is the preferred method of sorting in practice.
Java
This algorithm sorts in place. Call it with a copy of the array to preserve the unsorted order. <lang java>public static void cocktailSort( int[] A ){ boolean swapped; do{ swapped = false; for (int i =0; i<= A.length - 2;i++){ if (A[ i ] > A[ i + 1 ]) { //test whether the two elements are in the wrong order int temp = A[i]; A[i] = A[i+1]; A[i+1]=temp; swapped = true; } } if (!swapped) { //we can exit the outer loop here if no swaps occurred. break; } swapped = false; for (int i= A.length - 2;i>=0;i--){ if (A[ i ] > A[ i + 1 ]){ int temp = A[i]; A[i] = A[i+1]; A[i+1]=temp; swapped = true; } } //if no elements have been swapped, then the list is sorted } while (swapped); }</lang>
Lua
<lang Lua> function cocktailSort( A )
local swapped
repeat
swapped = false
for i = 1, #A - 1 do
if A[ i ] > A[ i+1 ] then
A[ i ], A[ i+1 ] = A[ i+1 ] ,A[i]
swapped=true
end
end
if swapped == false then
break -- repeatd loop;
end
for i = #A - 1,1,-1 do
if A[ i ] > A[ i+1 ] then
A[ i ], A[ i+1 ] = A[ i+1 ] , A[ i ]
swapped=true
end
end
until swapped==false
end
</lang>
Example: <lang lua> list = { 5, 6, 1, 2, 9, 14, 2, 15, 6, 7, 8, 97 } cocktailSort(list) for i=1,#list do
print(list[i]j)
end </lang>
MAXScript
<lang maxscript>fn cocktailSort arr = (
local swapped = true
while swapped do
(
swapped = false
for i in 1 to (arr.count-1) do
(
if arr[i] > arr[i+1] then
(
swap arr[i] arr[i+1]
swapped = true
)
)
if not swapped then exit
for i in (arr.count-1) to 1 by -1 do
(
if arr[i] > arr[i+1] then
(
swap arr[i] arr[i+1]
swapped = true
)
)
)
return arr
)</lang>
OCaml
<lang ocaml>let swap a i j =
let tmp = a.(i) in a.(i) <- a.(j); a.(j) <- tmp;
let cocktail_sort a =
let begin_ = ref(-1)
and end_ = ref(Array.length a - 2) in
let swapped = ref true in
try while !swapped do
swapped := false;
incr begin_;
for i = !begin_ to !end_ do
if a.(i) > a.(i+1) then begin
swap a (i) (i+1);
swapped := true;
end;
done;
if !swapped = false then raise Exit;
swapped := false;
decr end_;
for i = !end_ downto !begin_ do
if a.(i) > a.(i+1) then begin
swap a (i) (i+1);
swapped := true
end;
done;
done with Exit -> ()
let () =
let a = [| 3; 7; 4; 9; 6; 1; 8; 5; 2; |] in cocktail_sort a; Array.iter (Printf.printf " %d") a; print_newline();
- </lang>
outputs:
1 2 3 4 5 6 7 8 9
Octave
<lang octave>function sl = cocktailsort(l)
swapped = true;
while(swapped)
swapped = false;
for i = 1:(length(l)-1)
if ( l(i) > l(i+1) )
t = l(i); l(i) = l(i+1); l(i+1) = t; swapped = true;
endif
endfor
if ( !swapped )
break;
endif
swapped = false;
for i = (length(l)-1):-1:1
if ( l(i) > l(i+1) )
t = l(i); l(i) = l(i+1); l(i+1) = t; swapped = true;
endif endfor endwhile sl = l;
endfunction</lang>
<lang octave>s = cocktailsort([5, -1, 101, -4, 0, \ 1, 8, 6, 2, 3 ]); disp(s);</lang>
Perl
<lang perl>use strict; use warnings;
my @B=qw(t h e q u i c k b r o w n f o x j u m p s o v e r t h e l a z y d o g); print "@B\n"; my @C=cocktailSort(@B); print "@C\n";
- cocktailSort #####################
sub cocktailSort { #( A : list of sortable items ) defined as:
my @A = @_;
my $swapped = 1;
while ($swapped == 1) {
$swapped = 0;
for (my $i=0; $i<($#A-1); $i+=1) {
if ($A[$i] gt $A[$i+1]) { # test whether the two
# elements are in the wrong
# order
($A[$i+1], $A[$i])=($A[$i], $A[$i+1]); # let the two elements
# change places
$swapped = 1;
}
}
if ($swapped == 0) {
# we can exit the outer loop here if no swaps occurred.
print "no more swaps";
}
else {
$swapped = 0;
for (my $i=($#A-1); $i>0 ; $i-=1) {
if($A[$i] gt $A[$i+1]) {
($A[$i+1], $A[$i])=($A[$i], $A[$i+1]);
$swapped = 1;
}
}
}
- if no elements have been swapped,
- then the list is sorted
}
return (@A);
- end sub
}</lang>
Python
This implementation takes advantage of the identical processing of the two for loops and that a range is a first-class object in Python.<lang python>def cocktailSort(A):
up = range(len(A)-1)
while True:
for indices in (up, reversed(up)):
swapped = False
for i in indices:
if A[i] > A[i+1]:
A[i], A[i+1] = A[i+1], A[i]
swapped = True
if not swapped:
return</lang>
Usage: <lang python>test1 = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0] cocktailSort(test1) print test1
- >>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
test2=list('big fjords vex quick waltz nymph') cocktailSort(test2) print .join(test2)
- >>> abcdefghiijklmnopqrstuvwxyz</lang>
R
<lang R>cocktailsort <- function(x) {
lenx <- length(x)
repeat
{
swapped <- FALSE
for(i in 1:(lenx-1))
{
if(x[i] > x[i+1])
{
temp <- x[i]
x[i] <- x[i+1]
x[i+1] <- temp
swapped <- TRUE
}
}
if(!swapped) break
swapped <- FALSE
for(i in (lenx-1):1)
{
if(x[i] > x[i+1])
{
temp <- x[i]
x[i] <- x[i+1]
x[i+1] <- temp
swapped <- TRUE
}
}
if(!swapped) break
}
x
}
print(cocktailsort(c(5, -1, 101, -4, 0, 1, 8, 6, 2, 3)))</lang>
Ruby
<lang ruby>class Array
def cocktailsort!
begin
swapped = false
0.upto(length - 2) do |i|
if self[i] > self[i + 1]
self[i], self[i + 1] = self[i + 1], self[i]
swapped = true
end
end
break if not swapped
swapped = false
(length - 2).downto(0) do |i|
if self[i] > self[i + 1]
self[i], self[i + 1] = self[i + 1], self[i]
swapped = true
end
end
end while swapped
self
end
end ary = [7,6,5,9,8,4,3,1,2,0] ary.cocktailsort!
- => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</lang>
Slate
<lang slate>s@(Sequence traits) cocktailSort [ |swapped|
swapped: False.
s size <= 1 ifTrue: [^ s].
[{0 to: s size - 2. s size - 2 downTo: 0}
do: [|:range| range do: [|:index| (s at: index) > (s at: index + 1) ifTrue: [s swap: index with: index + 1. swapped: True]].
swapped ifFalse: [^ s].
swapped: False].
] loop
].</lang>
<lang slate>slate[1]> #( 10 9 8 7 6 0 -5) cocktailSort. {-5. 0. 6. 7. 8. 9. 10}</lang>
Smalltalk
<lang smalltalk>OrderedCollection extend [
swap: indexA and: indexB [
|t|
t := self at: indexA.
self at: indexA put: (self at: indexB).
self at: indexB put: t
]
cocktailSort [
|swapped|
[
swapped := false.
1 to: (self size - 1) do: [ :i |
(self at: i) > (self at: (i+1)) ifTrue: [
self swap: i and: (i+1).
swapped := true
]
].
swapped ifFalse: [ ^ self ].
swapped := false.
(self size - 1) to: 1 by: -1 do: [ :i |
(self at: i) > (self at: (i+1)) ifTrue: [
self swap: i and: (i+1).
swapped := true
]
].
swapped
] whileTrue: [ ].
^ self
]
].</lang>
<lang smalltalk>(#( 10 9 8 7 6 0 -5) asOrderedCollection cocktailSort) printNl.</lang>
Tcl
uses package struct::list from
to swap list elements
<lang tcl>package require Tcl 8.5 package require struct::list
proc cocktailsort {A} {
set len [llength $A]
set swapped true
while {$swapped} {
set swapped false
for {set i 0} {$i < $len - 1} {incr i} {
set j [expr {$i + 1}]
if {[lindex $A $i] > [lindex $A $j]} {
struct::list swap A $i $j
set swapped true
}
}
if { ! $swapped} {
break
}
set swapped false
for {set i [expr {$len - 2}]} {$i >= 0} {incr i -1} {
set j [expr {$i + 1}]
if {[lindex $A $i] > [lindex $A $j]} {
struct::list swap A $i $j
set swapped true
}
}
}
return $A
}
puts [cocktailsort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</lang>
Ursala
The same function is used for the traversal in each direction, in one case parameterized by the given predicate and in the other by its negation. Lists are used rather than arrays. The fold combinator (=>) avoids explicit recursion. <lang Ursala>#import std
ctsort = ^=+ +^|(==?/~&l+ @r+ ~&x++ @x,^/~&)+ ("p". =><> ~&r?\~&C "p"?lrhPX/~&C ~&rhPlrtPCC)^~/not ~&</lang> test program: <lang Ursala>#cast %s
test = ctsort(lleq) 'mdfdguldxisgbxjtqkadfkslakwkyioukdledbig'</lang> output:
'aabbddddddeffgggiiijkkkkklllmoqsstuuwxxy'