Unelte utilizator

Unelte site


laboratoare:laborator-09

Aceasta e o versiune anterioară a paginii.


Laborator 09: Algoritmi de sortare 2


1 Obiectivele laboratorului

Propunem studierea următorilor algoritmi de sortare:

  • Shell Sort
  • Heap Sort
  • Radix Sort
  • qsort şi sort

Propunem studierea următoarelor structuri auxiliare:

  • Heap-uri (pentru Heap Sort)
  • vector de sectoare - bucket-uri (pentru Radix Sort)
  • operaţii pe biţi
  • Pachetul STL → <algorithm>

2. Introducere

2.1 Heap-uri

2.2 Bucket-uri

2.3 Bit Shift

Menţionăm următoarele operaţii pe biţi ce se pot folosi în C/C++ :

Operaţii logice

  • & şi pe biţi(bitwise AND)
  • | sau pe biţi(bitwise OR)
  • ^ sau exclusiv pe biţi(bitwise XOR)
  • ~ complement pe biţi(bitwise NOT)

Deplasări

  • » la dreapta(right shift)
  • « la stânga(left shift)

Descriem numai operaţiile pe care le vom folosi în cadrul exemplului de mai jos: » şi &.

  • Operaţia n » k are ca rezultat valoarea obţinută prin mutarea la dreapta a tuturor biţilor lui n(pe primii k biţi se obţine 0, iar ultimii k biţi din n sunt ignoraţi).
  • Operaţia n & k are ca rezultat valoarea obţinută prin păstrarea biţilor nenuli din n pentru poziţiile pe care şi k are biţi nenuli(0 în rest)
Dacă n este număr natural şi k = 2p, atunci:
  • n » p == n / k
  • n & (k - 1) == n % k

Apar diferenţe în cazul numerelor negative.

3. Algoritmii

3.1 Shell Sort

  • timp mediu : O(N * log2 N)
  • timp la limită : O(N * log2 N)
  • memorie : O(1)
  • Stabil : NU

Descriere :

Algoritmul shell sort este o generalizare a algoritmului insertion sort.

  • La algoritmul insertion sort, pentru a insera un nou element în lista de elemente deja sortate, se deplasează fiecare element cu câte o poziţie spre dreapta atât timp cât avem elemente mai mari decât el. Practic, fiecare element înaintează spre poziţia sa finală cu câte o poziţie.
  • Algoritmul shell sort lucrează similar, doar că deplasează elementele spre poziţia finală cu mai mult de o poziţie. Se lucrează în iteraţii.
  • În prima iteraţie se aplică un insertion sort cu salt s1 mai mare decât 1. Asta înseamnă că fiecare element din şirul iniţial este deplasat spre stânga cu câte s1 poziţii atât timp cât întâlneste elemente mai mari decât el.
  • Se repetă asemenea iteraţii cu salturi din ce în ce mai mici s2, s3, s4, etc. Ultima iteraţie se face cu saltul 1. Această ultimă iteraţie este practic un insetion sort clasic.
  • Principiul este că, după fiecare iteraţie, sirul devine din ce în ce “mai sortat”. Iar, cum algoritmul insertion sort funcţionează cu atât mai repede cu cât sirul este mai sortat, per ansamblu vom obţine o îmbunătăţire de viteză.

Implementare :

void shellSort(int a[],int n)
{
    int i, j, k, h, v;
    int cols[] = {1391376, 463792, 198768, 86961, 33936, 13776, 4592,
    1968, 861, 336, 112, 48, 21, 7, 3, 1};
    for (k = 0; k < 16; k++) //parcurgem fiecare limita
    {
        h = cols[k]; //h = saltul
        for (i = h; i < n; i++) //insertion sort
        {
            v = a[i];
            j = i;
            while (j >= h && a[j-h] > v) //crescator
            {
                a[j] = a[j-h];
                j = j - h;
            }
            a[j] = v;
        }
    }
}
Există mai multe variante propuse pentru vectorul cu salturi, iar complexitatea de timp diferă în funcţie de varianta aleasă. În general, complexitatea de timp asociată algoritmului Shell sort este O(N * log^2 N) şi o variantă destul de cunoscută cu această complexitate foloseşte vectorul obţinut din elementele mai mici decât N ale mulţimii A, puse în ordine descrescatoare, unde A = { x = (2^p)*(3^q) / oricare ar fi p şi q naturale}

3.2 Heap Sort

  • timp mediu: O(N log N)
  • timp la limită: O(N log N)
  • memorie: O(1)
  • Stabil: NU

Descriere :

  • Metoda de sortare prin selecţie directă se bazează pe selecţia repetată a ultimei chei dintre n elemente, apoi dintre n-1 elemente rămase, etc.
  • Pentru a găsi cea mai mică cheie dintre n elemente sunt necesare n-1 comparaţii, apoi găsirea următoarei dintre n-1 elemente are nevoie de n-2 comparaţii, etc. ⇒ n(n-1)/2 comparaţii.
  • Această sortare se poate îmbunătăţi prin reţinerea, de la fiecare scanare, de mai multă informaţie decât identificarea unui singur element, cel mai mic.
  • De exemplu, cu n/2 comparaţii se poate determina cheia mai mică pentru fiecare pereche de elemente dintre cele n elemente, apoi cu alte n/4 comparaţii se poate determina cheia cea mai mică pentru fiecare pereche ale cheilor determinate anterior, şi aşa mai departe. Astfel, cu n-1 comparaţii se poate construi arborele de selecţie.
  • Exemplul ne dă o idee despre cum este implementată funcţia make_heap

