341:(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.
348:= 4/3 = 1.333…, while Lacey and Box suggest 1.3 as an ideal shrink factor after empirical testing on over 200,000 random lists of length approximately 1000. A value too small slows the algorithm down by making unnecessarily many comparisons, whereas a value too large fails to effectively deal with turtles, making it require many passes with a gap of 1.
351:
The pattern of repeated sorting passes with decreasing gaps is similar to
Shellsort, but in Shellsort the array is sorted completely each pass before going on to the next-smallest gap. Comb sort's passes do not completely sort the elements. This is the reason that
359:
One additional refinement suggested by Lacey and Box is the "rule of 11": always use a gap size of 11, rounding up gap sizes of 9 or 10 (reached by dividing gaps of 12, 13 or 14 by 1.3) to 11. This eliminates turtles surviving until the final gap-1 pass.
274:
originally designed by WĹ‚odzimierz
Dobosiewicz and Artur Borowy in 1980, later rediscovered (and given the name "Combsort") by Stephen Lacey and Richard Box in 1991. Comb sort improves on
295:
s "diminishing increment sort" definition mentions the term 'comb sort' as visualizing iterative passes of the data, "where the teeth of a comb touch;" the former term is linked to
213:
151:
27:
102:
260:
618:
290:
322:(distance from each other) of 1. The basic idea of comb sort is that the gap can be much larger than 1. The inner loop of bubble sort, which does the actual
564:
659:
326:, is modified such that the gap between swapped elements goes down (for each iteration of outer loop) in steps of a "shrink factor"
484:, or bidirectional bubble sort, is a variation of bubble sort that also addresses the problem of turtles, albeit less effectively.
682:
990:
509:
452:// If this assignment never happens within the loop, // then there have been no swaps and the list is sorted.
286:, in that they both allow elements that start far away from their intended position to move more than one space per swap.
226:
157:
108:
61:
1023:
1123:
697:
995:
26:
311:, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously.
447:
903:
783:
737:
167:
1064:
652:
118:
1043:
908:
763:
565:"A Fast, Easy Sort: A novel enhancement makes a bubble sort into one of the fastest sorting routines"
54:
1059:
798:
949:
924:
898:
702:
768:
574:
707:
668:
271:
71:
44:
1010:
877:
645:
592:
545:
518:
229:
344:
The shrink factor has a great effect on the efficiency of comb sort. Dobosiewicz suggested
1071:
954:
826:
727:
722:
712:
236:
160:
111:
64:
732:
1076:
985:
852:
821:
806:
687:
315:, large values around the beginning of the list, do not pose a problem in bubble sort.
283:
522:
1117:
944:
717:
569:
549:
481:
536:
Dobosiewicz, Wlodzimierz (29 August 1980). "An efficient variation of bubble sort".
959:
872:
742:
296:
613:
579:
1092:
934:
758:
692:
475:
275:
1038:
1018:
1000:
964:
893:
831:
816:
778:
435:
1033:
969:
939:
929:
867:
862:
857:
836:
788:
507:
Brejová, Bronislava (15 September 2001). "Analyzing variants of
Shellsort".
353:
279:
1102:
1097:
811:
1028:
318:
In bubble sort, when any two elements are compared, they always have a
637:
450:(input, input) sorted := false
573:. Vol. 16, no. 4. pp. 315–318, 320. Archived from
641:
478:, a generally slower algorithm, is the basis of comb sort.
239:
170:
121:
74:
1085:
1052:
1009:
978:
917:
886:
845:
797:
751:
675:
356:have a larger optimal shrink factor of about 2.25.
225:
156:
107:
60:
50:
40:
254:
207:
145:
96:
405:// If there are no swaps this pass, we are done
619:National Institute of Standards and Technology
403:gap := 1 sorted := true
653:
333:The gap starts out as the length of the list
8:
19:
563:Lacey, Stephen; Box, Richard (April 1991).
660:
646:
638:
337:being sorted divided by the shrink factor
238:
196:
187:
181:
169:
120:
85:
73:
395:gap := floor(gap / shrink)
494:
393:// Update the gap value for a next comb
426:// A single "comb" over the input list
18:
7:
502:
500:
498:
208:{\displaystyle \Omega (n^{2}/2^{p})}
171:
122:
14:
146:{\displaystyle \Theta (n\log n)}
25:
16:Interval based sorting algorithm
683:Computational complexity theory
307:The basic idea is to eliminate
538:Information Processing Letters
510:Information Processing Letters
249:
243:
202:
174:
140:
125:
91:
78:
1:
523:10.1016/S0020-0190(00)00223-4
31:Comb sort with shrink factor
593:"diminishing increment sort"
550:10.1016/0020-0190(80)90022-8
385:// Set the gap shrink factor
221:is the number of increments
1140:
991:Batcher odd–even mergesort
582:available at archive.org.
457:i := i + 1
387:sorted := false
24:
996:Pairwise sorting network
97:{\displaystyle O(n^{2})}
1024:Kirkpatrick–Reisch sort
432:i + gap < input.size
391:sorted = false
379:gap := input.size
354:Shellsort gap sequences
270:is a relatively simple
904:Oscillating merge sort
784:Proportion extend sort
738:Transdichotomous model
381:// Initialize gap size
256:
209:
147:
98:
1065:Pre-topological order
278:in the same way that
257:
210:
148:
99:
1044:Merge-insertion sort
909:Polyphase merge sort
764:Cocktail shaker sort
428:i := 0
418:gap := 11
255:{\displaystyle O(1)}
237:
168:
119:
72:
1060:Topological sorting
822:Cartesian tree sort
420:// The "rule of 11"
383:shrink := 1.3
21:
950:Interpolation sort
925:American flag sort
918:Distribution sorts
899:Cascade merge sort
669:Sorting algorithms
438:for a similar idea
252:
205:
143:
94:
1111:
1110:
1086:Impractical sorts
443:input > input
272:sorting algorithm
265:
264:
45:Sorting algorithm
1131:
1124:Comparison sorts
1019:Block merge sort
979:Concurrent sorts
878:Patience sorting
662:
655:
648:
639:
632:
631:
629:
627:
610:
604:
603:
601:
599:
589:
583:
578:
560:
554:
553:
533:
527:
526:
504:
453:
439:
427:
421:
406:
394:
386:
382:
261:
259:
258:
253:
230:space complexity
220:
214:
212:
211:
206:
201:
200:
191:
186:
185:
152:
150:
149:
144:
103:
101:
100:
95:
90:
89:
29:
22:
1139:
1138:
1134:
1133:
1132:
1130:
1129:
1128:
1114:
1113:
1112:
1107:
1081:
1072:Pancake sorting
1048:
1005:
974:
955:Pigeonhole sort
913:
882:
846:Insertion sorts
841:
827:Tournament sort
799:Selection sorts
793:
747:
728:Integer sorting
723:Sorting network
713:Comparison sort
671:
666:
636:
635:
625:
623:
612:
611:
607:
597:
595:
591:
590:
586:
580:Entire magazine
562:
561:
557:
535:
534:
530:
506:
505:
496:
491:
472:
467:
451:
433:
425:
419:
404:
392:
384:
380:
366:
305:
235:
234:
216:
192:
177:
166:
165:
117:
116:
81:
70:
69:
36:
17:
12:
11:
5:
1137:
1135:
1127:
1126:
1116:
1115:
1109:
1108:
1106:
1105:
1100:
1095:
1089:
1087:
1083:
1082:
1080:
1079:
1077:Spaghetti sort
1074:
1069:
1068:
1067:
1056:
1054:
1050:
1049:
1047:
1046:
1041:
1036:
1031:
1026:
1021:
1015:
1013:
1007:
1006:
1004:
1003:
998:
993:
988:
986:Bitonic sorter
982:
980:
976:
975:
973:
972:
967:
962:
957:
952:
947:
942:
937:
932:
927:
921:
919:
915:
914:
912:
911:
906:
901:
896:
890:
888:
884:
883:
881:
880:
875:
870:
865:
860:
855:
853:Insertion sort
849:
847:
843:
842:
840:
839:
837:Weak-heap sort
834:
829:
824:
819:
814:
809:
807:Selection sort
803:
801:
795:
794:
792:
791:
786:
781:
776:
771:
766:
761:
755:
753:
752:Exchange sorts
749:
748:
746:
745:
740:
735:
730:
725:
720:
715:
710:
705:
700:
695:
690:
688:Big O notation
685:
679:
677:
673:
672:
667:
665:
664:
657:
650:
642:
634:
633:
605:
584:
577:on 2021-09-27.
555:
528:
517:(5): 223–227.
493:
492:
490:
487:
486:
485:
479:
471:
468:
367:
365:
362:
304:
301:
284:insertion sort
263:
262:
251:
248:
245:
242:
232:
223:
222:
204:
199:
195:
190:
184:
180:
176:
173:
163:
154:
153:
142:
139:
136:
133:
130:
127:
124:
114:
105:
104:
93:
88:
84:
80:
77:
67:
58:
57:
52:
51:Data structure
48:
47:
42:
38:
37:
30:
15:
13:
10:
9:
6:
4:
3:
2:
1136:
1125:
1122:
1121:
1119:
1104:
1101:
1099:
1096:
1094:
1091:
1090:
1088:
1084:
1078:
1075:
1073:
1070:
1066:
1063:
1062:
1061:
1058:
1057:
1055:
1051:
1045:
1042:
1040:
1037:
1035:
1032:
1030:
1027:
1025:
1022:
1020:
1017:
1016:
1014:
1012:
1008:
1002:
999:
997:
994:
992:
989:
987:
984:
983:
981:
977:
971:
968:
966:
963:
961:
958:
956:
953:
951:
948:
946:
945:Counting sort
943:
941:
938:
936:
933:
931:
928:
926:
923:
922:
920:
916:
910:
907:
905:
902:
900:
897:
895:
892:
891:
889:
885:
879:
876:
874:
871:
869:
866:
864:
861:
859:
856:
854:
851:
850:
848:
844:
838:
835:
833:
830:
828:
825:
823:
820:
818:
815:
813:
810:
808:
805:
804:
802:
800:
796:
790:
787:
785:
782:
780:
777:
775:
772:
770:
769:Odd–even sort
767:
765:
762:
760:
757:
756:
754:
750:
744:
741:
739:
736:
734:
733:X + Y sorting
731:
729:
726:
724:
721:
719:
718:Adaptive sort
716:
714:
711:
709:
706:
704:
701:
699:
696:
694:
691:
689:
686:
684:
681:
680:
678:
674:
670:
663:
658:
656:
651:
649:
644:
643:
640:
622:
620:
615:
609:
606:
594:
588:
585:
581:
576:
572:
571:
570:Byte Magazine
566:
559:
556:
551:
547:
543:
539:
532:
529:
524:
520:
516:
512:
511:
503:
501:
499:
495:
488:
483:
482:Cocktail sort
480:
477:
474:
473:
469:
466:
463:
460:
456:
449:
446:
442:
437:
431:
424:
417:
413:
409:
402:
398:
390:
378:
374:
370:
363:
361:
357:
355:
349:
347:
342:
340:
336:
331:
329:
325:
321:
316:
314:
310:
302:
300:
298:
294:
292:
287:
285:
281:
277:
273:
269:
246:
240:
233:
231:
228:
224:
219:
197:
193:
188:
182:
178:
164:
162:
159:
155:
137:
134:
131:
128:
115:
113:
110:
106:
86:
82:
75:
68:
66:
63:
59:
56:
53:
49:
46:
43:
39:
34:
28:
23:
1011:Hybrid sorts
960:Proxmap sort
873:Library sort
773:
743:Quantum sort
624:. Retrieved
617:
608:
596:. Retrieved
587:
575:the original
568:
567:. Hands On.
558:
541:
537:
531:
514:
508:
465:end function
464:
461:
458:
454:
444:
440:
429:
422:
415:
411:
407:
400:
396:
388:
376:
372:
368:
358:
350:
345:
343:
338:
334:
332:
327:
323:
319:
317:
312:
308:
306:
289:
288:
282:improves on
267:
266:
217:
32:
1093:Stooge sort
935:Bucket sort
887:Merge sorts
759:Bubble sort
703:Inplacement
693:Total order
614:"comb sort"
476:Bubble sort
276:bubble sort
161:performance
112:performance
65:performance
1039:Spreadsort
1001:Samplesort
965:Radix sort
894:Merge sort
832:Cycle sort
817:Smoothsort
779:Gnome sort
621:(nist.gov)
544:(1): 5–6.
489:References
436:Shell sort
430:loop while
389:loop while
364:Pseudocode
227:Worst-case
62:Worst-case
1034:Introsort
970:Flashsort
940:Burstsort
930:Bead sort
868:Tree sort
863:Splaysort
858:Shellsort
789:Quicksort
774:Comb sort
708:Stability
414:gap = 10
371:combsort(
303:Algorithm
297:Don Knuth
280:Shellsort
268:Comb sort
172:Ω
135:
123:Θ
109:Best-case
20:Comb sort
1118:Category
1103:Bogosort
1098:Slowsort
812:Heapsort
626:March 9,
598:March 9,
470:See also
462:end loop
459:end loop
410:gap = 9
399:gap ≤ 1
369:function
291:nist.gov
215:, where
35:=1.24733
1029:Timsort
434:// See
408:else if
375:input)
313:Rabbits
309:turtles
158:Average
676:Theory
455:end if
423:end if
1053:Other
698:Lists
373:array
55:Array
41:Class
628:2021
600:2021
448:swap
445:then
416:then
401:then
330:: .
324:swap
546:doi
519:doi
320:gap
132:log
1120::
616:.
542:11
540:.
515:79
513:.
497:^
441:if
412:or
397:if
377:is
299:.
661:e
654:t
647:v
630:.
602:.
552:.
548::
525:.
521::
346:k
339:k
335:n
328:k
293:'
250:)
247:1
244:(
241:O
218:p
203:)
198:p
194:2
189:/
183:2
179:n
175:(
141:)
138:n
129:n
126:(
92:)
87:2
83:n
79:(
76:O
33:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
