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: