ShellSort

[•raduionut13]

Salut !
As dori daca puteti sa imi dati un algoritm de shellsort , dar care sa semene cat mai multe cu bubblesort . Stiam ceva cu increment dar numai tin minte .

[•Owlree]

Ideea de la Shell sort este că am putea sorta ceva mai rapid dacă am sorta mai întâi elementele mai depărtate.

De exemplu, ca să sortăm toate elementele de distanță 4, trebuie să sortăm separat cele 4 liste formate din

• primul element, al 5-lea, al 9-lea, ș.a.m.d
• al 2-lea element, al 6-lea, al 10-lea, ș.a.m.d
• al 3-lea element, al 7-lea, al 11-lea, ș.a.m.d
• al 4-lea element, al 8-lea, al 12-lea, ș.a.m.d.

Acum lista noastră cea mare (care conține exact cele 4 subliste de mai sus) are proprietatea că de oriunde plecăm, să zicem că de la al i-lea element, elementele de forma i+4k, unde k este număr natural, sunt mai mari sau egale cu elementul inițial, iar cele de forma i-4k, unde k este număr natural, sunt mai mici sau egale cu elementul inițial.

În general, ca să sortăm toate elementele de distanță k, vom împărți lista în următoarele subliste:

• 1, 1+k, 1+2k, 1+3k, 1+4k, ș.a.m.d.
• 2, 2+k, 2+2k, 2+3k, 2+4k, ș.a.m.d.
• ...
• k-1, (k-1)+k, (k-1)+2k, (k-1)+3k, (k-1)+4k, ș.a.m.d.
• k, k+k, k+2k, k+3k, k+4k, ș.a.m.d.

Obținând în total k subliste.

Acum Donald Shell în lucrarea lui (1959) n-a zis exact asta, dar metoda din spatele Shell sort este modulară, în sensul că putem folosi ce algoritm vrem pentru sortarea sublistelor și ce dimensiuni pentru distanțe vrem (atâta timp când ultima este 1).

Dacă am înțeles eu bine, întrebarea ta este cum am putea folosi bubble sort în Shell sort. Ideea este următoarea - dacă avem o listă de elemente de lungime n, vom sorta prima dată toate elementele la distanță n/2 între ele (cum am zis mai sus), apoi cele la distanță n/4, n/8, ș.a.m.d. Această alegere este arbitrară, este una populară totuși, este chiar cea folosită de Donald Shell în articolul original. Cu toate astea, puteam face o cu totul altă alegere, puteam sorta toate elementele la distană n-1, apoi n-2, n-3, etc. Bubble sort în viața de zi cu zi trece direct la sortarea elementelor la distanță 1. Oricum, deci am ales lista de distanțe {n/2, n/4, n/8, ... }. Din prima distanță, vom obține n/2 subliste, după metoda descrisă mai sus. Sortăm toate aceste subliste folosind bubble sort după care luăm următoarea distanță, n/4, din care vom obține n/4 subliste - procedăm analog, și procedăm analog pentru toate distanțele rămase.

Cred că ar trebui să specific că toate sortările se întâmplă pe loc, adică atunci când spunem că sortăm o sublistă sortăm sublista chiar în lista cea mare.

Pentru un exemplu de implementare, poți consulta sursa asta.