Cuprins:
1. Definirea sortarii prin insertie cu pas variabil.
2. Segventierea discrepantelor.
3. Algoritmul sortarii prin insertie cu pas variabil implementat in limbajul C.
4.Algoritmul sortarii prin insertie cu pas variabil implementat in limbajul Java.
1. Definirea sortarii prin insertie cu pas variabil. >>>
Sortarea prin insertie cu pas variabil este un algoritm de sortare, care in implementareqa originala necesita un numar de O(n2) comparatii si inlocuiri de elemente, in cazul in care algoritmul se comporta ineficient.O alternativa de algoritm de sortare prin insertie cu pas variabil a fost publicat in cartea lui V. Pratt, care avea o performanta in cazu in care se comporta ineficient definit prin relatia O(n log 2n).Acesta este un algoritm mai bun decat algoritmul a carui comportare ineficienta necesita un numar de O(n2) comparatii, insa mai putin parformant decat algoritmii de comparare care efectueaza un numar de O(n logn) comparatii pentru a realiza o sortare completa.Dealtfel, algoritmul de sortare prin insertie cu pas variabil este usor de depanat daca se doreste a se vedea cum functioneaza acest algoritm, insa este mai dificil sa se examineze timpul de executie al algoritmului.
Algoritmul de sortare prin insertie cu pas variabil este un algoritm care se desprinde din algoritmul de sortare prin insertie, insa aici trebuiesc facute doua observatii: 1. Sortarea prin insertie se comporta mai eficient daca datele de intreare (care terbuiesc sortate) sunt sortate in prealabil.
2. Sortarea prin insertie se comporta ineficient, comparativ cu sortarea prin insertie cu pas variabil, deaorece acest algoritm de sortare pozitioneaza numai cate un element la o perioada de timp.
Sortarea prin insertie cu pas variabil are un principiu de functionare asemanator cu sortarea prin insertie, deoarece elementele care se sorteaza sunt pozitionate in ordine diferita.Aceasta permita ca un element sa fie mutat printr-un "salt urias" la presupusa lui pozitie corecta.Astfel ca se efectueaza mai multe treceri de sortare asupra elementelor din tablou, in functie de numarul discrepantelor aflate intre elementele tabloului,care va fi din ce ince mai mic pana la sortarea finala.Ultima trecere de sortare efectuata de algoritmul sortarii prin inserie cu pas variabil este o sortare prin insertie plana, insa numai atunci, elementele din tabloul care trebuie sortat sunt sortate in intregime.
Presupunand ca un elementcu o valoare mica este stocat intr-o pozitie gresita la capatul tabloului care trebuie sortat.Folosind un algoritm care efectueaza un numar de On2) comparatii cum este algoritmul de sortare prin interclasare sau algoritmul de sortare prin insertie, se va executa un numar de n comparatii si interschimbari pentru a muta aceast element cu valoare mica, in toate modurile, catre un alt sfarsit de tablou.Sortarea prin insertie cu pas variabil va efectua salturi uriase pentru a pozitiona corect elementul cu valoare mica, astfel ca se vor realiza mai putine comparatii si mai putine interschimbari.
Un alt mod de a efectua o sortare prin insertie cu pas variabil este aceasta: se aranjeaza lista care trebuie sortata intr-un tablou, si apoi se va sorta tabloul (folosindu-se sortarea prin insertie).Se repeta acest proces, si de fiecare data se va descoperii un alt element cu valoare mica este descoperit in lungimea coloanei de numere.La sfarsit, tabloul devine o singura coloana.Transformarea listei initiale intr-un tablou este usor de urmarit, caci algoritmul se executa "pe loc" (prin incrementarea numarului de locatie printr-un pas care va avea un anumit numar de elemente care trebuiesc sortate, de exemplu folosind i+= pas in loc de i++).
De exemplu se considera o lista care contine numerele [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ].Daca se incepe cu un pas de 5, se poate vizulaiza caci acest pas va reprezenta un tablou care va avea 5 coloane:
Daca se sorteaza fiecare coloana, atunci se va optine:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
Daca se sorteaza fiecare coloana, atunci se va optine:
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
Aceastea se vor aranja intr-o singura lista de numere: [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].Astfel in urma sortarii a rezultat ca valoarea 10 care initial era la capatul listei, acum este pozitionata la inceput.Astfel ca lista obtinuta prin inlocuirea elementului cu valoaera 10 va efectua o sortare cu pas de 3, apoi inc-o o sortare cu pas de 1 (sortarea find algoritmul sortarii prin insertie).
Sortarea prin insertie cu pas variabil (shell sort) a fost denumita dupa iventatorul a acestei metode de sortare Donald Shell, care a publicat algoritmul "shell sort" in anul 1959.Unele manuale de algoritmi de sortare denumesc algoritmul de sortare prin insertie cu pas variabil ca si "metoda de sortare Shell-Metzner" dupa numele lui Donald Shell si Marlene Metzner Norton, caci acest tip de sortare i-a fost dedicat lui Metzner, care a replicat ca "eu nu am contribuit cu nimic la acest algoritm de sortare, si prefer ca numele meu sa nu mai fie atasat pe langa a lui Shell".
2. Segventierea discrepantelor. >>>
Tablou initial | 32 95 16 82 24 66 35 19 75 54 40 43 93 68 | Numar inlocuiri |
|
Sortare pas 5 | 32 35 16 68 24 40 43 19 75 54 66 95 93 82 | 11 inlocuiri |
Sortare pas 3 | 32 19 16 43 24 40 54 35 75 68 66 95 93 82 | 12 inlocuiri |
Sortare pas 1 | 16 19 24 32 35 40 43 54 66 68 75 82 93 95 | 15 inlocuiri |
Segventierea discrepantelor (diferentele dintre pozitiile corecte ale elementelor ce trebuiesc sortate si pozitia curenta) este o parte integrala a algoritmului de sortare prin insertie cu pas variabil.Orice segventa de incrementare este admisa, ea va fi mai lunga daca ultimul element care tebuie sortat este 1.Algoritmul de sortare prin insertie cu pas variabil incepe sortarea prin a realiza o sortare a discrepantelor , prin a elimina discrepanta primului element.Astfel se va proceda pentru fiecare element aflat in segventa pana cand se ajunge la ultimul element avand astfel o singura discrepanta de elimiat.Cand s-a ajuns sa se aiba o singura discrepanta.Astfel cand s-a ajuns la o singura discrepanta, ea se va elimina prin inserarea acestui element la locul potrivit anuland astfel discrepanta, folosindu-se algoritmul de sortare prin insertie, garantand in final ca lista este sortata.
Segventierea discrepantelor a fost initial propusa de Donald Shell, care implica impartirea listei de elemente care trebuiesc sortate in doua (N/2), si se continua acest proces pana cand se ajunge la un singur element.Atat timp cat acest concept realizeaza o performanta buna in cadrul algoritmulor de gradul 2 cum este de exemplu sortarea prin insertie, performanta se poate anula daca algoritmul se comporta multumitor sau ineficient.Manualele lui Weiss demonstreaza ca aceasta segventa a discrepantelor poate ajunge sa efectueze in cazul in care se conporta ineficient un numar de O(n2) sortari, daca datele initiale isi au pozitiile in tablou dupa forma (valoare_mica1, valoare_mare1, valoare_mica2, valoare_mare2, ...).Daca numerele initiale sunt sortate, atunci pozitial elementelor dupa procedeul de sortare va fi identica cu pozitia avuta inaintea sortarii, deoarece elementele sunt sortate, si astfel n-a avut loc nici o interschimbare de locatii.
Sortarea prin insertie cu pas variabil care depinde de sortarea prin segventa discrepantelor pentru o lista de k discrepante, realizeaza un numar de O(n2) comparatii daca se comporta ineficient (folosiind conceptul lui Shell care presupune ca sortarea prin insertie cu pas variabil va incepe de la jumatatea tabloului initial, si apoi se continua astfel aceasta divizare la 2), sau O(n3/2)-daca se utilizeaza conceptul lui Hibbard care incrementeaza discrepantele dupa realatia 2k - sau O(n4/3) - daca se utilizeaza conceptul lui Sedgewick, care incerementeaza discrepantele dupa realatia 9(4i)-9(2i)+1, sau 4i+1+3(2i)+1) sau O(n log2n).
Algoritmul sortarii prin insertie cu pas variabil implementat in limbajul C >>>
Sortarea prin insertie cu pas variabil este o metoda de sortare utilizata fregvent in cadrul limbajelor de programare.In acest paragraf este prezentata o metoda de sortare "shell sort" cu algoritmul implementat in limbaul C care sorteaza un tablou de numere intregi.Daca algoritmul nu se comporta eficient atunci el va realiza un numar de O(n2) comparatii.
#include
#include
void shell_sort(int a[], int lungime_tablou)
{int i, j, incrementari, temp;
incrementari = lungime_tablou/2;
while (incrementari > 0)
{for (i=incrementari; i < lungime_tablou; i++)
{j = i;
temp = a[i];
while ((j >= incrementari) && (a[j-incrementari] > temp))
{a[j] = a[j - incrementari];
j = j - incrementari; }
a[j] = temp; }
incrementari /= 2; }
printf("Sortarea prin insertie cu pas variabil:\n"); }
int main()
{int i;
int a1[]={1,11,2,22,3,33,4,44,5,55,6,66}; //tabloul initial
int a[]={1,11,2,22,3,33,4,44,5,55,6,66}; //tabloul care se sorteaza
shell_sort(a,sizeof(a)/sizeof(*a)); //sizeof(a)/sizeof(*a) este lungime_tablou
printf("Tabloul initial este: ");
for(i=0;i{printf("\nTabloul sortat este: ");
for(i=0;i{} }
Daca se ruleaza exemplul de mai sus, atunci pe ecran va aparea: Sortarea prin insertie cu pas variabil:
Tabloul initial este: 1 11 2 22 3 33 4 44 5 55 6 66
Tabloul sortat este: 1 2 3 4 5 6 11 22 33 44 55 66
4. Algoritmul sortarii prin insertie cu pas variabil implementat in limbajul Java >>>
Algoritmul sortarii prin insertie cu pas variabil este urmatorul:
//Prgramul demonstreza sortarea
// prin insertie cu pas variabil
//-shell sort implementat in java
class TablouSh
{ private long[] Tablou; // referinta catre tabloul "Tablou"
private int nElemente; // numarul elementelor de date
public TablouSh(int max) //acesta este constructorul
{Tablou = new long[max]; // se creaza tabloul
nElemente = 0;// sa nu mai fie nici un element }
public void insereaza(long valoare) // se pun elementele in tablou
{Tablou[nElemente] = valoare; //se insereaza elementele
nElemente++; //se incrementeza dimensiunea tabloului }
public void afiseaza() //se afiseaza pe ecran continutul tabloului
{System.out.print("A=");
for(int j=0; jSystem.out.print(Tablou[j] + " "); //se afiseaza valoarea lui "j"
System.out.println(""); //se afiseaza rand liber pe ecran }
public void sortareShell()
{int a, b;
long temp;
int h = 1; //se cauta valoarea initiala a lui "h"
while(h <= nElemente/3)
h = h*3 + 1; //(1, 4, 13, 40, 121, ...)while(h>0) //se decrementeaza valoarea lui "h" pana cand devine 1
{for(b=h; b{temp = Tablou[b];
a = b;
//o trecere (ex: 0, 4, 8)
while(a > h-1 && Tablou[a-h] >= temp)
{
Tablou[a] = Tablou[a-h];
a -= h;
}
Tablou[a] = temp; } //se termina instructiunea "for"
h = (h-1) / 3; //se decrementeaza h } //se incheie instructiunea "while(h>0)" } //se incheie prodedura sortareShell() } //se termina clasa TablouSh
class SortareShellApp
{public static void main(String[] args)
{int maxDim = 10; //tabloul va putea avea maxim 10 elemente
TablouSh tab;
tab = new Tablou(maxDim); //se creaza tabloul
for(int j=0; j{long n = (int)(java.lang.Math.random()*99);
tab.insert(n); }
tab.afiseaza(); //se afiseaa tabloul nesortat
tab.sortareShell(); //se sorteaza tabloul
tab.afiseaza(); //se afiseaza tabloul care s-a sortat } //se incheie functia main() } //se incheie clasa SortareShellApp |