ShellSort

Sortarea prin micşorarea incrementului ShellSort

Informaţii generale:

Această metodă de sortare îşi propune să îmbunătăţească algoritmul sortării prin inserare directă, InsertSort: elementele sunt aşezate pe rând în poziţia lor finală, pentru aşezarea fiecărui element x[i], acesta se va compara cu elementele deja ordonate aflate pe poziţiile de la 1 la i-1, în momentul în care se descoperă primul element mai mare decât x[i], subşirul ce îi urmează lui, până la elementul de pe poziţia i-1, se deplasează cu o poziţie la dreapta, iar elementul x[i] este aşezat pe locul rămas liber între cele două subşiruri ordonate, în poziţia sa finală.

Dacă avem un algoritm de sortare care deplasează elementele doar cu câte o poziţie o dată, timpul lui mediu va fi proporţional cu n², deoarece fiecare element se deplasează în medie cu n/3 poziţii. Din acest motiv s-au căutat metode care să îmbunătaţească inserţia directă, prin mecanisme cu ajutorul cărora elementele fac salturi mai lungi în locul paşilor mici. O asemenea metodă a fost propusă în 1959 de Donald L. Shell, metodă numită şi sortare cu micşorarea incrementului.

Prezentarea algoritmului:

Sortarea se face asupra unor subsecvenţe de elemente care devin din ce în ce mai mari până la dimensiunea n. Fiecare subsecvenţă i este determinată de un h_i numit increment. Incremenţii satisfac condiţia: h_t > h_t₋₁> · · · > h₂ > h₁, iar ultimul increment este întotdeauna egal cu 1.

Pentru fiecare increment h_i = h, se sortează elementele aflate la distanţă h în vector. Deci avem următoarele subsecvenţe de sortat:

x[1], x[1 + h], x[1 + 2h], ..., x[1 + kh]

x[2], x[2 + h], x[2 + 2h], ...

x[h], x[h + h], x[h + 2h], ...

Exemplu:

h=4

2 13 7 8 3 12 9 4 12

compar 2, 3,12 care sunt în ordinea dorită, deci nu apar interschimbări;
compar 13, 12 care se interschimbă;
compar 7, 9 care sunt în ordine;
compar 8, 4 care se interschimbă.

h=3

2 12 7 4 3 13 9 8 12

compar 2, 4,9 care sunt în ordinea dorită, deci nu apar interschimbări;
compar 12, 3 care se interschimbă, apoi 12, 8 care se interschimbă;
compar 7, 13 care sunt în ordine.

h=1

2 3 7 4 8 12 9 12 13

compar 2, 3 care sunt în ordinea dorită, deci nu apar interschimbări;
compar 3, 7 care sunt în ordine;
compar 7, 4 care se interschimbă;
compar 7, 8 care sunt în ordine;
compar 8,12 care sunt în ordine;
compar 12, 9 care se interschimbă;
compar 12, 12 care sunt în ordine;
compar 12, 13 care sunt în ordine.

va rezulta şirul:

2 3 4 7 8 9 12 12 13

Parcurgând acelaşi exemplu, dar cu alţi incremenţi (5>4>2>1), se va obţine acelaşi rezultat.

Unele şiruri de incremenţi sunt mai bune decât altele. Alegerea bună va creşte eficienţa algoritmului.

Presupunem că numărul incremenţilor este memorat de variabila nincr şi că valorile acestora sunt memorate în tabloul kval[h], 1≤h≤nincr.

Varianta pseudocod a algoritmului:

pentru s←t,1,-1 execută

pas←h[s];

pentru i←1,n,pas execută

j←0;

cât timp i+j+pas≤n şi j≤pas execută

dacă x[i+j]>x[i+j+pas] atunci

aux←x[i+j];x[i+j]←x[i+j+pas];x[i+j+pas]←aux;

sfârşit dacă;

j←j+1;

sfârşit cât timp;

sfârşit pentru;

Operaţia de sortare corespunzătoare incrementului h se numeşte h–sortare.

Pentru analiza eficienţei algoritmului, se poate demonstra, conform cercetărilor lui D. E. Knuth, următorul rezultat:

1. Dacă secvenţa de incremente h_t,...,h₁ satisface condiţia h_s+1mod h_s=0 pentru 1≤s<t, atunci timpul de execuţie pentru cazul cel mai nefavorabil este O( n²).

2. Timpul de execuţie în cazul cel mai nefavorabil pentru algoritmul ShellSort este , când h_s=2^s-1, 1≤s≤t, t=[log₂n]-1.

În consecinţă, Shell Sort este un algoritm foarte similar cu Insertion Sort, dar care foloseşte paşi mai mari decât unitatea pentru rearanjarea valorilor vectorului. Dimensiunea pasului scade de la o iteraţie la alta, iar în final algoritmul va efectua o sortare clasică prin inserţie, dar aplicată asupra unor valori aproape ordonate. Astfel, dacă o valoare mică este poziţionată către sfârşitul vectorului, algoritmul InsertSort va avea nevoie de aproximativ n comparaţii şi interschimbări pentru a muta elementul respectiv pe poziţia corectă. Folosind însă ShellSort, datorită faptului că algoritmul foloseşte paşi de dimensiune mai mare, valoarea respectivă va fi adusă pe poziţia corespunzătoare într-un număr mult mai mic de paşi.

