JavaScript is required for this website. Please allow JavaScript and refresh the page.
home Home
sort Sorts
LOGARITHMIC
Quick Sort Merge Sort Heap Sort
QUADRATIC
Bubble Sort Selection Sort Insertion Sort Gnome Sort Shaker Sort Odd Even Sort Pancake Sort
WEIRD
Bitonic Sort Radix Sort Shell Sort Comb Sort Bogo Sort
CUSTOM
Your Sort
SORT VISUALIZER
Comb Sort
Elements: 100
DESCRIPTION

Comb Sort is a sorting algorithm really similar to Bubble Sort. It highly improves its performances by removing the "turtles", that is the small elements placed near the end of the data structure that slows down a lot the performances of Bubble Sort.

Bubble Sort is based on comparing adjacent elements, so with a distance of 1. Comb Sort increases this distance using a shrink factor k (usually with a value of 1.3). Initially, the distance has a value of n. For each iteration, a Bubble Sort gets executed using the new distance value instead of 1. The distance gets progressively divided by the shrink factor k.

This procedure gets executed until the distance reaches the value of 1. At this point, the algorithm is a regular Bubble Sort, but the majority of the "turtles" already got removed.

Its average time complexity depends, in addition to the number of elements of the data structure, by a value p, representing the number of divisions carried out.

COMPLEXITY
Average Complexity Ω(n2 / 2p)
Best Case Θ(n × log n)
Worst Case O(n2)
Space Complexity O(1)