Shakersort

from Wikipedia, the free encyclopedia

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

principle

Animation of Shakersort, the red bar is shifted

The field to be sorted is passed through alternately up and down. Two neighboring elements are compared and exchanged if necessary.

Due to this bidirectionality , large or small elements can be deposited more quickly. The name can also be explained based on the sorting process, because the sorting process is reminiscent of shaking the array or a bartender.

complexity

The algorithm has a quadratic and therefore poor worst-case runtime compared to many other sorting algorithms , but in the simple version it also corresponds to the normal runtime. In computer science pressing it means Landau symbol by from. In return, this algorithm offers the advantage of a low memory requirement. Since the algorithm is an in-place process, it does not need any additional memory. In addition, Shakersort has a linear runtime complexity on almost sorted arrays ( ).

Formal algorithm

The algorithm looks like this in the pseudocode . The first element of the list of sortable elements Ahas the index 0: 

prozedur shakerSort( A : Liste sortierbarer Elemente )
  beginn := -1
  ende := Länge( A ) - 2
  wiederhole
    vertauscht := falsch
    beginn := beginn + 1
    für jedes i von beginn bis ende wiederhole
      falls A[ i ] > A[ i + 1 ] dann
        vertausche( A[ i ], A[ i + 1 ] )
        vertauscht := wahr
      ende falls
    ende für
    falls vertauscht = falsch dann
      brich wiederhole-solange-Schleife ab
    ende falls
    vertauscht := falsch
    ende := ende - 1
    für jedes i von ende bis beginn wiederhole
      falls A[ i ] > A[ i + 1 ] dann
        vertausche( A[ i ], A[ i + 1 ] )
        vertauscht := wahr
      ende falls
    ende für
  solange vertauscht
prozedur ende

example

A series of six numbers should be sorted in ascending order. The pairs of numbers marked in bold are compared. If the right number is smaller than the left, the numbers are swapped (marked in blue). 

55 07 78 12 42 33  1. Durchlauf
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  2. Durchlauf
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. Durchlauf
07 12 55 33 42 78
07 12 33 55 42 78
07 12 33 42 55 78  4. Durchlauf
07 12 33 42 55 78
07 12 33 42 55 78  5. Durchlauf
07 12 33 42 55 78  Fertig sortiert.

Web links