Implementare :

#include <algorithm>
void heapSort(int a[], int n) //fara vector din STL
{
    make_heap(a,a + n);
    sort_heap(a,a + n);
}
#include <algorithm>
#include <vector>
using namespace std;
void heapSort(int a[],int n) //cu vector din STL
{
    int i;
    vector<int> v; //puteam declara vector<int> v(a,a +n)
    for(int i = 0;i < n;i++) { //si am fi putut sari peste
        v.push_back(a[i]); //copierea element cu element
    }
    make_heap(v.begin(),v.end());
    sort_heap(v.begin(),v.end());
    for(int i = 0;i < n;i++) {
        a[i] = v[i];
    }
}

3.3 Radix Sort

  • timp mediu: O(N * k)
  • timp la limită: O(N * k)
  • memorie: O(N + k)
  • Stabil: DA

k = lungimea cuvântului/cheii(word size)

Vom prezenta varianta LSD(Least Signifiant Digit) a algoritmului de sortare.

Descriere :

LSD Radix Sort este una dintre cele mai rapide metode de sortare.Aceasta se bazează pe sortarea în funcţie de cea mai nesemnificativă „cifră“.

  • Radix Sort nu are la bază o tehnică de comparare. Fiecare element din vector(sau atribut al unui element, în cazul structurilor) după care facem sortarea va fi numit cheie.
  • Cheile sunt gândite ca şiruri de „caractere“(unde un „caracter“ poate fi un bit, o cifra, o literă, …).

Algoritmul trece prin următorii paşi:

  • pornind de la poziţia celui mai nesemnificativ „caracter“, numără de câte ori apare fiecare „caracter“ pe poziţia respectivă, apoi împarte un vector auxiliar în secţiuni(imaginare). Numărul de secţiuni este numărul de „caractere“ diferite ce pot exista în vector, adică fiecărei secţiuni îi este asociat un „caracter“, dimensiunea unei secţiuni depinde de numărul de apariţii ale „caracterului“ asociat;
  • pune fiecare element(în vectorul auxiliar) în secţiunea corespunzătoare, apoi copiază vectorul auxiliar înapoi în vectorul ce trebuie sortat. Se obţine un vector sortat până la poziţia curentă;
  • trece la poziţia următoare şi repetă paşii, ultima poziţie fiind cea a celui mai semnificativ „caracter“.

Implementare:

Exemplul prezentat foloseşte un octet pe post de „caracter“. Putem interpreta acest exemplu şi ca scriere a numerelor în baza 256, valoarea fiecărui octet fiind o „cifră“.

#define BYTE 8
#define COUNT_BYTE 256
int obtineOctetul(int n,int byteNr)
{   //cautam octetul de la pozitia byteNr
    //octetul de pe pozitia 0 este LSD = octetul cel mai din dreapta(pentru int)
    int bitsNr =  BYTE * byteNr;
    int mask = COUNT_BYTE - 1;
    return (n >> bitsNr) & mask;
}
void rad(int *a,int *b, int byteNr,int n)
{   //sortare dupa octetul de pe pozitia byteNr,
    // pe pozitia 0 este LSD = octetul cel mai din dreapta
    int i,
        count[COUNT_BYTE] = {0}, //numaram cate elemente au "car." i pe pozitia byteNr
        index[COUNT_BYTE] = {0}; //pozitia la care vom pune urmatorul element cu "car." i
    for(i = 0; i < n;i++) {
        int car = obtineOctetul(a[i],byteNr);
        count[car]++;
    }
    for(i = 1;i < COUNT_BYTE;i++) //sectionam vectorul b
        index[i] = index[i-1] + count[i-1];
    for(i = 0; i < n; i++) { //umplem sectiunile
        int car = obtineOctetul(a[i],byteNr);
        b[index[car]++] = a[i];
    }
}
void radixSort(int *a,int n)
{
    int *b = new int[n], //vector folosit la copiere
        byteNr, //pozitia curenta
        k = sizeof(a[0]); //numarul de "caractere"
    for(byteNr = 0; byteNr < k; byteNr += 2) {
        rad(a, b, byteNr, n); //in loc sa copiem b inapoi in a la fiecare pas
        rad(b, a, byteNr + 1, n); //copiem doar o data la 2 pasi
    }
    delete []b;
}
Exemplul prezentat funcţionează bine pentru întregi cu acelaşi semn.
Performanţa de timp poate fi influenţată prin schimbarea lungimii cuvântului(k), adică prin schimbarea „bazei“ folosite.
laboratoare/laborator-09.1488042806.txt.gz · Ultima modificare: 2017/02/25 19:13 de către mihai.iacov