Thread: shaker sort

Hi,

so shaker sort is supposed to be bi-directional bubble sort but I tried with an example, how is is it any better than regular, terrible bubble sort?

e.g.
n = 12
I put braces around the sorted sub-lists
descending order list: 30,25,24,23,22,20,18,17,16,15,14,13

pass 1: 25,24,23,22,20,18,17,16,15,14,13{30}
pass 2: {13}, 25,24,23,22,20,18,17,16,15,14,{30}
pass 3: {13}, 24,23,22,20,18,17,16,15,14, {25,30}
pass 4: {13,14},24,23,22,20,18,17,16,15,{25,30}
pass 5: {13,14}, 23,22,20,18,17,16,15, {24,25,30}
pass 6: {13,14,15}, 23,22,20,18,17,16,{24,25,30}
pass 7: {13,14,15}, 22,20,18,17,16, {23,24,25,30}
pass 8: {13,14,15,16}, 22,20,18,17,{23,24,25,30}
pass 9: {13,14,15,16},20,18,17,{22,23,24,25,30}
pass 10: {13,14,15,16,17,18},20,18{22,23,24,25,30}
pass 11: {13,14,15, 16,17,18}20,{22,23,24,25,30} (20 is left, 1 items so trivially sorted)

It's still (n - 1) passes as in bubble sort, so how is it improvment by scanning in both directions? Any help appreciated.

Hello IHeartProgramming,
As you have already stated the number of passes is n-1 and thus not an improvement upon bubble sort. However, this is just a single example with a fairly small number of integers to sort through, and nothing in terms of random ordering of the integers. To answer your question, it is not an improvement at all, in this case, but with larger lists that need to be sorted in a less trivial fashion (ie random order to ascending/descending) you should see an improvement.