Propunem studierea următorilor algoritmi de sortare:

• Shell Sort
• Heap Sort
• Radix Sort
• qsort şi sort

Propunem studierea următoarelor structuri auxiliare:

• Heap-uri (pentru Heap Sort)
• vector de sectoare - bucket-uri (pentru Radix Sort)
• deplasarea pe biţi(operaţia bit shift)
• Pachetul STL → <algorithm>

• timp mediu : O(N * log² N)
• timp la limită : O(N * log² N)
• memorie : O(1)
• Stabil : NU

Algoritmul shell sort este o generalizare a algoritmului insertion sort.

• La algoritmul insertion sort, pentru a insera un nou element în lista de elemente deja sortate, se deplasează fiecare element cu câte o poziţie spre dreapta atât timp cât avem elemente mai mari decât el. Practic, fiecare element înaintează spre poziţia sa finală cu câte o poziţie.
• Algoritmul shell sort lucrează similar, doar că deplasează elementele spre poziţia finală cu mai mult de o poziţie. Se lucrează în iteraţii.
• În prima iteraţie se aplică un insertion sort cu salt s1 mai mare decât 1. Asta înseamnă că fiecare element din şirul iniţial este deplasat spre stânga cu câte s1 poziţii atât timp cât întâlneste elemente mai mari decât el.
• Se repetă asemenea iteraţii cu salturi din ce în ce mai mici s2, s3, s4, etc. Ultima iteraţie se face cu saltul 1. Această ultimă iteraţie este practic un insetion sort clasic.
• Principiul este că, după fiecare iteraţie, sirul devine din ce în ce “mai sortat”. Iar, cum algoritmul insertion sort funcţionează cu atât mai repede cu cât sirul este mai sortat, per ansamblu vom obţine o îmbunătăţire de viteză.

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;
        }
    }
}

• timp mediu: O(N log N)
• timp la limită: O(N log N)
• memorie: O(1)
• Stabil: NU

• Metoda de sortare prin selecţie directă se bazează pe selecţia repetată a ultimei chei dintre n elemente, apoi dintre n-1 elemente rămase, etc.
• Pentru a găsi cea mai mică cheie dintre n elemente sunt necesare n-1 comparaţii, apoi găsirea următoarei dintre n-1 elemente are nevoie de n-2 comparaţii, etc. ⇒ n(n-1)/2 comparaţii.
• Această sortare se poate îmbunătăţi prin reţinerea, de la fiecare scanare, de mai multă informaţie decât identificarea unui singur element, cel mai mic.
• De exemplu, cu n/2 comparaţii se poate determina cheia mai mică pentru fiecare pereche de elemente dintre cele n elemente, apoi cu alte n/4 comparaţii se poate determina cheia cea mai mică pentru fiecare pereche ale cheilor determinate anterior, şi aşa mai departe. Astfel, cu n-1 comparaţii se poate construi arborele de selecţie.
• Exemplul ne dă o idee despre cum este implementată funcţia make_heap

#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];
    }
}

• timp mediu: O(N * k)
• timp la limită: O(N * k)
• memorie: O(N + k)
• Stabil: DA

k = lungimea cuvântului/cheii(word size)