849:
Another optimization can be that the algorithm remembers where the last actual swap has been done. In the next iteration, there will be no swaps beyond this limit and the algorithm has shorter passes. As the cocktail shaker sort goes bidirectionally, the range of possible swaps, which is the range to
425:
The first rightward pass will shift the largest element to its correct place at the end, and the following leftward pass will shift the smallest element to its correct place at the beginning. The second complete pass will shift the second largest and second smallest elements to their correct places,
835:. It differs in that instead of repeatedly passing through the list from bottom to top, it passes alternately from bottom to top and then from top to bottom. It can achieve slightly better performance than a standard bubble sort. The reason for this is that
927:
if the list is mostly ordered before applying the sorting algorithm. For example, if every element is at a position that differs by at most k (k ≥ 1) from the position it is going to end up in, the complexity of cocktail shaker sort becomes
438:
elements in the list are in their correct positions, and do not need to be checked. By shortening the part of the list that is sorted each time, the number of operations can be halved (see
38:
1208:
842:
An example of a list that proves this point is the list (2,3,4,5,1), which would only need to go through one pass of cocktail sort to become sorted, but if using an ascending
846:
would take four passes. However one cocktail sort pass should be counted as two bubble sort passes. Typically cocktail sort is less than two times faster than bubble sort.
196:
107:
896:
961:
148:
925:
236:
1047:
975:
But none of these refinements leads to an algorithm better than straight insertion ; and we already know that straight insertion isn't suitable for large
979:. In short, the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems.
1158:
1041:
1212:
445:
This is an example of the algorithm in MATLAB/OCTAVE with the optimization of remembering the last swap index and updating the bounds.
293:
Like most variants of bubble sort, cocktail shaker sort is used primarily as an educational tool. More performant algorithms such as
1241:
1024:
1202:
1264:
967:
37:
1572:
202:
154:
113:
65:
1605:
1203:
Java source code and an animated demo of cocktail sort (called bi-directional bubble sort) and several other algorithms
971:, along with similar refinements of bubble sort. In conclusion, Knuth states about bubble sort and its improvements:
1109:"[JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort - Java Bug System"
839:
only passes through the list in one direction and therefore can only move items backward one step each iteration.
1705:
1279:
1577:
286:. The algorithm extends bubble sort by operating in two directions. While it improves on bubble sort by more
1485:
1365:
1319:
1073:
Duhl, Martin (1986). "Die schrittweise
Entwicklung und Beschreibung einer Shuffle-Sort-Array Schaltung".
1710:
1646:
1234:
1040:
Black, Paul E.; Bockholt, Bob (24 August 2009). "bidirectional bubble sort". In Black, Paul E. (ed.).
1625:
1490:
1133:
58:
1197:
305:
are used by the sorting libraries built into popular programming languages such as Python and Java.
1641:
1380:
1173:
1531:
1506:
1480:
1284:
1082:
1350:
1051:
164:
75:
1289:
1250:
1020:
865:
48:
1592:
1459:
1227:
931:
205:
123:
1653:
1536:
1408:
1309:
1304:
1294:
1094:
901:
212:
157:
116:
68:
1314:
1658:
1567:
1434:
1403:
1388:
1269:
1169:
1016:
859:
267:
1699:
1526:
1299:
797:% increases `beginIdx` because the elements before `newBeginIdx` are in correct order
1541:
1454:
1324:
1108:
1008:
850:
be tested, will reduce per pass, thus reducing the overall running time slightly.
1674:
1516:
1340:
1274:
843:
836:
832:
656:% decreases `endIdx` because the elements after `newEndIdx` are in correct order
439:
287:
283:
1620:
1600:
1582:
1546:
1475:
1413:
1398:
1360:
298:
17:
1615:
1551:
1521:
1511:
1449:
1444:
1439:
1418:
1370:
1355:
294:
1684:
1679:
1393:
1075:
1610:
898:
for both the worst case and the average case, but it becomes closer to
302:
1219:
1209:".NET Implementation of cocktail sort and several other algorithms"
467:% `beginIdx` and `endIdx` marks the first and last index to check
1223:
965:
The cocktail shaker sort is also briefly discussed in the book
418:// if no elements have been swapped, then the list is sorted
406:swap(A, A) swapped := true
313:
The simplest form goes through the whole list each time:
375:// we can exit the outer loop here if no swaps occurred.
354:// test whether the two elements are in the wrong order
290:, it provides only marginal performance improvements.
1015:. Vol. 3. Sorting and Searching (1st ed.).
934:
904:
868:
215:
167:
126:
78:
1077:(in German). Technical University of Kaiserslautern.
1667:
1634:
1591:
1560:
1499:
1468:
1427:
1379:
1333:
1257:
241:
201:
153:
112:
64:
54:
44:
955:
919:
890:
230:
190:
142:
101:
288:quickly moving items to the beginning of the list
973:
1048:National Institute of Standards and Technology
858:The complexity of the cocktail shaker sort in
831:Cocktail shaker sort is a slight variation of
1235:
8:
1043:Dictionary of Algorithms and Data Structures
30:
1242:
1228:
1220:
1166:The Grand Challenge to Reinvent Computing
933:
903:
879:
867:
214:
187:
178:
166:
139:
125:
98:
89:
77:
1003:
1001:
999:
995:
1090:
1080:
266:(which can also refer to a variant of
29:
358:// let the two elements change places
7:
25:
1198:Interactive demo of cocktail sort
1011:(1973). "Sorting by Exchanging".
360:swapped := true
1159:"A new World Model of Computing"
36:
1265:Computational complexity theory
968:The Art of Computer Programming
1172:, Brazil: CSBC. Archived from
1134:"[Python-Dev] Sorting"
947:
938:
914:
908:
885:
872:
383:swapped := false
330:swapped := false
225:
219:
184:
171:
136:
130:
95:
82:
1:
1157:Hartenstein, R. (July 2010).
827:Differences from bubble sort
1013:Art of Computer Programming
1727:
1573:Batcher odd–even mergesort
1132:Peters, Tim (2002-07-20).
191:{\displaystyle O(n^{2})\,}
102:{\displaystyle O(n^{2})\,}
256:bidirectional bubble sort
35:
1578:Pairwise sorting network
891:{\displaystyle O(n^{2})}
447:
323:list of sortable items)
1606:Kirkpatrick–Reisch sort
1486:Oscillating merge sort
1366:Proportion extend sort
1320:Transdichotomous model
987:
957:
956:{\displaystyle O(kn).}
921:
892:
232:
192:
144:
143:{\displaystyle O(n)\,}
103:
1647:Pre-topological order
1113:bugs.openjdk.java.net
958:
922:
893:
319:cocktailShakerSort(A
282:, is an extension of
233:
193:
145:
104:
1626:Merge-insertion sort
1491:Polyphase merge sort
1346:Cocktail shaker sort
1019:. pp. 110–111.
932:
920:{\displaystyle O(n)}
902:
866:
252:Cocktail shaker sort
231:{\displaystyle O(1)}
213:
165:
124:
76:
31:Cocktail shaker sort
1642:Topological sorting
1404:Cartesian tree sort
378:break do-while loop
32:
1532:Interpolation sort
1507:American flag sort
1500:Distribution sorts
1481:Cascade merge sort
1251:Sorting algorithms
953:
917:
888:
457:cocktailShakerSort
430:passes, the first
228:
188:
140:
99:
1693:
1692:
1668:Impractical sorts
426:and so on. After
249:
248:
49:Sorting algorithm
27:Sorting algorithm
16:(Redirected from
1718:
1706:Comparison sorts
1601:Block merge sort
1561:Concurrent sorts
1460:Patience sorting
1244:
1237:
1230:
1221:
1216:
1211:. Archived from
1187:
1185:
1184:
1178:
1163:
1144:
1143:
1141:
1140:
1129:
1123:
1122:
1120:
1119:
1105:
1099:
1098:
1092:
1088:
1086:
1078:
1070:
1064:
1063:
1061:
1059:
1054:on 16 March 2013
1050:. Archived from
1037:
1031:
1030:
1009:Knuth, Donald E.
1005:
985:
962:
960:
959:
954:
926:
924:
923:
918:
897:
895:
894:
889:
884:
883:
822:
819:
816:
813:
810:
807:
804:
801:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
768:
765:
762:
759:
756:
753:
750:
747:
744:
741:
738:
735:
732:
729:
726:
723:
720:
717:
714:
711:
708:
705:
702:
699:
696:
693:
690:
687:
684:
681:
678:
675:
672:
669:
666:
663:
660:
657:
654:
651:
648:
645:
642:
639:
636:
633:
630:
627:
624:
621:
618:
615:
612:
609:
606:
603:
600:
597:
594:
591:
588:
585:
582:
579:
576:
573:
570:
567:
564:
561:
558:
555:
552:
549:
546:
543:
540:
537:
534:
531:
528:
525:
522:
519:
516:
513:
510:
507:
504:
501:
498:
495:
492:
489:
486:
483:
480:
477:
474:
471:
468:
465:
461:
458:
455:
451:
419:
376:
359:
355:
254:, also known as
237:
235:
234:
229:
206:space complexity
197:
195:
194:
189:
183:
182:
149:
147:
146:
141:
108:
106:
105:
100:
94:
93:
40:
33:
21:
1726:
1725:
1721:
1720:
1719:
1717:
1716:
1715:
1696:
1695:
1694:
1689:
1663:
1654:Pancake sorting
1630:
1587:
1556:
1537:Pigeonhole sort
1495:
1464:
1428:Insertion sorts
1423:
1409:Tournament sort
1381:Selection sorts
1375:
1329:
1310:Integer sorting
1305:Sorting network
1295:Comparison sort
1253:
1248:
1207:
1194:
1182:
1180:
1176:
1161:
1156:
1153:
1148:
1147:
1138:
1136:
1131:
1130:
1126:
1117:
1115:
1107:
1106:
1102:
1089:
1079:
1072:
1071:
1067:
1057:
1055:
1039:
1038:
1034:
1027:
1007:
1006:
997:
992:
986:
983:
930:
929:
900:
899:
875:
864:
863:
856:
829:
824:
823:
820:
817:
814:
811:
808:
805:
802:
799:
796:
793:
790:
787:
784:
781:
778:
775:
772:
769:
766:
763:
760:
757:
754:
751:
748:
745:
742:
739:
736:
733:
730:
727:
724:
721:
718:
715:
712:
709:
706:
703:
700:
697:
694:
691:
688:
685:
682:
679:
676:
673:
670:
667:
664:
661:
658:
655:
652:
649:
646:
643:
640:
637:
634:
631:
628:
625:
622:
619:
616:
613:
610:
607:
604:
601:
598:
595:
592:
589:
586:
583:
580:
577:
574:
571:
568:
565:
562:
559:
556:
553:
550:
547:
544:
541:
538:
535:
532:
529:
526:
523:
520:
517:
514:
511:
508:
505:
502:
499:
496:
493:
490:
487:
484:
481:
478:
475:
472:
469:
466:
463:
459:
456:
453:
449:
423:
417:
374:
357:
353:
311:
211:
210:
174:
163:
162:
122:
121:
85:
74:
73:
28:
23:
22:
15:
12:
11:
5:
1724:
1722:
1714:
1713:
1708:
1698:
1697:
1691:
1690:
1688:
1687:
1682:
1677:
1671:
1669:
1665:
1664:
1662:
1661:
1659:Spaghetti sort
1656:
1651:
1650:
1649:
1638:
1636:
1632:
1631:
1629:
1628:
1623:
1618:
1613:
1608:
1603:
1597:
1595:
1589:
1588:
1586:
1585:
1580:
1575:
1570:
1568:Bitonic sorter
1564:
1562:
1558:
1557:
1555:
1554:
1549:
1544:
1539:
1534:
1529:
1524:
1519:
1514:
1509:
1503:
1501:
1497:
1496:
1494:
1493:
1488:
1483:
1478:
1472:
1470:
1466:
1465:
1463:
1462:
1457:
1452:
1447:
1442:
1437:
1435:Insertion sort
1431:
1429:
1425:
1424:
1422:
1421:
1419:Weak-heap sort
1416:
1411:
1406:
1401:
1396:
1391:
1389:Selection sort
1385:
1383:
1377:
1376:
1374:
1373:
1368:
1363:
1358:
1353:
1348:
1343:
1337:
1335:
1334:Exchange sorts
1331:
1330:
1328:
1327:
1322:
1317:
1312:
1307:
1302:
1297:
1292:
1287:
1282:
1277:
1272:
1270:Big O notation
1267:
1261:
1259:
1255:
1254:
1249:
1247:
1246:
1239:
1232:
1224:
1218:
1217:
1215:on 2012-02-12.
1205:
1200:
1193:
1192:External links
1190:
1189:
1188:
1170:Belo Horizonte
1152:
1149:
1146:
1145:
1124:
1100:
1091:|journal=
1065:
1032:
1025:
1017:Addison-Wesley
994:
993:
991:
988:
981:
952:
949:
946:
943:
940:
937:
916:
913:
910:
907:
887:
882:
878:
874:
871:
860:big O notation
855:
852:
828:
825:
448:
391:length(A) − 1
342:length(A) − 1
315:
310:
307:
268:selection sort
247:
246:
243:
239:
238:
227:
224:
221:
218:
208:
199:
198:
186:
181:
177:
173:
170:
160:
151:
150:
138:
135:
132:
129:
119:
110:
109:
97:
92:
88:
84:
81:
71:
62:
61:
56:
55:Data structure
52:
51:
46:
42:
41:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1723:
1712:
1709:
1707:
1704:
1703:
1701:
1686:
1683:
1681:
1678:
1676:
1673:
1672:
1670:
1666:
1660:
1657:
1655:
1652:
1648:
1645:
1644:
1643:
1640:
1639:
1637:
1633:
1627:
1624:
1622:
1619:
1617:
1614:
1612:
1609:
1607:
1604:
1602:
1599:
1598:
1596:
1594:
1590:
1584:
1581:
1579:
1576:
1574:
1571:
1569:
1566:
1565:
1563:
1559:
1553:
1550:
1548:
1545:
1543:
1540:
1538:
1535:
1533:
1530:
1528:
1527:Counting sort
1525:
1523:
1520:
1518:
1515:
1513:
1510:
1508:
1505:
1504:
1502:
1498:
1492:
1489:
1487:
1484:
1482:
1479:
1477:
1474:
1473:
1471:
1467:
1461:
1458:
1456:
1453:
1451:
1448:
1446:
1443:
1441:
1438:
1436:
1433:
1432:
1430:
1426:
1420:
1417:
1415:
1412:
1410:
1407:
1405:
1402:
1400:
1397:
1395:
1392:
1390:
1387:
1386:
1384:
1382:
1378:
1372:
1369:
1367:
1364:
1362:
1359:
1357:
1354:
1352:
1351:Odd–even sort
1349:
1347:
1344:
1342:
1339:
1338:
1336:
1332:
1326:
1323:
1321:
1318:
1316:
1315:X + Y sorting
1313:
1311:
1308:
1306:
1303:
1301:
1300:Adaptive sort
1298:
1296:
1293:
1291:
1288:
1286:
1283:
1281:
1278:
1276:
1273:
1271:
1268:
1266:
1263:
1262:
1260:
1256:
1252:
1245:
1240:
1238:
1233:
1231:
1226:
1225:
1222:
1214:
1210:
1206:
1204:
1201:
1199:
1196:
1195:
1191:
1179:on 2013-08-07
1175:
1171:
1167:
1160:
1155:
1154:
1150:
1135:
1128:
1125:
1114:
1110:
1104:
1101:
1096:
1084:
1076:
1069:
1066:
1053:
1049:
1045:
1044:
1036:
1033:
1028:
1026:0-201-03803-X
1022:
1018:
1014:
1010:
1004:
1002:
1000:
996:
989:
980:
978:
972:
970:
969:
963:
950:
944:
941:
935:
911:
905:
880:
876:
869:
861:
853:
851:
847:
845:
840:
838:
834:
826:
446:
443:
441:
437:
434:and the last
433:
429:
422:
421:end procedure
415:
412:
409:
405:
401:
398:
394:
390:
386:
382:
379:
373:
369:
366:
363:
352:
348:
345:
341:
337:
333:
329:
326:
322:
318:
314:
308:
306:
304:
300:
296:
291:
289:
285:
281:
277:
273:
269:
265:
261:
260:cocktail sort
257:
253:
244:
240:
222:
216:
209:
207:
204:
200:
179:
175:
168:
161:
159:
156:
152:
133:
127:
120:
118:
115:
111:
90:
86:
79:
72:
70:
67:
63:
60:
57:
53:
50:
47:
43:
39:
34:
19:
18:Cocktail sort
1711:Stable sorts
1593:Hybrid sorts
1542:Proxmap sort
1455:Library sort
1345:
1325:Quantum sort
1213:the original
1181:. Retrieved
1174:the original
1165:
1137:. Retrieved
1127:
1116:. Retrieved
1112:
1103:
1074:
1068:
1056:. Retrieved
1052:the original
1042:
1035:
1012:
976:
974:
966:
964:
857:
848:
841:
830:
444:
435:
431:
427:
424:
420:
413:
410:
407:
403:
399:
396:
392:
388:
384:
380:
377:
371:
367:
364:
361:
350:
346:
343:
339:
335:
331:
327:
324:
320:
316:
312:
292:
280:shuttle sort
279:
276:shuffle sort
275:
271:
263:
259:
255:
251:
250:
1675:Stooge sort
1517:Bucket sort
1469:Merge sorts
1341:Bubble sort
1285:Inplacement
1275:Total order
984:D. E. Knuth
844:bubble sort
837:bubble sort
833:bubble sort
806:newBeginIdx
779:newBeginIdx
521:newBeginIdx
440:bubble sort
356:swap(A, A)
284:bubble sort
272:ripple sort
264:shaker sort
158:performance
117:performance
69:performance
1700:Categories
1621:Spreadsort
1583:Samplesort
1547:Radix sort
1476:Merge sort
1414:Cycle sort
1399:Smoothsort
1361:Gnome sort
1183:2011-01-14
1139:2020-01-11
1118:2020-01-11
1058:5 February
990:References
854:Complexity
309:Pseudocode
299:merge sort
203:Worst-case
66:Worst-case
1616:Introsort
1552:Flashsort
1522:Burstsort
1512:Bead sort
1450:Tree sort
1445:Splaysort
1440:Shellsort
1371:Quicksort
1356:Comb sort
1290:Stability
1093:ignored (
1083:cite book
665:newEndIdx
638:newEndIdx
533:newEndIdx
402:A > A
349:A > A
317:procedure
295:quicksort
114:Best-case
1685:Bogosort
1680:Slowsort
1394:Heapsort
982:—
800:beginIdx
701:beginIdx
554:beginIdx
539:beginIdx
512:beginIdx
470:beginIdx
450:function
416:swapped
385:for each
370:swapped
332:for each
1611:Timsort
1151:Sources
411:end for
365:end for
303:timsort
242:Optimal
155:Average
1258:Theory
1023:
686:endIdx
659:endIdx
560:endIdx
527:endIdx
518:endIdx
488:length
482:endIdx
408:end if
381:end if
368:if not
362:end if
1635:Other
1280:Lists
1177:(PDF)
1162:(PDF)
515:<=
509:while
414:while
301:, or
278:, or
59:Array
45:Class
1095:help
1060:2010
1021:ISBN
743:deal
719:>
602:deal
578:>
404:then
372:then
351:then
862:is
821:end
818:end
794:end
791:end
776:));
677:for
653:end
650:end
635:));
545:for
442:).
397:do:
344:do:
270:),
1702::
1168:.
1164:.
1111:.
1087::
1085:}}
1081:{{
1046:.
998:^
785:ii
767:ii
758:),
755:ii
728:ii
713:ii
704:if
680:ii
644:ii
626:ii
617:),
614:ii
587:ii
572:ii
563:if
548:ii
400:if
395:0
393:to
389:in
387:i
347:if
340:to
338:0
336:in
334:i
328:do
325:is
297:,
274:,
262:,
258:,
245:No
1243:e
1236:t
1229:v
1186:.
1142:.
1121:.
1097:)
1062:.
1029:.
977:N
951:.
948:)
945:n
942:k
939:(
936:O
915:)
912:n
909:(
906:O
886:)
881:2
877:n
873:(
870:O
815:;
812:1
809:+
803:=
788:;
782:=
773:1
770:+
764:(
761:A
752:(
749:A
746:(
740:=
737:)
734:1
731:+
725:(
722:A
716:)
710:(
707:A
698::
695:1
692:-
689::
683:=
674:;
671:1
668:-
662:=
647:;
641:=
632:1
629:+
623:(
620:A
611:(
608:A
605:(
599:=
596:)
593:1
590:+
584:(
581:A
575:)
569:(
566:A
557::
551:=
542:;
536:=
530:;
524:=
506:;
503:1
500:-
497:)
494:A
491:(
485:=
479:;
476:1
473:=
464:)
462:A
460:(
454:=
452:A
436:i
432:i
428:i
321::
226:)
223:1
220:(
217:O
185:)
180:2
176:n
172:(
169:O
137:)
134:n
131:(
128:O
96:)
91:2
87:n
83:(
80:O
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
