GeeksforGeeks

În acest articol, vom discuta proprietățile importante ale diferitelor tehnici de sortare, inclusiv complexitatea, stabilitatea și constrângerile de memorie. Înainte de a înțelege acest articol, ar trebui să înțelegeți elementele de bază ale diferitelor tehnici de sortare (A se vedea : Tehnici de sortare).

Analiza complexității în timp –
Am discutat despre complexitatea în cel mai bun, mediu și cel mai rău caz a diferitelor tehnici de sortare cu scenarii posibile.

Sortare bazată pe comparații –
În sortarea bazată pe comparații, elementele unui tablou sunt comparate între ele pentru a găsi tabloul sortat.

• Sortare cu bule și sortare prin inserție –
  Complexitatea în timp medie și în cel mai rău caz: n^2
  Complexitatea în timp în cel mai bun caz: n atunci când tabloul este deja sortat.
  Cazul cel mai defavorabil: atunci când array-ul este sortat invers.
• Selection sort –
  Complexitatea timpului în cel mai bun, mediu și cel mai defavorabil caz: n^2 care este independent de distribuția datelor.
• Merge sort –
  Complexitatea de timp cea mai bună, medie și cea mai proastă în cazul cel mai rău: nlogn care este independent de distribuția datelor.
• Heap sort –
  Complexitatea de timp cea mai bună, medie și cea mai proastă în cazul cel mai rău: nlogn care este independent de distribuția datelor.
• Sortare rapidă –
  Este o abordare de tip „divide et impera” cu relație de recurență:

   T(n) = T(k) + T(n-k-1) + cn

  Cazul cel mai defavorabil: când array-ul este sortat sau sortat invers, algoritmul de partiție împarte array-ul în două subarray-uri cu 0 și n-1 elemente. Prin urmare,

  T(n) = T(0) + T(n-1) + cnSolving this we get, T(n) = O(n^2)

  Cazul cel mai bun și cazul mediu: În medie, algoritmul de partiționare împarte matricea în două sub-rețele cu dimensiuni egale. Prin urmare,

  T(n) = 2T(n/2) + cnSolving this we get, T(n) = O(nlogn)

Sortare bazată pe necomparare –
În sortarea bazată pe necomparare, elementele tabloului nu sunt comparate între ele pentru a găsi tabloul sortat.

• Sortare Radix –
  Complexitatea de timp cea mai bună, medie și cea mai defavorabilă: nk, unde k este numărul maxim de cifre din elementele tabloului.
• Sortare prin numărare –
  Complexitatea de timp cea mai bună, medie și cea mai defavorabilă: n+k, unde k este dimensiunea tabloului de numărare.
• Bucket sort –
  Complexitatea de timp cea mai bună și medie: n+k unde k este numărul de buckets.
  Complexitatea de timp în cel mai rău caz: n^2 dacă toate elementele aparțin aceluiași bucket.

Tehnica de sortare in-place/Outplace –
O tehnică de sortare este inplace dacă nu utilizează memorie suplimentară pentru sortarea tabloului.
Dintre tehnicile bazate pe comparație discutate, numai sortarea prin fuziune este o tehnică outplaced, deoarece necesită un array suplimentar pentru a fuziona subarray-urile sortate.
Dintre tehnicile care nu se bazează pe comparație discutate, toate sunt tehnici outplaced. Sortarea prin numărare utilizează o matrice de numărare, iar sortarea cu găleți utilizează un tabel hash pentru sortarea matricei.

Tehnică online/offline –
O tehnică de sortare este considerată online dacă poate accepta date noi în timp ce procedura este în curs de desfășurare, adică nu este nevoie de date complete pentru a începe operația de sortare.
Printre tehnicile bazate pe comparație discutate, doar Insertion Sort se califică pentru acest lucru din cauza algoritmului de bază pe care îl utilizează, și anume procesează matricea (nu doar elementele) de la stânga la dreapta, iar dacă se adaugă elemente noi în dreapta, acest lucru nu are impact asupra operațiunii în curs.

