Aceasta e o versiune anterioară a paginii.
Propunem studierea următorilor algoritmi de sortare:
Propunem studierea următoarelor structuri auxiliare:
Există mai mutle tipuri de heap, dar ne vom referi numai la binary heap pentru implementarea algoritmului Heap sort.
Un heap binar este un arbore binar cu următoarele proprietăţi:
Dacă nodurile conţin numere întregi după care stabilim relaţia de ordine, heap-ul poate fi de două feluri:
Un pas din algoritmul Radix sort foloseşte o funcţie de indexare. Aceasta prelucrează cheia fiecărui element pentru a decide câte elemente să pună în fiecare sector(bucket).
Menţionăm următoarele operaţii pe biţi ce se pot folosi în C/C++ :
Operaţii logice
Deplasări
Descriem numai operaţiile pe care le vom folosi în cadrul exemplului de mai jos: » şi &.
Apar diferenţe în cazul numerelor negative.
Algoritmul shell sort este o generalizare a algoritmului insertion sort.
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; } } }
Descriem următorii paşi pentru o variantă de implementare a algoritmului Heap sort(ordonare crescătoare):
Definim următoarele două funcţii pentru a prezenta mai usor algoritmul Heap sort:
void schimba(int a[],int i,int j) //functie auxiliara { int aux; aux = a[i]; a[i] = a[j]; a[j] = aux; } void cerne(int a[],int n,int k) { int fiuStanga = 2 * k + 1, //pozitia primului copil fiuDreapta = 2 * k + 2, pozMax = fiuStanga; //pozitia copilului mai mare if(fiuStanga >= n) return; //"nodul" k este frunza if(fiuDreapta < n) { if(a[fiuDreapta] > a[fiuStanga] ) { pozMax = fiuDreapta; } }//am ales copilul mai mare if(a[k] < a[pozMax]) { schimba(a,k,pozMax); //nodul k este "cernut" - coboara cerne(a,n,pozMax); //cernem la noua lui pozitie } } void makeHeap(int a[],int n) //functia mai e numita "heapify" { //pentru i > n / 2, i este cu siguranta nod frunza for(int i = n / 2;i >= 0;i--) { //ne asiguram ca exista ordine cerne(a,n,i); // pentru orice nod de la i la n-1 } } void heapSort(int a[],int n) { makeHeap(a,n); //construim un heap while(n > 1) { schimba(a,0,n-1); //mutam maximul pe ultima pozitie n--; //am asezat un element pe pozitia finala cerne(a,n,0); //elementul pus in locul maximului trebuie "cernut" //obtinem din nou forma de heap } }
//implementare STL #include <algorithm> void heapSort(int a[], int n) //fara vector din STL { make_heap(a,a + n);//pointer catre primul element si pointer sort_heap(a,a + n);//catre primul bloc de memorie de după vector }
#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]; } }
k = lungimea cuvântului/cheii(word size)
Vom prezenta varianta LSD(Least Signifiant Digit) a algoritmului de sortare.
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ă“.
Algoritmul trece prin următorii paşi:
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; }
E1. Creaţi un alt vector(mai simplu) pentru salturi, de exemplu: {1e5,1e4,1e3,1e2,1e1,1}, unde 1ek = 10k. Încercaţi să folosiţi acest vector pentru sortare şi observaţi diferenţa de performanţă.
E2. Introduceţi o variabilă globală cu care să contorizaţi numărul de apelări ale funcţiei „cerne“. Afişaţi numărul de apelări necesare pentru construirea heap-ului(makeHeap) şi numărul de apelări necesare pentru tot algoritmul(heapSort).
E3. Încercaţi să sortaţi un vector cu orice numere întregi(pozitive şi negative). Verificaţi rezultatul şi adăugaţi un pas în algoritm pentru a aşeza corect elementele.
E4. Schimbaţi funcţia de indexare(obtineOctetul) şi valoarea lui k pentru a sorta un vector de şiruri de caractere.
E5. Se dă un vector cu n întregi, unde toate valorile din vector sunt cuprinse între 0 şi n^2 - 1. Sortaţi vectorul în timp O(n).