Corectitudinea algoritmului este garantată de faptul că la ultimul pas se realizează o sortare clasică a întregului vector prin metoda inserţiei. Dar, datorită faptului că datele sunt deja parţial ordonate, sortarea prin metoda inserţiei la ultima trecere va avea nevoie de doar câteva iteraţii pentru a finaliza ordonarea elementelor vectorului.

Dimensiunea seturilor de date folosite la fiecare pas al algoritmului are un impact major asupra eficienţei cu care se realizează operaţia de ordonare. Se recomandă ca valorile incrementului să fie numere prime între ele.

Algoritmul Shell Sort este de departe cel mai rapid algoritm din clasa celor de complexitate egală cu O(n²). Astfel, viteza algoritmului este de aproximativ cinci ori mai mare faţă de sortarea prin metoda bulelor şi de peste două ori mai mare în comparaţie cu metoda de sortare prin inserţie. Cu toate că algoritmul este mai lent în comparaţie cu alte metode de sortare (cum ar fi, de exemplu, QuickSort, MergeSort sau HeapSort), simplitatea acestuia îl face să fie o foarte bună alegere pentru cazurile în care se doreşte sortarea repetată a unor liste de dimensiune moderată (mai puţin de 5000 elemente).

Implementare C++:

for(s=t;t>=1;t--)

{pas=h[s];

for(i=1;i<=n;i+pas)

{ j=0;

while(i+j+pas<=n && j<=pas)

{if (x[i+j]>x[i+j+pas]) {

aux= x[i+j]; x[i+j]=x[i+j+pas]; x[i+j+pas]=aux;}

j=j+1;

}

Implementare Pascal:

for s:=t downto 1 do begin

pas:=h[s];

for i:=1 to n step pas do

begin

j:=0;

while (i+j+pas<=n) and (j<=pas) do

begin

if x[i+j]>x[i+j+pas] then begin

aux:= x[i+j];x[i+j]:=x[i+j+pas];x[i+j+pas]:=aux;

end;

j:=j+1;

end;

Mergi la pagina METODE DE SORTARE

Aplicatii

Aplicaţie1: În fişierul sărituri.in sunt notate numele, prenumele şi lungimea săriturii pentru cei n elevi dintr-o clasă. Să se construiască un fişier text ordcresc.out, încare se scriu elevii ordonaţi după lungimea săriturii.

Program C++:

#include <fstream.h>

struct elev { char nume[20], prenume[20];

float lung; }

elev a[30]; int i,t,n;

ifstream f(“sarituri.in”);

ofstream g (“ordcresc.out”);

int h(int s){

int i,p=2;

for (i=2; i<=s; i++) p*=2;

return p-1}

void shellsort(elev a[30], int t ){

int s, pas, i, j; elev aux;

for(s=t;t>=1;t--)

{pas=h(s);

for(i=1;i<=n;i+pas)

{ j=0;

while(i+j+pas<=n && j<=pas)

{if (a[i+j].lung>a[i+j+pas].lung) {

aux=a[i+j;a[i+j]=a[i+j+pas];

a[i+j+pas]=aux;}

j=j+1;

}

} }

void main(){

f>>n;

for (i=1; i<=n; i++)

f>>a[i].nume>>a[i].prenume>>a[i].lung;

t=4;

shellsort(a,t);

for (i=1; i<=n; i++)

g<< a[i].nume<<a[i].prenume<< a[i].lung<<” ”;

f.close();

g.close(); }

Program Pascal:

PROGRAM ShellSort1;

TYPE elev=RECORD

nume, prenume: STRING[20];

lung: REAL; END;

vector=ARRAY[1..30] OF elev;

VAR a:vector; i,t,n:INTEGER; f,g:TEXT;

FUNCTION h(s:INTEGER):INTEGER;

VAR i,p:INTEGER;

BEGIN

p:=2;

FOR i:=2 TO s DO p:=2*p;

h:=p-1; END;

PROCEDURE ShellSort(VAR a:vector, t:INTEGER);

VAR s,i,j,pas: INTEGER; aux:elev;

BEGIN

FOR s:=t DOWNTO 1 DO BEGIN

pas:=h(s);

FOR i:=1 TO n STEP pas DO

BEGIN

j:=0;

WHILE (i+j+pas<=n) AND (j<=pas) DO

BEGIN

IF a[i+j].lung>a[i+j+pas].lung THEN BEGIN

aux:=a[i+j];a[i+j]:=a[i+j+pas];

a[i+j+pas]:=aux;END;

j:=j+1;

END;

END; END;

BEGIN

ASSIGN (f, ’sarituri.in’);

ASSIGN (g, ’ordcresc.out’);

RESET(f);READ(f,n);

FOR i:=1 TO n DO

READ (f, a[i].nume, a[i].prenume, a[i].lung);

t:=4;

ShellSort (a,t);

REWRITE (g);

FOR i:=1 TO n DO

WRITE (g, a[i].nume, a[i].prenume, a[i].lung, ’ ’);

CLOSE(f); CLOSE(g); END.

Mergi la pagina METODE DE SORTARE