Sorting algorithms/Comb sort: Difference between revisions

Content added Content deleted

Inline

Revision as of 15:46, 27 May 2010

This task has been clarified. Its programming examples are in need of review to ensure that they still fit the requirements of the task.

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

ActionScript

<lang 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; }</lang>

AutoHotkey

<lang 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

}</lang> 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

C

Implementation of Combsort11. Its efficiency can be improved by just switching to Insertion sort when the gap size becomes less than 10. <lang c>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;
     }
   }
 }

}</lang>

C++

This is copied from the Wikipedia article. <lang cpp>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;
           }
       }
   }

}</lang>

C#

<lang csharp>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;
       }
   }

} </lang>

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. <lang forth>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</lang>

Io

<lang 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)</lang>

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.

<lang J>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

)</lang>

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

Java

This is copied from the Wikipedia article. <lang java>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;
           }
       }
   }

}</lang>

Lua

<lang 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}))</lang>

OCaml

<lang 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

</lang>

Oz

<lang 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}}</lang>

PHP

<lang php>function combSort($arr){ $gap = count($arr); 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; }</lang>

PL/I

<lang 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; </lang>

PureBasic

Implementation of CombSort11. <lang PureBasic>;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</lang> Implementation of CombSort. <lang PureBasic>;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</lang>

Python

<lang 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</lang> results in

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

Ruby

<lang 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!</lang> results in

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

Sather

<lang 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;</lang>

Tcl

<lang 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]</lang> Produces this output:

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

TI-83 BASIC

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

:L₁→L₂
:dim(L₂)→A
:While A>5 and B=0
:int(A/1.3)→A
:1→C
:0→B
:While (C+A)≥dim(L₂)
:If L₂(C)>L₂(C+A)
:Then
:L₂(C)→D
:L₂(C+A)→L₂(C)
:D→L₂(C+A)
:1→B
:End
:C+1→C
:End
:DelVar A
:DelVar B
:DelVar C
:DelVar D
:L₁→L₃
:L₂→L₁
:prgmSORTINS
:L₃→L₁
:DelVar L₃
:Return