Dobosiewicz Sort (also called Comb sort)

grasping the bytes > Information Visualization > Sort Algorithms Visualizer > Dobosiewicz Sort - (fr)

Sort Algorithms Visualizer

> Sort algorithms

Instructions

Exercises

Invented by Dobosiewicz in 1980, it can be interpreted as a variant of Shell sort, as it replaces a sequence of decreasing-gap insertion sort with bubble sort passes. In other words, this algorithm does to bubble sort what Shell sort does to insertion sort. This algorithm and its variants (that include a shaker pass or a brick pass) are interesting to study from a theoretical standpoint, nevertheless, all its variants are less efficient than the best Shell sorts, which is in turn less efficient than a tuned quicksort (when there is no need for stability), or a tuned merge sort (when stability is required).

public class DoboSort extends SortAlgorithm {
public DoboSort (int t, MainView v) {
super("Brick Sort", t, v);
}

int reduce(int gap) {
gap=gap*10/13;
if(gap==9||gap==10)
gap=11;
if(gap<1)
return 1;
return gap;
}

public void sort() {
int gap=size;
boolean swapped;
do {
swapped=false;
gap=reduce(gap);
for(int i=0; i < size-gap; i++) {
if(compare(i,i+gap)>0) {
swapped=true;
exchange(i, i+gap);
}
}
} while(gap>1||swapped);
}
}

This algorithm is mentioned in this paper. Quite a few pages on the net, including Wikipedia, attribute this algorithm to Stephen Lacey and Richard Box, who described it in Byte Magazine in April 1991.