Sorting algorithms/Comb sort

From Rosetta Code
< Sorting algorithms(Redirected from Comb sort)
Jump to: navigation, search
This task has been clarified. Its programming examples are in need of review to ensure that they still fit the requirements of the task.
Task
Sorting algorithms/Comb 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 other sorting algorithms, see Category:Sorting Algorithms, or:
O(n logn) Sorts
Heapsort | Mergesort | Quicksort
O(n log2n) Sorts
Shell Sort
O(n2) Sorts
Bubble sort | Cocktail sort | Comb sort | Gnome sort | Insertion sort | Selection sort | Strand sort
Other Sorts
Bead sort | Bogosort | Counting sort | Pancake sort | Permutation sort | Radix sort | Sleep sort | Stooge sort

The Comb Sort is a variant of the Bubble Sort. Like the Shell sort, the Comb Sort increases the gap used in comparisons and exchanges (dividing the gap by (1-e^{-\varphi})^{-1} \approx 1.247330950103979 works best, but 1.3 may be more practical). Some implementations use the insertion sort once the gap is less than a certain amount. See the article on Wikipedia. Variants:

  • Combsort11 makes sure the gap ends in (11, 8, 6, 4, 3, 2, 1), which is significantly faster than the other two possible endings
  • Combsort with different endings changes to a more efficient sort when the data is almost sorted (when the gap is small). Comb sort with a low gap isn't much better than the Bubble Sort.

Pseudocode:

function combsort(array input)
    gap := input.size //initialize gap size
    loop until gap = 1 and swaps = 0
        //update the gap value for a next comb. Below is an example
        gap := int(gap / 1.25)
        if gap < 1
          //minimum gap is 1
          gap := 1
        end if
        i := 0
        swaps := 0 //see Bubble Sort for an explanation
        //a single "comb" over the input list
        loop until i + gap >= input.size //see Shell sort for similar idea
            if input[i] > input[i+gap]
                swap(input[i], input[i+gap])
                swaps := 1 // Flag a swap has occurred, so the
                           // list is not guaranteed sorted
            end if
            i := i + 1
        end loop
    end loop
end function

Contents

[edit] ActionScript

function combSort(input:Array)
{
var gap:uint = input.length;
var swapped:Boolean = false;
while(gap > 1 || swapped)
{
gap /= 1.25;
swapped = false;
for(var i:uint = 0; i + gap < input.length; i++)
{
if(input[i] > input[i+gap])
{
var tmp = input[i];
input[i] = input[i+gap];
input[i+gap]=tmp;
swapped = true;
}
}
}
return input;
}

[edit] Ada

with Ada.Text_IO;
procedure Comb_Sort is
generic
type Element_Type is private;
type Index_Type is range <>;
type Array_Type is array (Index_Type range <>) of Element_Type;
with function ">" (Left, Right : Element_Type) return Boolean is <>;
with function "+" (Left : Index_Type; Right : Natural) return Index_Type is <>;
with function "-" (Left : Index_Type; Right : Natural) return Index_Type is <>;
procedure Comb_Sort (Data: in out Array_Type);
 
procedure Comb_Sort (Data: in out Array_Type) is
procedure Swap (Left, Right : in Index_Type) is
Temp : Element_Type := Data(Left);
begin
Data(Left)  := Data(Right);
Data(Right) := Temp;
end Swap;
Gap : Natural := Data'Length;
Swap_Occured : Boolean;
begin
loop
Gap := Natural (Float(Gap) / 1.25 - 0.5);
if Gap < 1 then
Gap := 1;
end if;
Swap_Occured := False;
for I in Data'First .. Data'Last - Gap loop
if Data (I) > Data (I+Gap) then
Swap (I, I+Gap);
Swap_Occured := True;
end if;
end loop;
exit when Gap = 1 and not Swap_Occured;
end loop;
end Comb_Sort;
 
