Aceasta e o versiune anterioară a paginii.
Propunem studierea următorilor algoritmi de sortare:
Propunem studierea următoarelor structuri auxiliare:
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; } } }
#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]; } }
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; }