Implementarea algoritmului Quicksort în Java

1. Prezentare generală

În acest tutorial, vom explora detaliat algoritmul QuickSort, concentrându-ne pe implementarea Java.

De asemenea, vom discuta despre avantajele și dezavantajele sale și apoi vom analiza complexitatea timpului.

2. Algoritm QuickSort

Quicksort este un algoritm de sortare, care se bazează pe principiul de împărțire și cucerire. Are o complexitate medie O (n log n) și este unul dintre cei mai utilizați algoritmi de sortare, în special pentru volumele mari de date.

Este important să ne amintim că Quicksort nu este un algoritm stabil. Un algoritm stabil de sortare este un algoritm în care elementele cu aceleași valori apar în aceeași ordine în ieșirea sortată așa cum apar în lista de intrare.

Lista de intrare este împărțită în două sub-liste de un element numit pivot; o sub-listă cu elemente mai mici decât pivotul și alta cu elemente mai mari decât pivotul. Acest proces se repetă pentru fiecare sub-listă.

În cele din urmă, toate listele secundare sortate se îmbină pentru a forma rezultatul final.

2.1. Etape algoritmice

  1. Alegem un element din listă, numit pivot. O vom folosi pentru a împărți lista în două sub-liste.
  2. Reordonăm toate elementele din jurul pivotului - cele cu valoare mai mică sunt plasate în fața acestuia și toate elementele mai mari decât pivotul după acesta. După acest pas, pivotul se află în poziția sa finală. Acesta este pasul important de partiție.
  3. Aplicăm pașii de mai sus recursiv la ambele sub-liste din stânga și din dreapta pivotului.

După cum putem vedea, quicksort este în mod natural un algoritm recursiv, ca orice abordare de divizare și cucerire.

Să luăm un exemplu simplu pentru a înțelege mai bine acest algoritm.

Arr[] = {5, 9, 4, 6, 5, 3}
  1. Să presupunem că alegem 5 ca pivot pentru simplitate
  2. Mai întâi vom pune toate elementele mai mici de 5 în prima poziție a matricei: {3, 4, 5, 6, 5, 9}
  3. O vom repeta apoi pentru sub-matricea stângă {3,4}, luând 3 ca pivot
  4. Nu există elemente mai mici de 3
  5. Aplicăm quicksort pe sub-matricea din dreapta pivotului, adică {4}
  6. Această sub-matrice constă dintr-un singur element sortat
  7. Continuăm cu partea dreaptă a matricei originale, {6, 5, 9} până când obținem matricea comandată finală

2.2. Alegerea pivotului optim

Punctul crucial în QuickSort este să alegeți cel mai bun pivot. Elementul de mijloc este, desigur, cel mai bun, deoarece ar împărți lista în două sub-liste egale.

Dar găsirea elementului de mijloc dintr-o listă neordonată este dificilă și consumă mult timp, de aceea luăm ca pivot primul element, ultimul element, mediana sau orice alt element aleatoriu.

3. Implementare în Java

Prima metodă este quickSort () care ia ca parametri matricea care trebuie sortată, primul și ultimul index. Mai întâi, verificăm indicii și continuăm doar dacă mai sunt elemente de sortat.

Obținem indexul pivotului sortat și îl folosim pentru a apela recursiv metoda partition () cu aceiași parametri ca metoda quickSort () , dar cu indici diferiți:

public void quickSort(int arr[], int begin, int end) { if (begin < end) { int partitionIndex = partition(arr, begin, end); quickSort(arr, begin, partitionIndex-1); quickSort(arr, partitionIndex+1, end); } }

Să continuăm cu metoda partition () . Pentru simplitate, această funcție ia ultimul element ca pivot. Apoi, verifică fiecare element și îl schimbă înaintea pivotului dacă valoarea acestuia este mai mică.

La sfârșitul partiționării, toate elementele mai mici decât pivotul se află în stânga acestuia și toate elementele mai mari decât pivotul se află în dreapta acestuia. Pivotul este la poziția sa finală sortată și funcția returnează această poziție:

private int partition(int arr[], int begin, int end) { int pivot = arr[end]; int i = (begin-1); for (int j = begin; j < end; j++) { if (arr[j] <= pivot) { i++; int swapTemp = arr[i]; arr[i] = arr[j]; arr[j] = swapTemp; } } int swapTemp = arr[i+1]; arr[i+1] = arr[end]; arr[end] = swapTemp; return i+1; }

4. Analiza algoritmului

4.1. Complexitatea timpului

În cel mai bun caz, algoritmul va împărți lista în două sub-liste de dimensiuni egale. Deci, prima iterație a listei complete de dimensiuni n are nevoie de O (n) . Sortarea celor două sub-liste rămase cu n / 2 elemente necesită 2 * O (n / 2) fiecare. Ca rezultat, algoritmul QuickSort are complexitatea lui O (n log n) .

În cel mai rău caz, algoritmul va selecta doar un element în fiecare iterație, deci O (n) + O (n-1) + ... + O (1) , care este egal cu O (n2) .

În medie, QuickSort are O (n log n) complexitate, făcându-l potrivit pentru volume mari de date.

4.2. QuickSort vs MergeSort

Să discutăm în ce cazuri ar trebui să alegem QuickSort peste MergeSort.

Deși atât Quicksort, cât și Mergesort au o complexitate medie în timp de O (n log n) , Quicksort este algoritmul preferat, deoarece are o complexitate spațială O (log (n)) . Mergesort, pe de altă parte, necesită O (n) spațiu de stocare suplimentar, ceea ce îl face destul de scump pentru tablouri.

Quicksort necesită accesarea unor indici diferiți pentru operațiunile sale, dar acest acces nu este direct posibil în listele legate, deoarece nu există blocuri continue; prin urmare, pentru a accesa un element trebuie să iterăm prin fiecare nod de la începutul listei legate. De asemenea, Mergesort este implementat fără spațiu suplimentar pentru LinkedLists.

Într-un astfel de caz, în general se preferă creșteri generale pentru Quicksort și Mergesort.

5. Concluzie

Quicksort este un algoritm elegant de sortare, care este foarte util în majoritatea cazurilor.

Este, în general, un algoritm „în loc”, cu complexitatea medie a timpului O (n log n).

Un alt punct interesant de menționat este că metoda Java Arrays.sort () folosește Quicksort pentru sortarea matricilor primitivelor. Implementarea utilizează doi pivoti și funcționează mult mai bine decât soluția noastră simplă, de aceea pentru codul de producție este de obicei mai bine să folosiți metode de bibliotecă.

Ca întotdeauna, codul pentru implementarea acestui algoritm poate fi găsit peste depozitul nostru GitHub.