Lecture
Comb sort (English: comb sort) — is a fairly simplified sorting algorithm, originally designed by Wlodzimierz Dobosiewicz in 1980. It was later rediscovered and popularized in an article by Stephen Lacey and Richard Box in Byte Magazine in April 1991 . Comb sort improves upon bubble sort, and competes with algorithms similar to quicksort. The main idea is to eliminate turtles, or small values at the end of the list, which slow bubble sort down considerably (rabbits, large values at the beginning of the list, are not a problem for bubble sort).
In bubble sort, when two elements are compared, the gap (distance from each other) is equal to 1. The main idea of comb sort is that this gap can be much larger than one (Shell sort is also based on this idea, but it is a modification of insertion sort rather than bubble sort).
In "bubble," "shaker," and "odd-even" sort, when traversing the array, adjacent elements are compared. The main idea of "comb" sort is that initially a fairly large distance is taken between the elements being compared, and as the array becomes more ordered, this distance is narrowed down to the minimum. In this way, we are, so to speak, combing the array, gradually smoothing out ever neater strands. It is best to choose the initial gap between the compared elements with regard to a special quantity called the shrink factor, whose optimal value is approximately 1.247 . Initially, the distance between elements is at its maximum, that is, equal to the size of the array minus one. Then, after passing through the array with this step, the step must be divided by the shrink factor and the list passed through again. This continues until the difference between the indices reaches one. In that case, adjacent elements are compared just as in bubble sort, but only for a single iteration.
The optimal value of the shrink factor is 
, where 
— is the base of the natural logarithm, and 
— is the golden ratio.
const n = 5; var a: array [0..n] of integer; i, jr: integer; j: real; begin for i := 0 to n do a[i] := Random(12); j := n; jr := Round(j); while i < i + jr do begin i := 0; jr := Round(j); while i + j <= n do begin if a[i] > a[i + Round(j)] then begin a[i] := a[i] + a[i + jr]; a[i + jr] := a[i] - a[i + jr]; a[i] := a[i] - a[i + jr]; end; Inc(i); end; j := j / 1.247; end; for i := 0 to n do begin for jr := 0 to i - 1 do begin if a[jr] > a[jr + 1] then begin a[jr] := a[jr] + a[jr + 1]; a[jr + 1] := a[jr] - a[jr + 1]; a[jr] := a[jr] - a[jr + 1]; end; end; end; Writeln(a); end.
The loop will stop only when j becomes equal to 0, in other words, when i becomes equal to i + j.
void comb(std::vector<int> &data) // data — the name of the vector (passed by reference, so that calling comb(array) modifies the array vector)
{
double factor = 1.2473309; // shrink factor
int step = data.size() - 1; // sorting step
//The last iteration of the loop, when step==1, is equivalent to a single pass of bubble sort
while (step >= 1)
{
for (int i = 0; i + step < data.size(); i++)
{
if (data[i] > data[i + step])
{
std::swap(data[i], data[i + step]);
}
}
step /= factor;
}
}
function combsort($array) { $sizeArray = count($array); // Iterate through all elements of the array for ($i = 0; $i < $sizeArray; $i++) { // Compare in pairs. // We start with the first and last element, then gradually shrink // the range of values being compared. for ($j = 0; $j < $i + 1; $j++) { // Index of the right-hand element in the current comparison iteration $elementRight = ($sizeArray - 1) - ($i - $j); if ($array[$j] > $array[$elementRight]) { $buff = $array[$j]; $array[$j] = $array[$elementRight]; $array[$elementRight] = $buff; unset($buff); } } } return $array; }
def combsort(alist): alen = len(alist) gap = (alen * 10 // 13) if alen > 1 else 0 while gap: if 8 < gap < 11: ## variant "comb-11" gap = 11 swapped = False for i in range(alen - gap): if alist[i + gap] < alist[i]: alist[i], alist[i + gap] = alist[i + gap], alist[i] swapped = True gap = (gap * 10 // 13) or swapped
function combSorting(array) {
var interval = Math.floor(array.length / 1.3);
while (interval > 0) {
for(var i = 0; i + interval < array.length; i++) {
if (array[i] > array[i + interval]) {
var small = array[i + interval];
array[i + interval] = array[i];
array[i] = small;
}
}
interval = Math.floor(interval / 1.3);
}
}
|
Sorting algorithms
|
|
|---|---|
| Theory |
Complexity O-notation Order relation Types of sorting
Stable Internal External |
| Exchange |
|
| Selection |
|
| Insertion |
|
| Merge |
|
| Non-comparison |
|
| Hybrid |
|
| Other |
|
| Impractical |
|
Comments