Tehnică stabilă/instabilă –
O tehnică de sortare este stabilă dacă nu modifică ordinea elementelor cu aceeași valoare.
Dintre tehnicile bazate pe comparație, sortarea cu bule, sortarea prin inserție și sortarea prin îmbinare sunt tehnici stabile. Sortarea prin selecție este instabilă, deoarece poate schimba ordinea elementelor cu aceeași valoare. De exemplu, considerăm matricea 4, 4, 4, 1, 3.

În prima iterație, elementul minim găsit este 1 și este schimbat cu 4 pe poziția 0. Prin urmare, ordinea lui 4 în raport cu 4 de la poziția 1 se va schimba. În mod similar, quick sort și heap sort sunt, de asemenea, instabile.

Dintre tehnicile bazate pe necomparare, Counting sort și Bucket sort sunt tehnici de sortare stabile, în timp ce stabilitatea radix sort depinde de algoritmul de bază utilizat pentru sortare.

Analiza tehnicilor de sortare :

• Când array-ul este aproape sortat, sortarea prin inserție poate fi preferată.
• Când ordinea intrărilor nu este cunoscută, sortarea prin îmbinare este preferată deoarece are o complexitate de timp în cel mai rău caz de nlogn și este, de asemenea, stabilă.
• Când array-ul este sortat, sortarea prin inserție și sortarea cu bule oferă o complexitate de n dar sortarea rapidă oferă o complexitate de n^2.

Que – 1. Care algoritm de sortare va dura cel mai puțin timp atunci când toate elementele din tabloul de intrare sunt identice? Luați în considerare implementări tipice ale algoritmilor de sortare.
(A) Insertion Sort
(B) Heap Sort
(C) Merge Sort
(D) Selection Sort

Soluție: După cum s-a discutat, sortarea prin inserție va avea o complexitate de n atunci când matricea de intrare este deja sortată.

Que – 2. Luați în considerare algoritmul Quicksort. Să presupunem că există o procedură pentru găsirea unui element pivot care împarte lista în două subliste, fiecare dintre ele conținând cel puțin o cincime din elemente. Fie T(n) numărul de comparații necesare pentru sortarea a n elemente. Atunci, (GATE-CS-2012)
(A) T(n) <= 2T(n/5) + n
(B) T(n) <= T(n/5) + T(4n/5) + n
(C) T(n) <= 2T(4n/5) + n
(D) T(n) <= 2T(n/2) + n

Soluție: T(n) <= 2T(n/2) + n

Soluție: T(n) <: Complexitatea sortării rapide poate fi scrisă astfel:

T(n) = T(k) + T(n-k-1) + cn

Cum se arată în întrebare, o listă conține 1/5 din totalul elementelor. Prin urmare, o altă listă va avea 4/5 din totalul elementelor. Punând valorile, obținem:

T(n) = T(n/5) + T(4n/5) + cn, ceea ce corespunde variantei (B).

Tabel comparativ de complexitate în timp și spațiu :

.

.

.

.

Algoritmul de sortare	Complexitatea temporală			Complexitatea spațială
	Cazul cel mai bun	Media Case	Worst Case	Worst Case
Bubble Sort	Ω(N)	Θ(N2)	O(N2)	O(N2)	O(1)
Selection Sort	Ω(N2)	Θ(N2)	O(N2)	O(1)
Insertion Sort	Ω(N)	Θ(N2)	O(N2)	O(1)
Merge Sort	Ω(N log N)	Θ(N log N)	O(N log N)	O(N)
Heap Sort	Ω(N log N)	Θ(N log N)	O(N log N)	O(N log N)	O(1)
Sortare rapidă	Ω(N log N)	Θ(N log N)	O(N2)	O(N log N)
Sortare Radix	Ω(N k)	Θ(N k)	O(N k)	O(N + k)
Count Sort	Ω(N + k)	Θ(N + k)	O(N + k)	O(N + k)	O(k)
Bucket Sort	Ω(N + k)	Θ(N + k)	O(N2)	O(N2)	O(N)