ShakerSort

Sortarea prin metoda ShakerSort (CocktailSort)

Informaţii generale:

Această metodă de sortare este o îmbunătăţire a sortării prin metoda bulelor, prezentată anterior. În metoda bulelor, se repetă parcurgerea totală a şirului de sortat, atât timp cât sunt în vector elemente vecine, “bule”, care nu sunt în poziţia dorită. Acolo unde sunt identificate bule, elementele se interschimbă. Reluarea parcurgerii se opreşte când la ultima parcurgere nu se mai întâlnesc bule. Pentru a marca dacă într-o parcurgere mai sunt bule, se foloseşte o variabilă ce poate avea două stări.

Prezentarea algoritmului:

Pentru ordonare crescătoare, la metoda bulelor, se observă că la fiecare parcurgere, elementele mari se deplasează spre sfârşitul vectorului, astfel încât nu ar mai fi necesar să fie parcurse aceste elemente. Se foloseşte o variabilă nouă, dr, care va memora indicele ultimei valori care a făcut parte dintr-o bulă, următoarea parcurgere realizându-se până la acel indice. Apoi, se va face o parcurgere de la dreapta la stânga, reţinându-se într-o altă variabilă poziţia inferioară, st, din care va porni următoarea parcurgere, deoarece şi către început se deplasează în ordine elementele mici.

K.E. Inverson a făcut următoarea observaţie: dacă j este un indice astfel încât x[j] şi x[j+1] nu sunt interschimbate în două treceri consecutive, în direcţii opuse, atunci x[j] şi x[j+1] sunt în poziţiile lor finale, nefiind necesar să mai fie ulterior parcurse.

Deci, vectorul se parcurge în ambele sensuri, ducând prin fiecare parcurgere elementele mari, respectiv mici spre capete. Algoritmul se opreşte când cele două variabile, st şi dr, indică acelaşi element (se întâlnesc) sau la ultima parcurgere nu s-au mai făcut interschimbări (t=0).

Exemplu: Fie şirul 128, 77, 905, 403, 372, 478, 553, 348, 237, 878

i	1	2	3	4	5	6	7	8	9	10
x[i]	128	77	905	403	372	478	553	348	237	878

→ st=1 dr=10

i	1	2	3	4	5	6	7	8	9	10
x[i]	77	128	403	372	478	553	348	237	878	905

st=1 dr=9 ←

i	1	2	3	4	5	6	7	8	9	10
x[i]	77	128	237	403	372	478	553	348	878	905

→ st=4 dr=9

i	1	2	3	4	5	6	7	8	9	10
x[i]	77	128	237	372	403	478	348	553	878	905

st=4 dr=7 ←

i	1	2	3	4	5	6	7	8	9	10
x[i]	77	128	237	348	372	403	478	553	878	905

→ st=5 dr=7

i	1	2	3	4	5	6	7	8	9	10
x[i]	77	128	237	348	372	403	478	553	878	905

t=0 st=5 dr=7

Varianta pseudocod a algoritmului:

st←1;

dr←n;

repetă

t←0;

pentru i = st, dr-1 execută

dacă x[i]>x[i+1] atunci

interschimb (x[i], x[i+1]);

t←i;

sfârşit dacă;

sfârşit pentru;

dacă t≠0 atunci

dr←t;

t←0;

pentru i=dr, st+1, -1 execută

dacă x[i] <x[i-1] atunci

interschimb( x[i], x[i-1])

t←i;

sfârşit dacă;

st←t;

sfârşit dacă;

până când t=0 sau st=dr;

Prin metoda ShakerSort se îmbunătăţeşte perfomanţa sortării cu bule. Prin treceri alternate în direcţii opuse, numărul mediu de comparaţii este uşor redus, însă algoritmul nu se îmbunătăţeşte în aşa fel încât să devină mai eficient nici faţă de inserţia directă, InsertSort. Algoritmul rămâne în categoria ordinul O(n²).

Implementare C++:

void shaker ()

{ int i, st, dr, t, aux;

st=1;

dr=n;

{t=0;

for (i=st; i<=dr-1; i++)

if (x[i]>x[i+1])

{aux=x[i];

x[i]=x[i+1];

x[i+1]=aux;

t=i; }

if (t!=0)

{dr=t;

t=0;

for (i=dr; i>=st+1; i--)

if (x[i]<x[i+1])

{aux=x[i];

x[i]=x[i+1];

x[i+1]=aux;

t=i; }}

st=t;}

}

