Talk:Cocktail shaker sort

performance

As the article says, cocktail sort is a slight modification to bubble / exchange sort. Given that, and on inspecting the code, it looks to me that the worst-case performance is $O(n^{2})$ rather than $O(n^{3})$. I'm going to do a bit of research on this first before editing the article, though. Jgoulden (talk) 22:09, 15 October 2008 (UTC)

You are correct, a bidirectional bubble sort is $O(n^{2})$. A simple proof is that one forward-and-back traversal guarantees the first and last element of the list are in the correct position. One traversal takes $2n$ steps, and sorting the list takes no more than $n/2$ traversals, so the result is $O(n^{2})$.

If you examine the page history, the edits from 217.205.57.110 in October are clearly vandalism, and this particular vandal chose to make bubble sort an $O(n^{3})$ algorithm, among other absurdities. Unfortunately people did not realize this and attempted to correct the vandal; I've reviewed all the changes and simply reverted everything to as it was at the beginning of the month, as all of the other changes were incomplete attempts to fix the vandalism. Obscuranym (talk) 09:13, 22 October 2008 (UTC)

sort

This algorithm can be refined by recording the last swap in each pass. For each step where you don't swap; if you have not swapped yet then move the start limit up, and if you're at the end limit then set that limit to your last swap and end that pass. Stop when the limits meet, or start the next pass at the new limit. This is helpful when only a limited area of the array has been de-sorted. In some applications you'll be able to pre-load the limits with helpful values.

It also speeds the algorithm up quite a bit on data that's already almost sorted. About eight years ago, I implemented the cocktail sort algorithm before I'd heard it given a name. My program was a simple flat database app. To delete a record it would move a record from the end to fill its place. When the user adds, deletes and changes some records and then issues the sort command, the cocktail sort would simply and efficiently move the added records down into place, the records moved to replace deleted ones back up to the end, and the modified records in whatever direction they need to go. -- Smjg 12:26, 31 Mar 2005 (UTC)

---

I've also come across "shaker sort" meaning something else: a variation of selection sort in which the minimum and maximum elements are picked out in each pass. We don't seem to have a mention of this variation - maybe this should be added to the Selection sort page and then mentioned here? -- Smjg 22:03, 30 Mar 2005 (UTC)

Sure, go ahead. You need to be bold in editing pages and do that yourself! After all, you're the one who knows about that alternate meaning and can explain it. Graue 00:49, 24 Apr 2005 (UTC)

Since Smjg didn't add it, I did (forgot to log in...). In case anyone's interested, there's an example implementation at http://www.cs.ubc.ca/spider/harrison/Java/. Is it worth making 'shaker sort' a page of its own which notes that it's also (more commonly) used as a name for cocktail sort? It's the 'more commonly' bit there that makes me somewhat apprehensive... that page is about the only one I can find where the name is used for something other than cocktail sort. Deewiant 18:17, 06 Aug 2005 (UTC)

F77 example

I would have done this with nice, PIC fortran 95 but I've only just begun to update my skills to the current standard. Oh well, perhaps someone who knows more than I can post code more up-to-date with current programming practice. CAPS LOCK