Comb Sort Algo in Java

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. Rabbits, large values around the beginning of the list, do not pose a problem in bubble sort.

In bubble sort, when any two elements are compared, they always have a gap (distance from each other) of 1. The basic idea of comb sort is that the gap can be much more than 1. The inner loop of bubble sort, which does the actual swap, is modified such that gap between swapped elements goes down (for each iteration of outer loop) in steps of shrink factor: [ input size / shrink factor, input size / shrink factor^2, input size / shrink factor^3, ..., 1 ].

The gap starts out as the length of the list being sorted divided by the shrink factor (generally 1.3; see below) and one pass of the aforementioned modified bubble sort is applied with that gap. Then the gap is divided by the shrink factor again, the list is sorted with this new gap, and the process repeats until the gap is 1. At this point, comb sort continues using a gap of 1 until the list is fully sorted. The final stage of the sort is thus equivalent to a bubble sort, but by this time most turtles have been dealt with, so a bubble sort will be efficient.

The shrink factor has a great effect on the efficiency of comb sort. 1.3 has been suggested as an ideal shrink factor by the authors of the original article after empirical testing on over 200,000 random lists. A value too small slows the algorithm down by making unnecessarily many comparisons, whereas a value too large fails to effectively deal with turtles.

So,Comb Sort is mainly an improvement over Bubble Sort. Bubble sort always compares adjacent values. So all inversions are removed one by one. Comb Sort improves on Bubble Sort by using gap of size more than 1. The gap starts with a large value and shrinks by a factor of 1.3 in every iteration until it reaches the value 1. Thus Comb Sort removes more than one inversion counts with one swap and performs better than Bublle Sort.

The shrink factor has been empirically found to be 1.3 (by testing Combsort on over 200,000 random lists).

Although, it works better than Bubble Sort on average, worst case remains O(n2).


Code Implementation:

import java.util.*;

public class CombSort
 {

    public static void sort(int[] array, int size)
    {
        int gap = size; // The distance between elements being compared
        boolean swapped = true;
        int i; // Our index

        while (gap > 1 || swapped)
        {
            if (gap > 1) {
                gap = (int)(gap / 1.3);
            }

            if (gap == 9 || gap == 10)
            {
                gap = 11;
            }

            i = 0;
            swapped = false;

            // Loop through comparing numbers a gap-length apart.
            // If the first number is bigger than the second, swap them.
            while (i + gap < size)
            {
                if (array[i] > array[i+gap])
                {
                    swap(array, i, i+gap);
                    swapped = true;
                }
                i++;
            }
        }
    }

    public static void swap(int[] list, int i, int j)
    {
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }

    public static String input(String s)
    {    
        System.out.print(s);
        Scanner scan = new Scanner(System.in);
        return scan.next();
    }

    public static void main(String[] args) {
        /* Ask the user how many numbers of what range
        should be sorted by the algorithm and if they want to see the array */

        int ammount = Integer.parseInt( input("How many numbers shall be generated? ") );
        int min = Integer.parseInt( input("Min value of numbers: ") );
        int max = Integer.parseInt( input("Max value of numbers: ") );
        boolean show_array = input("Would you like to see the sorted and unsorted list?(y/n) ").equals("y");
       
        int[] numbers = new int[ammount];
        Random rand = new Random();
        for (int n=0; n < ammount; n++)
        {
            numbers[n] = rand.nextInt(max - min + 1) + min;
        }

        if (show_array)
        {
            System.out.println("__UNSORTED ARRAY__");
            System.out.println(Arrays.toString(numbers));
        }
        sort(numbers, ammount);
        if (show_array)
        {
            System.out.println("__SORTED ARRAY__");
            System.out.println(Arrays.toString(numbers));
        }

    }
}

Output:

How many numbers shall be generated?
4
Min value of numbers: 2
Max value of numbers: 8
Would you like to see the sorted and unsorted list?(y/n) y
__UNSORTED ARRAY__
[5, 3, 8, 6]
__SORTED ARRAY__
[3, 5, 6, 8]


Another Implementation:

import java.util.Scanner;

public class CombSort
{
    public static void main(String[] args)
    {
        int i;
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter no elements you want (Size):");
        int size = sc.nextInt();
        int[] a = new int[size];
        System.out.println("Please enter the " + size + " elements:");
        for (i = 0; i < size; i++)
        {
            a[i] = sc.nextInt();
        }
        System.out.println("Sorted array is :");
        CombSort cs = new CombSort(a);
        for (i = 0; i < size; i++)
        {
            System.out.printf("%d\t", a[i]);
        }
    }
    private final int[] a;

    private CombSort(int[] b)
    {
        this.a = b;
        combSort(a.length);
    }

    private void combSort(int size)
    {
        float shrink = 1.3f;
        int swap;
        int i, gap = size;
        boolean swapped = false;
        while ((gap > 1) || swapped)
        {
            if (gap > 1)
            {
                gap = (int) ((float) gap / shrink);
            }
            swapped = false;
            for (i = 0; gap + i < size; ++i)
            {
                if (a[i] - a[i + gap] > 0)
                {
                    swap = a[i];
                    a[i] = a[i + gap];
                    a[i + gap] = swap;
                    swapped = true;
                }
            }
        }
    }
}

Result:

Enter no elements you want (Size):
4
Please enter the 4 elements:
12
23
08
44
Sorted array is :
8 12 23 44