while (t!=0 && st !=dr) ;

}

Implementare Pascal:

procedure shaker ;

var i, st, dr, t, aux:integer;

begin

st:=1;

dr:=n;

repeat

t:=0;

for i:=st to dr-1 do

if x[i]>x[i+1] then

begin

aux:=x[i];

x[i]:=x[i+1];

x[i+1]:=aux;

t:=i;

end

if t<>0 then

begin

dr:=t;

t:=0;

for i=dr downto st+1 do

if x[i]<x[i+1] then

begin

aux=x[i];

x[i]=x[i+1];

x[i+1]=aux;

t=i;

end;

st:=t;

until (t=0) or (st =dr) ;

end;

Mergi la pagina METODE DE SORTARE

Aplicaţii

Aplicaţie1: Să se scrie o funcţie de ordonare care primeşte 3 parametri: un vector x cu maxim 100 de elemente numere întregi, n reprezentând numărul de elemente şi numărul k mai mic decât n.Funcţia ordonează crescător primele k elemente şi descrescător celelalte n-k.

Program C++:

#include <iostream.h>

#include <conio.h>

int x[100], i, n, k;

void shakersort (int x[100], int n, int k){

int i, st, dr, t, aux;

st=1;dr=k;

do{t=0;

for (i=st; i<=dr-1; i++)

if (x[i]>x[i+1])

{aux=x[i];x[i]=x[i+1];

x[i+1]=aux;t=i; }

if (t!=0){dr=t;t=0;

for (i=dr; i>=st+1; i--)

if (x[i]<x[i+1]){

aux=x[i];x[i]=x[i+1];

x[i+1]=aux;t=i; }}

st=t;}}

while (t!=0 && st !=dr) ;

st=k+1;dr=n;

do{t=0;

for (i=st; i<=dr-1; i++)

if (x[i]<x[i+1]){

aux=x[i];x[i]=x[i+1];

x[i+1]=aux;t=i; }

if (t!=0){dr=t;t=0;

for (i=dr; i>=st+1; i--)

if (x[i]>x[i+1]){

aux=x[i];x[i]=x[i+1];

x[i+1]=aux;t=i; }}

st=t;}}

while (t!=0 && st !=dr) ;}

void main(){

cin>>n>>k;

for(i=1;i<=n;i++) cin>>x[i];

shakersort(x, n, k);

for(i=1;i<=n;i++) cout<<x[i]<<” ”;}

Program Pascal :

PROGRAM ShakerSort1;

TYPE vector=ARRAY[1..100] OF INTEGER;

VAR x:vector; i,n,k:INTEGER;

PROCEDURE ShakerSort(VAR x:vector; n,k:INTEGER);

VAR i, st, dr, t, aux:INTEGER;

BEGIN

st:=1;dr:=k;

REPEAT

t:=0;

FOR i:=st TO dr-1 DO

IF x[i]>x[i+1] THEN

BEGIN

aux:=x[i];x[i]:=x[i+1];

x[i+1]:=aux;t:=i; END

IF t<>0 THEN

BEGIN

dr:=t; t:=0;

FOR i=dr DOWNTO st+1 DO

IF x[i]<x[i+1] THEN BEGIN

aux=x[i];x[i]=x[i+1];

x[i+1]=aux;t=i;END;

END;

st:=t;

UNTIL (t=0) OR (st =dr) ;

st:=k+1;dr:=n;

REPEAT

t:=0;

FOR i:=st TO dr-1 DO

IF x[i]<x[i+1] THEN

BEGIN

aux:=x[i];x[i]:=x[i+1];

x[i+1]:=aux;t:=i; END

IF t<>0 THEN

BEGIN

dr:=t; t:=0;

FOR i=dr DOWNTO st+1 DO

IF x[i]>x[i+1] THEN BEGIN

aux=x[i];x[i]=x[i+1];

x[i+1]=aux;t=i;END;

END;

st:=t;

UNTIL (t=0) OR (st =dr) ;

END;

BEGIN

READLN(n,k);

FOR i:=1 TO n DO READLN(x[i]);

ShakerSort (x, n, k);

FOR i:=1 TO n DO WRITE(x[i], ’ ’);

END.

Mergi la pagina METODE DE SORTARE