if [ - [jthen : [ - ] [ - : [ ] [ :xk : end endl : + for : to by + do if [ - [jthen : [ - ] [ - : [ ] [ :xk : end endr : - until end shakersort dir table an example of shakersort analysis of bubblesort and shakersort the number of comparisons in the straight exchange algorithm is ( )/ and the minimumaverageand maximum numbers of moves (assignments of itemsare mmin mavg *( )/ mmax *( )/ the analysis of the improved methodsparticularly that of shakersortis intricate the least number of comparisons is cmin - for the improved bubblesortknuth arrives at an average number of passes proportional to * / and an average number of comparisons proportional ( *( ln( )))/ but we note that all improvements mentioned above do in no way affect the number of exchangesthey only reduce the number of redundant double checks unfortunatelyan exchange of two items is generally more costly operation than comparison of keysour clever improvements therefore have much less profound effect than one would intuitively expect this analysis shows that the exchange sort and its minor improvements are inferior to both the insertion and the selection sortsand in factthe bubblesort has hardly anything to recommend it except its catchy name the shakersort algorithm is used with advantage in those cases in which it is known that the items are already almost in order rare case in practice it can be shown that the average distance that each of the items has to travel during sort is / places this figure provides clue in the search for improvedi more effective sorting methods all straight sorting methods essentially move each item by one position in each elementary step thereforethey are bound to require in the order such steps any improvement must be based on the principle of moving items over greater distances in single leaps