Comb Sort

Comb sort is a comparison sorting algorithm improves on Bubble sort. The basic idea is to eliminate turtles, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. (Wikipedia)

Comb Sort

Worst case performance - O(n^2)

C++

void comb_sort(int array[], int length)
{
    int gap = length;
    bool swapped = true;
    while((gap > 1) || (swapped == true))
    {
        gap /= 1.25;
        if (gap < 1)
        {
            gap = 1;
        }
        int i = 0;
        swapped = false;
        while (i + gap < length)
        {
            if (array[i] > array[i + gap])
            {
                int temp = array[i];
                array[i] = array[i + gap];
                array[i + gap] = temp;
                swapped = true;
            }
            i++;
        }
    }
} 

Java

      public int[] comb_sort(int[] array) {
        int gap = array.length;
        boolean swapped = true;
        while ((gap > 1) || (swapped == true)) {
            gap /= 1.25;
            if (gap < 1) {
                gap = 1;
            }
            int i = 0;
            swapped = false;
            while (i + gap < array.length) {
                if (array[i] > array[i + gap]) {
                    int temp = array[i];
                    array[i] = array[i + gap];
                    array[i + gap] = temp;
                    swapped = true;
                }
                i++;
            }
        }
        return array;
    }

Matlab

function array = comb_sort(array)
    gap = numel(array);
    swapped = true;
    while (gap > 1) || swapped
        gap = floor(gap/1.25);
        if gap < 1
            gap = 1;
        end
        i = 1;
        swapped = false;
        while (i+gap-1) < numel(array)
            if array(i) > array(i+gap)
                array([i i+gap]) = array([i+gap i]);
                swapped = true;
            end
            i = i + 1;
        end
    end
end

Python

import math

def comb_sort(array):
    gap = len(array)
    swapped = True
    while gap > 1 or swapped :
        gap = math.floor(gap/1.25)
        if gap < 1 :
            gap = 1
        i = 0
        swapped = False
        while (i+gap)< len(array):
            if array[i] > array[i + gap]:
                temp = array[i]
                array[i] = array[i + gap]
                array[i + gap] = temp
                swapped = True
            i = i + 1