# Sorting algorithms/Comb sort

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 comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts

O(n log2n) sorts
Shell 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 ${\displaystyle 1/\left(1-{\frac {1}{e^{\varphi }}}\right)\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)
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);

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]

## 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.

: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