type Integer_Array is array (Positive range <>) of Integer;
procedure Int_Comb_Sort is new Comb_Sort (Integer, Positive, Integer_Array);
Test_Array : Integer_Array := (1, 3, 256, 0, 3, 4, -1);
begin
Int_Comb_Sort (Test_Array);
for I in Test_Array'Range loop
Ada.Text_IO.Put (Integer'Image (Test_Array (I)));
end loop;
Ada.Text_IO.New_Line;
end Comb_Sort;

Output:

-1 0 1 3 3 4 256

[edit] AutoHotkey

List1 = 23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78
List2 = 88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70
 
List2Array(List1, "MyArray")
CombSort("MyArray")
MsgBox, % List1 "`n" Array2List("MyArray")
 
List2Array(List2, "MyArray")
CombSort("MyArray")
MsgBox, % List2 "`n" Array2List("MyArray")
 
 
 
;---------------------------------------------------------------------------
CombSort(Array) { ; CombSort of Array %Array%, length = %Array%0
;---------------------------------------------------------------------------
Gap := %Array%0
While Gap > 1 Or Swaps {
If (Gap > 1)
Gap := 4 * Gap // 5
i := Swaps := False
While (j := ++i + Gap) <= %Array%0 {
If (%Array%%i% > %Array%%j%) {
Swaps := True
%Array%%i% := (%Array%%j% "", %Array%%j% := %Array%%i%)
}
}
}
}
 
 
 
;---------------------------------------------------------------------------
List2Array(List, Array) { ; creates an array from a comma separated list
;---------------------------------------------------------------------------
global
StringSplit, %Array%, List, `,
}
 
 
 
;---------------------------------------------------------------------------
Array2List(Array) { ; returns a comma separated list from an array
;---------------------------------------------------------------------------
Loop, % %Array%0
List .= (A_Index = 1 ? "" : ",") %Array%%A_Index%
Return, List
}

Message (1) box shows:

23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78
12,14,23,24,24,31,35,38,46,51,57,57,58,76,78,89,92,95,97,99

Message (2) box shows:

88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70
0,4,5,8,14,18,20,31,33,44,62,70,73,75,76,78,81,82,84,88

[edit] AWK

function combsort( a, len,    gap, igap, swap, swaps, i )
{
gap = len
swaps = 1
 
while( gap > 1 || swaps )
{
gap /= 1.2473;
if ( gap < 1 ) gap = 1
i = swaps = 0
while( i + gap < len )
{
igap = i + int(gap)
if ( a[i] > a[igap] )
{
swap = a[i]
a[i] = a[igap]
a[igap] = swap
swaps = 1
}
i++;
}
}
}
 
BEGIN {
a[0] = 5
a[1] = 2
a[2] = 7
a[3] = -11
a[4] = 6
a[5] = 1
 
combsort( a, length(a) )
 
for( i=0; i<length(a); i++ )
print a[i]
}

[edit] BBC BASIC

DEF PROC_CombSort11(Size%)
 
gap%=Size%
REPEAT
IF gap% > 1 THEN
gap%=gap% / 1.3
IF gap%=9 OR gap%=10 gap%=11
ENDIF
I% = 1
Finished%=TRUE
REPEAT
IF data%(I%) > data%(I%+gap%) THEN
SWAP data%(I%),data%(I%+gap%)
Finished% = FALSE
ENDIF
I%+=1
UNTIL I%+gap% > Size%
UNTIL gap%=1 AND Finished%
 
ENDPROC

[edit] C

Implementation of Combsort11. Its efficiency can be improved by just switching to Insertion sort when the gap size becomes less than 10.

void Combsort11(double a[], int nElements)
{
int i, j, gap, swapped = 1;
double temp;
 
gap = nElements;
while (gap > 1 || swapped == 1)
{
gap = gap * 10 / 13;
if (gap == 9 || gap == 10) gap = 11;
if (gap < 1) gap = 1;
swapped = 0;
for (i = 0, j = gap; j < nElements; i++, j++)
{
if (a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
swapped = 1;
}
}
}
}

[edit] C++

This is copied from the Wikipedia article.

template<class ForwardIterator>
void combsort ( ForwardIterator first, ForwardIterator last )
{
static const double shrink_factor = 1.247330950103979;
typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;
difference_type gap = std::distance(first, last);
bool swaps = true;
 
while ( (gap > 1) || (swaps == true) ){
if (gap > 1)
gap = static_cast<difference_type>(gap/shrink_factor);
 
swaps = false;
ForwardIterator itLeft(first);
ForwardIterator itRight(first); std::advance(itRight, gap);
 
for ( ; itRight!=last; ++itLeft, ++itRight ){
if ( (*itRight) < (*itLeft) ){
std::iter_swap(itLeft, itRight);
swaps = true;
}
}
}
}

[edit] C#

using System;
 
namespace CombSort
{
class Program
{
static void Main(string[] args)
{
int[] unsorted = new int[] { 3, 5, 1, 9, 7, 6, 8, 2, 4 };
Console.WriteLine(string.Join(",", combSort(unsorted)));
}
public static int[] combSort(int[] input)
{
double gap = input.Length;
bool swaps = true;
while (gap > 1 || swaps)
{
gap /= 1.247330950103979;
if (gap < 1) { gap = 1; }
int i = 0;
swaps = false;
while (i + gap < input.Length)
{
int igap = i + (int)gap;
if (input[i] > input[igap])
{
int swap = input[i];
input[i] = input[igap];
input[igap] = swap;
swaps = true;
}
i++;
}
}
return input;
}
}
}

[edit] COBOL

This excerpt contains just enough of the procedure division to show the workings. See the example for the bubble sort for a more complete program.

       C-PROCESS SECTION.
C-000.
DISPLAY "SORT STARTING".
 
MOVE WC-SIZE TO WC-GAP.
 
PERFORM E-COMB UNTIL WC-GAP = 1 AND FINISHED.
 
DISPLAY "SORT FINISHED".
 
C-999.
EXIT.
 
E-COMB SECTION.
E-000.
IF WC-GAP > 1
DIVIDE WC-GAP BY 1.3 GIVING WC-GAP
IF WC-GAP = 9 OR 10
MOVE 11 TO WC-GAP.
 
MOVE 1 TO WC-SUB-1.
MOVE "Y" TO WF-FINISHED.
 
PERFORM F-SCAN UNTIL WC-SUB-1 + WC-GAP > WC-SIZE.
 
E-999.
EXIT.
 
F-SCAN SECTION.
F-000.
ADD WC-SUB-1 WC-GAP GIVING WC-SUB-2.
IF WB-ENTRY(WC-SUB-1) > WB-ENTRY(WC-SUB-2)
MOVE WB-ENTRY(WC-SUB-1) TO WC-TEMP
MOVE WB-ENTRY(WC-SUB-2) TO WB-ENTRY(WC-SUB-1)
MOVE WC-TEMP TO WB-ENTRY(WC-SUB-2)
MOVE "N" TO WF-FINISHED.
 
ADD 1 TO WC-SUB-1.
 
F-999.
EXIT.

[edit] D

Translation of: Python
import std.stdio, std.algorithm;
 
void combSort(T)(T[] input) pure nothrow @safe @nogc {
int gap = input.length;
bool swaps = true;
 
while (gap > 1 || swaps) {
gap = max(1, cast(int)(gap / 1.2473));
swaps = false;
foreach (immutable i; 0 .. input.length - gap)
if (input[i] > input[i + gap]) {
input[i].swap(input[i + gap]);
swaps = true;
}
}
}
 
void main() {
auto data = [28, 44, 46, 24, 19, 2, 17, 11, 25, 4];
data.combSort;
data.writeln;
}
Output:
[2, 4, 11, 17, 19, 24, 25, 28, 44, 46]

[edit] Eiffel

 
 
class
COMB_SORT [G -> COMPARABLE]
 
feature
 
combsort (ar: ARRAY [G]): ARRAY [G]
-- Sorted array in ascending order.
require
array_not_void: ar /= Void
local
gap, i: INTEGER
swap: G
swapped: BOOLEAN
shrink: REAL_64
do
create Result.make_empty
Result.deep_copy (ar)
gap := Result.count
from
until
gap = 1 and swapped = false
loop
from
i := Result.lower
swapped := false
until
i + gap > Result.count
loop
if Result [i] > Result [i + gap] then
swap := Result [i]
Result [i] := Result [i + gap]
Result [i + gap] := swap
swapped := TRUE
end
i := i + 1
end
shrink := gap / 1.3
gap := shrink.floor
if gap < 1 then
gap := 1
end
end
ensure
Result_is_set: Result /= VOID
Result_is_sorted: is_sorted (Result)
end
 
feature {NONE}
 
is_sorted (ar: ARRAY [G]): BOOLEAN
--- Is 'ar' sorted in ascending order?
require
ar_not_empty: ar.is_empty = FALSE
local
i: INTEGER
do
Result := TRUE
from
i := ar.lower
until
i = ar.upper
loop
if ar [i] > ar [i + 1] then
RESULT := FALSE
end
i := i + 1
end
end
 
end
 
 

Test:

 
class
APPLICATION
 
create
make
 
feature
 
make
do
test := <<1, 5, 99, 2, 95, 7, -7>>
io.put_string ("unsorted" + "%N")
across
test as ar
loop
io.put_string (ar.item.out + "%T")
end
io.put_string ("%N" + "sorted:" + "%N")
create combsort
test := combsort.combsort (test)
across
test as ar
loop
io.put_string (ar.item.out + "%T")
end
end
 
combsort: COMB_SORT [INTEGER]
 
test: ARRAY [INTEGER]
 
end
 
Output:
unsorted:
1 5 99 2 95 7 -7
sorted:
-7 1 2 5 7 95 99

[edit] Forth

This is an implementation of Comb sort with a different ending. Here Gnome sort is used, since it is rather small. The dataset is rather large, because otherwise the Comb sort routine would never kick in, passing control to Gnome sort almost right away. Note Comb sort can be kept much simpler this way, because Combsort11 optimizations and swapped flags can be discarded.

defer precedes
defer exchange
 
: gnomesort ( a n)
swap >r 1 ( n c)
begin ( n c)
over over > ( n c f)
while ( n c)
dup if ( n c)
dup dup 1- over over r@ precedes
if r@ exchange 1- else drop drop 1+ then
else 1+ then ( n c)
repeat drop drop r> drop ( --)
;
 
: combsort ( a n --)
dup begin ( a n g)
10 13 */ tuck >r >r 0 ( a g 0)
begin ( a g 0)
over r@ < ( a g 0 f)
while ( a g 0)
rot >r over over r@ precedes ( g 0 f)
if over over r@ exchange then ( g 0)
r> rot 1+ rot 1+ ( a g 0)
repeat drop drop r> r> ( a n g)
dup 9 < ( a n g f)
until drop gnomesort ( --)
;
 
create example
8 93 69 52 50 79 33 52 19 77 , , , , , , , , , ,
72 85 11 61 64 80 64 76 47 65 , , , , , , , , , ,
13 47 23 40 87 45 2 48 22 69 , , , , , , , , , ,
1 53 33 60 57 14 76 32 59 12 , , , , , , , , , ,
74 38 39 22 87 28 37 93 71 88 , , , , , , , , , ,
56 35 48 99 21 35 26 28 58 85 , , , , , , , , , ,
27 16 54 88 82 18 45 64 45 87 , , , , , , , , , ,
98 97 60 77 43 1 64 0 32 89 , , , , , , , , , ,
77 90 68 83 9 76 10 10 95 12 , , , , , , , , , ,
99 23 74 58 54 25 50 9 94 1 , , , , , , , , , ,
 
:noname >r cells r@ + @ swap cells r> + @ swap < ; is precedes
:noname >r cells r@ + swap cells r> + over @ over @ swap rot ! swap ! ; is exchange
 
: .array 100 0 do example i cells + ? loop cr ;
 
.array example 100 combsort .array

[edit] Fortran

Works with: Fortran version 90 and later
program Combsort_Demo
implicit none
 
integer, parameter :: num = 20
real :: array(num)
 
call random_seed
call random_number(array)
write(*,*) "Unsorted array:-"
write(*,*) array
write(*,*)
call combsort(array)
write(*,*) "Sorted array:-"
write(*,*) array
 
contains
 
subroutine combsort(a)
 
real, intent(in out) :: a(:)
real :: temp
integer :: i, gap
logical :: swapped = .true.
 
gap = size(a)
do while (gap > 1 .or. swapped)
gap = gap / 1.3
if (gap < 1) gap = 1
swapped = .false.
do i = 1, size(a)-gap
if (a(i) > a(i+gap)) then
temp = a(i)
a(i) = a(i+gap)
a(i+gap) = temp;
swapped = .true.
end if
end do
end do
 
end subroutine combsort
 
end program Combsort_Demo

[edit] Go

package main
 
import "fmt"
 
func main() {
a := []int{170, 45, 75, -90, -802, 24, 2, 66}
fmt.Println("before:", a)
combSort(a)
fmt.Println("after: ", a)
}
 
func combSort(a []int) {
if len(a) < 2 {
return
}
for gap := len(a); ; {
if gap > 1 {
gap = gap * 4 / 5
}
swapped := false
for i := 0; ; {
if a[i] > a[i+gap] {
a[i], a[i+gap] = a[i+gap], a[i]
swapped = true
}
i++
if i+gap >= len(a) {
break
}
}
if gap == 1 && !swapped {
break
}
}
}

More generic version that sorts anything that implements sort.Interface:

package main
 
import (
"sort"
"fmt"
)
 
func main() {
a := []int{170, 45, 75, -90, -802, 24, 2, 66}
fmt.Println("before:", a)
combSort(sort.IntSlice(a))
fmt.Println("after: ", a)
}
 
func combSort(a sort.Interface) {
if a.Len() < 2 {
return
}
for gap := a.Len(); ; {
if gap > 1 {
gap = gap * 4 / 5
}
swapped := false
for i := 0; ; {
if a.Less(i+gap, i) {
a.Swap(i, i+gap)
swapped = true
}
i++
if i+gap >= a.Len() {
break
}
}
if gap == 1 && !swapped {
break
}
}
}

[edit] Groovy

Combsort solution:

def makeSwap = { a, i, j -> print "."; a[i] ^= a[j]; a[j] ^= a[i]; a[i] ^= a[j] }
 
def checkSwap = { a, i, j -> [(a[i] > a[j])].find { it }.each { makeSwap(a, i, j) } }
 
def combSort = { input ->
def swap = checkSwap.curry(input)
def size = input.size()
def gap = size
def swapped = true
while (gap != 1 || swapped) {
gap = (gap / 1.247330950103979) as int
gap = (gap < 1) ? 1 : gap
swapped = (0..<(size-gap)).any { swap(it, it + gap) }
}
input
}

Combsort11 solution:

def combSort11 = { input ->
def swap = checkSwap.curry(input)
def size = input.size()
def gap = size
def swapped = true
while (gap != 1 || swapped) {
gap = (gap / 1.247330950103979) as int
gap = ((gap < 1) ? 1 : ([10,9].contains(gap) ? 11 : gap))
swapped = (0..<(size-gap)).any { swap(it, it + gap) }
}
input
}

Test:

println   (combSort([23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4]))
println (combSort11([23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4]))
println ()
println (combSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1]))
println (combSort11([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1]))

Output:

..................................................................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]
..........................................................................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]

...............................................................................................[0, 1, 4, 5, 7, 8, 12, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]
...............................................................................................[0, 1, 4, 5, 7, 8, 12, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]

[edit] Haskell

import Data.List
import Control.Arrow
import Control.Monad
 
flgInsert x xs = ((x:xs==) &&& id)$ insert x xs
 
gapSwapping k = (and *** concat. transpose). unzip
. map (foldr (\x (b,xs) -> first (b &&)$ flgInsert x xs) (True,[]))
. transpose. takeWhile (not.null). unfoldr (Just. splitAt k)
 
combSort xs = (snd. fst) $ until (\((b,_),g)-> b && g==1)
(\((_,xs),g) ->(gapSwapping g xs, fg g)) ((False,xs), fg $ length xs)
where fg = max 1. truncate. (/1.25). fromIntegral

Example:

*Main> combSort [23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78]
[12,14,23,24,24,31,35,38,46,51,57,57,58,76,78,89,92,95,97,99]

[edit] Io

List do(
combSortInPlace := method(
gap := size
swap := true
 
while(gap > 1 or swap,
swap = false
gap = (gap / 1.25) floor
 
for(i, 0, size - gap,
if(at(i) > at(i + gap),
swap = true
swapIndices(i, i + gap)
)
)
)
self)
)
 
lst := list(23, 76, 99, 58, 97, 57, 35, 89, 51, 38, 95, 92, 24, 46, 31, 24, 14, 12, 57, 78)
lst combSortInPlace println # ==> list(12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99)

[edit] Icon and Unicon

procedure main()                     #: demonstrate various ways to sort a list and string 
demosort(combsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end
 
procedure combsort(X,op) #: return sorted X
local gap,swapped,i
 
op := sortop(op,X) # select how and what we sort
 
swappped := gap := *X # initialize gap size and say swapped
until /swapped & gap = 1 do {
gap := integer(gap / 1.25) # update the gap value for a next comb
gap <:= 1 # minimum gap of 1
swapped := &null
 
i := 0
until (i +:= 1) + gap > *X do # a single "comb" over the input list
if op(X[i+gap],X[i]) then
X[i+1] :=: X[swapped := i] # swap and flag as unsorted
}
return X
end

Note: This example relies on the supporting procedures 'sortop', and 'demosort' in Bubble Sort. The full demosort exercises the named sort of a list with op = "numeric", "string", ">>" (lexically gt, descending),">" (numerically gt, descending), a custom comparator, and also a string.

Abbreviated sample output:
Sorting Demo using procedure combsort
  on list : [ 3 14 1 5 9 2 6 3 ]
    with op = &null:         [ 1 2 3 3 5 6 9 14 ]   (0 ms)
  ...
  on string : "qwerty"
    with op = &null:         "eqrtwy"   (0 ms)

[edit] J

Generally, this task should be accomplished in J using /:~. Here we take an approach that's more comparable with the other examples on this page.

Large gap sizes allow some parallelism in comparisons and swaps. (If the gap size is G, then G pairs can be compared and swapped in parallel.) Beyond that, however, the data flow complexity of this algorithm requires a fair bit of micro-management.

combSort=:3 :0
gap=. #y
whilst.1 < gap+swaps do.
swaps=. 0
i=. i.2,gap=. 1 >. <.gap%1.25
while.{:$i=.i #"1~ ({: i) < #y do.
swaps=.swaps+#{:k=.i #"1~b=. >/ i{y
i=. i+gap
y=.((|.k){y) k} y
end.
end.
y
)

Example use:

   combSort 23 76 99 58 97 57 35 89 51 38 95 92 24 46 31 24 14 12 57 78
12 14 23 24 24 31 35 38 46 51 57 57 58 76 78 89 92 95 97 99
   combSort 88 18 31 44 4 0 8 81 14 78 20 76 84 33 73 75 82 5 62 70
0 4 5 8 14 18 20 31 33 44 62 70 73 75 76 78 81 82 84 88

[edit] Java

This is copied from the Wikipedia article.

public static <E extends Comparable<? super E>> void sort(E[] input) {
int gap = input.length;
boolean swapped = true;
while (gap > 1 || swapped) {
if (gap > 1) {
gap = (int) (gap / 1.3);
}
swapped = false;
for (int i = 0; i + gap < input.length; i++) {
if (input[i].compareTo(input[i + gap]) > 0) {
E t = input[i];
input[i] = input[i + gap];
input[i + gap] = t;
swapped = true;
}
}
}
}

[edit] jq

Works with: jq version 1.4

An implementation of the pseudo-code in the task description:

# Input should be the array to be sorted.
def combsort:
 
# As soon as "condition" is true, emit . and stop:
def do_until(condition; next):
def u: if condition then . else (next|u) end;
u;
 
def swap(i;j):
if i==j then . else .[i] as $tmp | .[i] = .[j] | .[j] = $tmp end;
 
. as $in
| length as $length
# state: [gap, swaps, array] where:
# gap is the gap size;
# swaps is a boolean flag indicating a swap has occurred,
# implying that the array might not be sorted;
# array is the current state of the array being sorted
| [ $length, false, $in ]
| do_until( .[0] == 1 and .[1] == false;
# update the gap value for the next "comb":
([1, ((.[0] / 1.25) | floor)] | max) as $gap # minimum gap is 1
 
# state: [i, swaps, array]
| [0, false, .[2]]
# a single "comb" over the input list:
| do_until( (.[0] + $gap) >= $length;
.[0] as $i
| if .[2][$i] > .[2][$i+$gap] then
[$i+1, true, (.[2]|swap($i; $i+$gap))]
else .[0] += 1
end)
| .[0] = $gap )
| .[2] ;

[edit] Lua

function combsort(t)
local gapd, gap, swaps = 1.2473, #t, 0
while gap + swaps > 1 do
local k = 0
swaps = 0
if gap > 1 then gap = math.floor(gap / gapd) end
for k = 1, #t - gap do
if t[k] > t[k + gap] then
t[k], t[k + gap], swaps = t[k + gap], t[k], swaps + 1
end
end
end
return t
end
 
print(unpack(combsort{3,5,1,2,7,4,8,3,6,4,1}))

[edit] Mathematica

combSort[list_] := Module[{ gap = 0, listSize = 0, swaps = True},  
gap = listSize = Length[list];
While[ !((gap <= 1) && (swaps == False)),
 
gap = Floor@Divide[gap, 1.25];
If[ gap < 1, gap = 1]; i = 1; swaps = False;
 
While[ ! ((i + gap - 1) >= listSize),
If[ list[[i]] > list[[i + gap]], swaps = True;
list[[i ;; i + gap]] = list[[i + gap ;; i ;; -1]];
];
i++;
]
]
]
combSort@{2, 1, 3, 7, 6}
->{1, 2, 3, 6, 7}

[edit] MATLAB / Octave

function list = combSort(list)
 
listSize = numel(list);
gap = int32(listSize); %Coerce gap to an int so we can use the idivide function
swaps = true; %Swap flag
 
while not((gap <= 1) && (swaps == false))
 
gap = idivide(gap,1.25,'floor'); %Int divide, floor the resulting operation
 
if gap < 1
gap = 1;
end
 
i = 1; %i equals 1 because all arrays are 1 based in MATLAB
swaps = false;
 
%i + gap must be subtracted by 1 because the pseudo-code was writen
%for 0 based arrays
while not((i + gap - 1) >= listSize)
 
if (list(i) > list(i+gap))
list([i i+gap]) = list([i+gap i]); %swap
swaps = true;
end
i = i + 1;
 
end %while
end %while
end %combSort

Sample Output:

>> combSort([4 3 1 5 6 2])
 
ans =
 
1 2 3 4 5 6

[edit] MAXScript

fn combSort arr =
(
local gap = arr.count
local swaps = 1
while not (gap == 1 and swaps == 0) do
(
gap = (gap / 1.25) as integer
if gap < 1 do
(
gap = 1
)
local i = 1
swaps = 0
while not (i + gap > arr.count) do
(
if arr[i] > arr[i+gap] do
(
swap arr[i] arr[i+gap]
swaps = 1
)
i += 1
 
)
 
 
)
return arr
)

Output:

 
a = for i in 1 to 10 collect random 1 10
#(2, 6, 5, 9, 10, 7, 2, 6, 1, 4)
combsort a
#(1, 2, 2, 4, 5, 6, 6, 7, 9, 10)
 

[edit] NetRexx

/* NetRexx */
 
options replace format comments java crossref savelog symbols binary
 
placesList = [String -
"UK London", "US New York" -
, "US Boston", "US Washington" -
, "UK Washington", "US Birmingham" -
, "UK Birmingham", "UK Boston" -
]
sortedList = combSort(String[] Arrays.copyOf(placesList, placesList.length))
 
lists = [placesList, sortedList]
loop ln = 0 to lists.length - 1
cl = lists[ln]
loop ct = 0 to cl.length - 1
say cl[ct]
end ct
say
end ln
 
return
 
method combSort(input = String[]) public constant binary returns String[]
 
swaps = isTrue
gap = input.length
loop label comb until gap = 1 & \swaps
gap = int gap / 1.25
if gap < 1 then
gap = 1
i_ = 0
swaps = isFalse
loop label swaps until i_ + gap >= input.length
if input[i_].compareTo(input[i_ + gap]) > 0 then do
swap = input[i_]
input[i_] = input[i_ + gap]
input[i_ + gap] = swap
swaps = isTrue
end
i_ = i_ + 1
end swaps
end comb
 
return input
 
method isTrue public constant binary returns boolean
return 1 == 1
 
method isFalse public constant binary returns boolean
return \isTrue
 
Output
UK  London
US  New York
US  Boston
US  Washington
UK  Washington
US  Birmingham
UK  Birmingham
UK  Boston

UK  Birmingham
UK  Boston
UK  London
UK  Washington
US  Birmingham
US  Boston
US  New York
US  Washington

[edit] Nim

proc combSort[T](a: var openarray[T]) =
var gap = a.len
var swapped = true
while gap > 1 or swapped:
gap = gap * 10 div 13
if gap == 9 or gap == 10: gap = 11
if gap < 1: gap = 1
swapped = false
var i = 0
for j in gap .. <a.len:
if a[i] > a[j]:
swap a[i], a[j]
swapped = true
inc i
 
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
combSort a
echo a

Output:

@[-31, 0, 2, 2, 4, 65, 83, 99, 782]

[edit] Objeck

 
bundle Default {
class Stooge {
function : Main(args : String[]) ~ Nil {
nums := [3, 5, 1, 9, 7, 6, 8, 2, 4];
CombSort(nums);
each(i : nums) {
IO.Console->Print(nums[i])->Print(",");
};
IO.Console->PrintLine();
}
 
function : CombSort(input : Int[]) ~ Nil {
gap : Float := input->Size();
swaps := true;
while(gap > 1 | swaps) {
gap /= 1.247330950103979;
if(gap < 1) { gap := 1; };
i : Int := 0;
swaps := false;
while(i + gap < input->Size()) {
igap : Int := i + gap->As(Int);
if (input[i] > input[igap]) {
swap : Int := input[i];
input[i] := input[igap];
input[igap] := swap;
swaps := true;
};
i += 1;
};
};
}
}
}
 

[edit] OCaml

let comb_sort ~input =
let input_length = Array.length input in
let gap = ref(input_length) in
let swapped = ref true in
while (!gap > 1 || !swapped) do
if (!gap > 1) then
gap := int_of_float (float !gap /. 1.3);
 
swapped := false;
for i = 0 to input_length - !gap do
if input.(i) > input.(i + !gap) then begin
let tmp = input.(i) in
input.(i) <- input.(i + !gap);
input.(i + !gap) <- tmp;
swapped := true;
end
done
done
;;

[edit] Oz

declare
proc {CombSort Arr}
Low = {Array.low Arr}
High = {Array.high Arr}
Size = High - Low + 1
Gap = {NewCell Size}
Swapped = {NewCell true}
proc {Swap I J}
Arr.J := (Arr.I := Arr.J)
end
in
for while:@Gap>1 orelse @Swapped do
if @Gap > 1 then
Gap := {Float.toInt {Floor {Int.toFloat @Gap} / 1.3}}
end
Swapped := false
for I in Low..High-@Gap do
if Arr.I > Arr.(I+@Gap) then
{Swap I I+@Gap}
Swapped := true
end
end
end
end
Arr = {Tuple.toArray unit(3 1 4 1 5 9 2 6 5)}
in
{CombSort Arr}
{Show {Array.toRecord unit Arr}}

[edit] PARI/GP

combSort(v)={
my(phi=(1+sqrt(5))/2,magic=1/(1-exp(-phi)),g=#v,swaps);
while(g>1 | swaps,
if(g>1, g\=magic);
swaps=0;
for(i=1,#v-g,
if(v[i]>v[i+g],
my(t=v[i]);
v[i]=v[i+g];
v[i+g]=t;
swaps++
)
)
);
v
};

[edit] Pascal

program CombSortDemo;
 
type
TIntArray = array[1..40] of integer;
 
var
data: TIntArray;
i: integer;
 
procedure combSort(var a: TIntArray);
var
i, gap, temp: integer;
swapped: boolean;
begin
gap := length(a);
swapped := true;
while (gap > 1) or swapped do
begin
gap := trunc(gap / 1.3);
if (gap < 1) then
gap := 1;
swapped := false;
for i := 1 to length(a) - gap do
if a[i] > a[i+gap] then
begin
temp := a[i];
a[i] := a[i+gap];
a[i+gap] := temp;
swapped := true;
end;
end;
end;
 
begin
Randomize;
writeln('The data before sorting:');
for i := low(data) to high(data) do
begin
data[i] := Random(high(data));
write(data[i]:4);
end;
writeln;
combSort(data);
writeln('The data after sorting:');
for i := low(data) to high(data) do
begin
write(data[i]:4);
end;
writeln;
end.

Output:

The data before sorting:
  10  26  32  10   9  32  38  37  12   9  16   7  25   1  37   7  24  22   7  36   2   5  10   5  33  35  32  18   5  28   7   5  36  12  16  36  24   3  29  15
The data after sorting:
   1   2   3   5   5   5   5   7   7   7   7   9   9  10  10  10  12  12  15  16  16  18  22  24  24  25  26  28  29  32  32  32  33  35  36  36  36  37  37  38

[edit] Perl

sub combSort {
my @arr = @_;
my $gap = @arr;
my $swaps = 1;
while ($gap > 1 || $swaps) {
$gap /= 1.25 if $gap > 1;
$swaps = 0;
foreach my $i (0 .. $#arr - $gap) {
if ($arr[$i] > $arr[$i+$gap]) {
@arr[$i, $i+$gap] = @arr[$i+$gap, $i];
$swaps = 1;
}
}
}
return @arr;
}

[edit] Perl 6

Translation of: Perl
sub comb_sort ( @a is copy ) {
my $gap = +@a;
my $swaps = 1;
while $gap > 1 or $swaps {
$gap = ( ($gap * 4) div 5 ) || 1 if $gap > 1;
 
$swaps = 0;
for ^(+@a - $gap) -> $i {
my $j = $i + $gap;
if @a[$i] > @a[$j] {
@a[$i, $j] .= reverse;
$swaps = 1;
}
}
}
return @a;
}
 
my @weights = (^50).map: { 100 + ( 1000.rand.Int / 10 ) };
say @weights.sort.Str eq @weights.&comb_sort.Str ?? 'ok' !! 'not ok';
 

[edit] PHP

function combSort($arr){
$gap = count($arr);
$swap = true;
while ($gap > 1 || $swap){
if($gap > 1) $gap /= 1.25;
 
$swap = false;
$i = 0;
while($i+$gap < count($arr)){
if($arr[$i] > $arr[$i+$gap]){
list($arr[$i], $arr[$i+$gap]) = array($arr[$i+$gap],$arr[$i]);
$swap = true;
}
$i++;
}
}
return $arr;
}

[edit] PicoLisp

(de combSort (Lst)
(let (Gap (length Lst) Swaps NIL)
(while (or (> Gap 1) Swaps)
(setq Gap (max 1 (/ (* Gap 4) 5)))
(off Swaps)
(use Lst
(for (G (cdr (nth Lst Gap)) G (cdr G))
(when (> (car Lst) (car G))
(xchg Lst G)
(on Swaps) )
(pop 'Lst) ) ) ) )
Lst )

Output:

: (combSort (88 18 31 44 4 0 8 81 14 78 20 76 84 33 73 75 82 5 62 70))
-> (0 4 5 8 14 18 20 31 33 44 62 70 73 75 76 78 81 82 84 88)

[edit] PL/I

 
/* From the pseudocode. */
comb_sort: procedure (A);
declare A(*) fixed;
declare t fixed;
declare (i, gap) fixed binary (31);
declare swaps bit (1) aligned;
 
gap = hbound(A,1) - lbound(A,1); /* initialize the gap size. */
do until (gap <= 1 & swaps);
/* update the gap value for a next comb. */
put skip data (gap);
gap = gap / 1.25e0;
put skip data (gap);
swaps = '1'b;
/* a single "comb" over the array. */
do i = lbound(A,1) by 1 until (i + gap >= hbound(A,1));
if A(i) > A(i+gap) then
do;
t = A(i); A(i) = A(i+gap); A(i+gap) = t;
swaps = '0'b; /* Flag a swap has occurred, so */
/* the list is not guaranteed sorted. */
end;
end;
end;
end comb_sort;
 

[edit] PowerShell

Massaging gap to always hit 11. Based on PowerShell from Cocktail Sort

function CombSort ($a) {
$l = $a.Length
$gap = 11
while( $gap -lt $l )
{
$gap = [Math]::Floor( $gap*1.3 )
}
if( $l -gt 1 )
{
$hasChanged = $true
:outer while ($hasChanged -or ( $gap -gt 1 ) ) {
$count = 0
$hasChanged = $false
if( $gap -gt 1 ) {
$gap = [Math]::Floor( $gap/1.3 )
} else {
$l--
}
for ($i = 0; $i -lt ( $l - $gap ); $i++) {
if ($a[$i] -gt $a[$i+$gap]) {
$a[$i], $a[$i+$gap] = $a[$i+$gap], $a[$i]
$hasChanged = $true
$count++
}
}
}
}
$a
}
 
$l = 100; CombSort ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( -( $l - 1 ), $l - 1 ) } )

[edit] PureBasic

Implementation of CombSort11.

;sorts an array of integers
Procedure combSort11(Array a(1))
Protected i, gap, swaps = 1
Protected nElements = ArraySize(a())
 
gap = nElements
While (gap > 1) Or (swapped = 1)
gap * 10 / 13
If gap = 9 Or gap = 10: gap = 11: EndIf
If gap < 1: gap = 1: EndIf
 
i = 0
swaps = 0
While (i + gap) <= nElements
If a(i) > a(i + gap)
Swap a(i), a(i + gap)
swaps = 1
EndIf
i + 1
Wend
Wend
EndProcedure

Implementation of CombSort.

;sorts an array of integers
Procedure combSort(Array a(1))
Protected i, gap, swaps = 1
Protected nElements = ArraySize(a())
 
gap = nElements
While (gap > 1) Or (swaps = 1)
gap = Int(gap / 1.25)
 
i = 0
swaps = 0
While (i + gap) <= nElements
If a(i) > a(i + gap)
Swap a(i), a(i + gap)
swaps = 1
EndIf
i + 1
Wend
Wend
EndProcedure

[edit] Python

>>> def combsort(input):
gap = len(input)
swaps = True
while gap > 1 or swaps:
gap = max(1, int(gap / 1.25)) # minimum gap is 1
swaps = False
for i in range(len(input) - gap):
j = i+gap
if input[i] > input[j]:
input[i], input[j] = input[j], input[i]
swaps = True
 
 
>>> y = [88, 18, 31, 44, 4, 0, 8, 81, 14, 78, 20, 76, 84, 33, 73, 75, 82, 5, 62, 70]
>>> combsort(y)
>>> assert y == sorted(y)
>>> y
[0, 4, 5, 8, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]
>>>

[edit] Racket

 
#lang racket
(require (only-in srfi/43 vector-swap!))
 
(define (comb-sort xs)
(define (ref i) (vector-ref xs i))
(define (swap i j) (vector-swap! xs i j))
(define (new gap) (max 1 (exact-floor (/ gap 1.25))))
(define size (vector-length xs))
(let loop ([gap size] [swaps 0])
(unless (and (= gap 1) (= swaps 0))
(loop (new gap)
(for/fold ([swaps 0]) ([i (in-range 0 (- size gap))])
(cond
[(> (ref i) (ref (+ i gap)))
(swap i (+ i gap))
(+ swaps 1)]
[swaps])))))
xs)
 

[edit] REXX

Programming note:   the REXX statement (line 11)     s=trunc(s*.8)     could've been expressed as:     s=s*.8%1     (which is slower), but is more cryptic.

/*REXX program sorts a  stemmed array  using the  comb-sort  algorithm. */
call gen@; w=length(#) /*generate the array elements. */
call show@ 'before sort' /*show the before array elements.*/
call combSort # /*invoke the comb sort. */
call show@ ' after sort' /*show the after array elements.*/
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────COMBSORT subroutine─────────────────*/
combSort: procedure expose @.; parse arg N /*N: is number of elements.*/
s=N-1 /*S: is the spread between COMBs.*/
do until s<=1 & done; done=1 /*assume sort is done (so far). */
s=trunc(s*.8) /* ÷ is slow, * is better.*/
do j=1 until js>=N; js=j+s
if @.j>@.js then do; _=@.j; @.j=@.js; @.js=_; done=0; end
end /*j*/
end /*until*/
return
/*──────────────────────────────────GEN@ subroutine─────────────────────*/
gen@: @. =  ; @.12 = 'dodecagon 12'
@.1 = '----polygon--- sides'  ; @.13 = 'tridecagon 13'
@.2 = '============== ======='  ; @.14 = 'tetradecagon 14'
@.3 = 'triangle 3'  ; @.15 = 'pentadecagon 15'
@.4 = 'quadrilateral 4'  ; @.16 = 'hexadecagon 16'
@.5 = 'pentagon 5'  ; @.17 = 'heptadecagon 17'
@.6 = 'hexagon 6'  ; @.18 = 'octadecagon 18'
@.7 = 'heptagon 7'  ; @.19 = 'enneadecagon 19'
@.8 = 'octagon 8'  ; @.20 = 'icosagon 20'
@.9 = 'nonagon 9'  ; @.21 = 'hectogon 100'
@.10 = 'decagon 10'  ; @.22 = 'chiliagon 1000'
@.11 = 'hendecagon 11'  ; @.23 = 'myriagon 10000'
do #=1 while @.#\==''; end; #=#-1 /*find how many entries in array.*/
return
/*──────────────────────────────────SHOW@ subroutine────────────────────*/
show@: say copies('▒',60); do j=1 for # /*display array elements.*/
say ' element' right(j,w) arg(1)":" @.j
end /*j*/
return

Data note:   A   hendecagon   (also known as an   undecagon   or   unidecagon)   is from the Greek word   hendeka   [eleven]   and   gon─   [corner].

output

▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
        element  1 before sort: ----polygon---  sides
        element  2 before sort: ============== =======
        element  3 before sort: triangle           3
        element  4 before sort: quadrilateral      4
        element  5 before sort: pentagon           5
        element  6 before sort: hexagon            6
        element  7 before sort: heptagon           7
        element  8 before sort: octagon            8
        element  9 before sort: nonagon            9
        element 10 before sort: decagon           10
        element 11 before sort: hendecagon        11
        element 12 before sort: dodecagon         12
        element 13 before sort: tridecagon        13
        element 14 before sort: tetradecagon      14
        element 15 before sort: pentadecagon      15
        element 16 before sort: hexadecagon       16
        element 17 before sort: heptadecagon      17
        element 18 before sort: octadecagon       18
        element 19 before sort: enneadecagon      19
        element 20 before sort: icosagon          20
        element 21 before sort: hectogon         100
        element 22 before sort: chiliagon       1000
        element 23 before sort: myriagon       10000
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
        element  1  after sort: ----polygon---  sides
        element  2  after sort: ============== =======
        element  3  after sort: chiliagon       1000
        element  4  after sort: decagon           10
        element  5  after sort: dodecagon         12
        element  6  after sort: enneadecagon      19
        element  7  after sort: hectogon         100
        element  8  after sort: hendecagon        11
        element  9  after sort: heptadecagon      17
        element 10  after sort: heptagon           7
        element 11  after sort: hexadecagon       16
        element 12  after sort: hexagon            6
        element 13  after sort: icosagon          20
        element 14  after sort: myriagon       10000
        element 15  after sort: nonagon            9
        element 16  after sort: octadecagon       18
        element 17  after sort: octagon            8
        element 18  after sort: pentadecagon      15
        element 19  after sort: pentagon           5
        element 20  after sort: quadrilateral      4
        element 21  after sort: tetradecagon      14
        element 22  after sort: triangle           3
        element 23  after sort: tridecagon        13

[edit] Ruby

class Array
def combsort!
gap = size
swaps = true
while gap > 1 or swaps
gap = [1, (gap / 1.25).to_i].max
swaps = false
0.upto(size - gap - 1) do |i|
if self[i] > self[i+gap]
self[i], self[i+gap] = self[i+gap], self[i]
swaps = true
end
end
end
self
end
end
 
p [23, 76, 99, 58, 97, 57, 35, 89, 51, 38, 95, 92, 24, 46, 31, 24, 14, 12, 57, 78].combsort!

results in

[12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]

[edit] Sather

class SORT{T < $IS_LT{T}} is
 
private swap(inout a, inout b:T) is
temp ::= a;
a := b;
b := temp;
end;
 
-- ---------------------------------------------------------------------------------
comb_sort(inout a:ARRAY{T}) is
gap ::= a.size;
swapped ::= true;
loop until!(gap <= 1 and ~swapped);
if gap > 1 then
gap := (gap.flt / 1.25).int;
end;
i ::= 0;
swapped := false;
loop until! ( (i + gap) >= a.size );
if (a[i] > a[i+gap]) then
swap(inout a[i], inout a[i+gap]);
swapped := true;
end;
i := i + 1;
end;
end;
end;
end;
 
class MAIN is
main is
a:ARRAY{INT} := |88, 18, 31, 44, 4, 0, 8, 81, 14, 78, 20, 76, 84, 33, 73, 75, 82, 5, 62, 70|;
b ::= a.copy;
SORT{INT}::comb_sort(inout b);
#OUT + b + "\n";
end;
end;

[edit] Tcl

proc combsort {input} {
set gap [llength $input]
while 1 {
set gap [expr {int(floor($gap / 1.3))}]
set swaps 0
for {set i 0} {$i+$gap < [llength $input]} {incr i} {
set j [expr {$i+$gap}]
if {[lindex $input $i] > [lindex $input $j]} {
set tmp [lindex $input $i]
lset input $i [lindex $input $j]
lset input $j $tmp
incr swaps
}
}
if {$gap <= 1 && !$swaps} break
}
return $input
}
 
set data {23 76 99 58 97 57 35 89 51 38 95 92 24 46 31 24 14 12 57 78}
puts [combsort $data]

Produces this output:

12 14 23 24 24 31 35 38 46 51 57 57 58 76 78 89 92 95 97 99

[edit] TI-83 BASIC

Requires prgmSORTINS. Gap division of 1.3. Switches to Insertion sort when gap is less than 5.

:L1→L2
:dim(L2)→A
:While A>5 and B=0
:int(A/1.3)→A
:1→C
:0→B
:While (C+A)≥dim(L2)
:If L2(C)>L2(C+A)
:Then
:L2(C)→D
:L2(C+A)→L2(C)
:D→L2(C+A)
:1→B
:End
:C+1→C
:End
:DelVar A
:DelVar B
:DelVar C
:DelVar D
:L1→L3
:L2→L1
:prgmSORTINS
:L3→L1
:DelVar L3
:Return
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox