Sorting algorithms/Comb sort

From Rosetta Code

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 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)
        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 1 ActionScript 2 C 3 C++ 4 J 5 Java 6 Lua 7 OCaml 8 Oz 9 PL/I 10 PureBasic 11 Python 12 Ruby 13 Tcl 14 TI-83 BASIC

[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] 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] J

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

[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] 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] 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);
 
    let i = ref 0 in
    swapped := false;
    while (!i + !gap < input_length) 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;
      incr i;
    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] 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] 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 = int(gap / 1.25)
        swaps = False
        for i in range(len(input) - gap):
            if input[i] > input[i+gap]:
                input[i], input[i+gap] = input[i+gap], input[i]
                swaps = True
 
x = [23, 76, 99, 58, 97, 57, 35, 89, 51, 38, 95, 92, 24, 46, 31, 24, 14, 12, 57, 78]
combsort(x)
print x

results in

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

[edit] Ruby

class Array
  def combsort!
    gap = size
    swaps = true
    until gap <= 1 and swaps
      gap = (gap / 1.25).to_int
      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] 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