Sorting algorithms/Comb sort

From Rosetta Code
Revision as of 12:31, 26 January 2010 by rosettacode>Wmeyer (Added Oz.)
Task
Sorting algorithms/Comb sort
You are encouraged to solve this task according to the task description, using any language you may know.
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

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>

Java

This is copied from the Wikipedia article. <lang java>public static void sort(Comparable[] input) {

   int gap = input.length;
   boolean swapped = true;
   while (gap > 1 || swapped) {
       if (gap > 1) {
           gap = (int) (gap / 1.3);
       }
       int i = 0;
       swapped = false;
       while (i + gap < input.length) {
           if (input[i].compareTo(input[i + gap]) > 0) {
               Comparable t = input[i];
               input[i] = input[i + gap];
               input[i + gap] = t;
               swapped = true;
           }
           i++;
       }
   }

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

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]


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
:Stop