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)