ShakerSort

ShakerSort je sortirni algoritem.

Je zgolj nadgrajena oblika algoritma za navadne zamenjave, ker združuje obe smeri sortiranja le-tega.

Sprememba postopka

Menjavamo smer prehodov:

• pregledovanje od leve proti desni prestavi na pravo mesto max element
• pregledovanje od desne proti levi pripelje na pravo mesto min element
• neurejen del na sredini tabele se oži z obeh strani

Primer sortiranja

l

leva meja

r

desna meja

6 5 1 4 2 3 9 1
  l           r    <--  (premikamo v levo)
              m
1 6 5 1 4 2 3 9
    l         r    -->  (premikamo v desno)
1|5 1 4 2 3|6 9       ker ni prišlo do zamenjave se r pomakne nazaj (ker je del že urejen)
    l     r
1 1|5 2 4 3|6 9    <--
      l   r
1 1|2 4 3|5 6 9    -->
      l r
1 1 2 3 4 5 6 9    <--
        r l
1 1 2 3 4 5 6 9

podrobnejši primer enega potovanja

2 3 4 5 6 7 1
1|2 3 4 5 6 7
1 2 3 4 5 6 7

7 1 2 3 4 5 6
1 7 2 3 4 5 6
1 2 7 3 4 5 6
1 2 3 7 4 5 6
1 2 3 4 7 5 6
1 2 3 4 5 7 6
1 2 3 4 5 6 7

Algoritem v javi

public static void shakersort(Element[] a,int atr) //sortiranje s tresenjem manjsi
  {
    int j,m,l,r;
    Element x;
    l=1; r=a.length-1; m=r;
    do
    {
      for (j=r; j>=l; --j)
        if (a[j].manjsi(a[j-1],atr))
        {
          x=a[j];
          a[j]=a[j-1];
          a[j-1]=x;
          m=j;
        }
      l=++m;
      a[0].izpisiTabelo(a,atr);
 
      if (j<=r)
      {
      for (j=l; j<=r; ++j)
        if (a[j].manjsi(a[j-1],atr))
        {
          x=a[j];
          a[j]=a[j-1];
          a[j-1]=x;
          m=j;
        }
      r=--m;
      a[0].izpisiTabelo(a,atr);
      }
    } while (l<=r);
  }

Povezave

• Shaker Sort