Cocktail sort

The term refers to a stable Shakersort sort algorithm sorts a set of linearly arranged elements (eg, numbers) according to size. Other names for this algorithm are Cocktailsort, Ripplesort, Shearsort or BiDiBubbleSort ( bidirectional bubblesort ).

Principle

The field to be sorted is alternately run up and down. In each case two adjacent elements are compared and swapped if necessary.

Through this bi-directionality, there is a more rapid sedimentation of large or small items. On the basis of the sorting process is also the name can be explained because of the sorting process is reminiscent of the shaking of the array or a bartender.

Complexity

The algorithm has a square and therefore in comparison to many other sorting algorithms poor worst-case running time, but in the simple version at the same time also corresponds to the normal run time. In computer science, one expresses this by Landau symbol by. Therefore, this algorithm has the advantage of low memory requirements. Since the algorithm is an in -place method, it needs no extra memory. In addition Shakersort has almost sorted array is a linear runtime complexity ().

Formal algorithm

The algorithm looks in pseudocode as follows:

Procedure shakerSort (A: list of sortable items )    start: = -1    end: = length (A ) - 2    repeat      swapped: = false      start: = start 1      repeat for each i from beginning to end        when A [i ]> A [ i 1 ] then          Swap (A [i ], A ​​[i 1] )          swapped: = true        end if      end for      if reversed = false then        break from repeat - until loop      end if      swapped: = false      end: = end - 1      repeat for each i from end to beginning        when A [i ]> A [ i 1 ] then          Swap (A [i ], A ​​[i 1] )          swapped: = true        end if      end for    as long as reversed procedure end example

A set of six numbers to be sorted in ascending order. The bold number pairs are compared. If the right number here is smaller than the left, so the numbers are reversed ( blue).

55 07 78 12 42 33 1st run 07 55 78 12 42 33 07 55 78 12 42 33 07 55 12 78 42 33 07 55 12 42 78 33 07 55 12 42 33 78 2nd Pass 07 55 12 33 42 78 07 55 12 33 42 78 07 12 55 33 42 78 07 12 55 33 42 78 3 Pass 07 12 55 33 42 78 07 12 33 55 42 78 07 12 33 42 55 78 4 Pass 07 12 33 42 55 78 07 12 33 42 55 78 5th cycle 07 12 33 42 55 78 Finish sorted. Web Links

  • Visualization of Shakersort as a Java applet
  • Declaration of Shakersort algorithm
  • Http://www.sortieralgorithmen.de/shakersort/index.html
  • Sorting algorithm
Bidirectional (disambiguation)
195557
de