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:
#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]; } afisare(b,n); } 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; }