Structuri și algoritmi de date

(A doua parte — Sortare)

„În prima parte” a explorării noastre a structurilor de date și a algoritmilor, am învățat că utilizarea unei matrice sortate ne oferă o mai mare flexibilitate atunci când vine vorba de sarcini precum găsirea, modificarea sau ștergerea elementelor. Acest lucru devine valoros atunci când avem de-a face cu multe elemente, care sunt comune în activitățile noastre zilnice. Deoarece aceste acțiuni sunt utilizate frecvent, este esențial să luați ceva timp pentru a discuta despre algoritmii de sortare, mai ales atunci când aveți de-a face cu matrice neordonate.

Articolul va fi structurat după cum urmează:

Cum ați proceda?

Sortificare cu bule

Selecție Sortare

Sortare prin inserare

Cum ai face-o?

Ca persoană, ai avantaje față de un program de calculator. Puteți să vă uitați la toți copiii deodată și să îl alegeți rapid pe cel mai înalt, fără a fi nevoie să îi măsurați și să îi comparați pe fiecare.

După o repoziționare informală, puteți aranja cu ușurință toți copiii într-o linie, așa cum se arată în ilustrație.

Cu toate acestea, un program de calculator nu poate procesa datele în același mod. Poate compara doar doi copii la un moment dat, datorită modului în care funcționează operatorii de comparație. Această perspectivă limitată este o temă comună în algoritmi. Deși lucrurile ar putea părea simple pentru oameni, algoritmii nu pot vedea imaginea de ansamblu. În schimb, se concentrează pe detalii specifice și urmează reguli simple.

Cei trei algoritmi din acest capitol urmează doi pași în mod repetat până când datele sunt sortate

Sortificare cu bule

Bubble Sort este un algoritm simplu de sortare care parcurge în mod repetat o listă de elemente și compară elementele adiacente, schimbându-le dacă sunt în ordinea greșită. Se numește „Bubble Sort” deoarece elementele mai mici „bulează” în partea de sus a listei, în timp ce elementele mai mari „se scufundă” în partea de jos.

Iată cum funcționează sortarea cu bule:

  • Începeți prin a compara primele două elemente ale listei. Dacă primul element este mai mare decât al doilea, schimbați-le.
  • Treceți la următoarea pereche de elemente și comparați-le. Din nou, schimbați dacă este necesar.
  • Continuați acest proces pentru întreaga listă, comparând și schimbând în mod repetat elementele adiacente până când nu mai sunt necesare schimburi.
  • După o trecere prin listă, cel mai mare element va fi „bulboat” până în ultima poziție. Repetați procesul pentru elementele rămase nesortate.
  • Continuați să repetați pașii 1–4 până când întreaga listă este sortată.

Bubble Sort este ușor de înțeles și implementat, dar nu este foarte eficient pentru liste mari. Complexitatea timpului mediu și cel mai rău caz este O(n²), unde „n” este numărul de elemente din listă. Acest lucru îl face nepractic pentru sortarea seturi de date mari. Cu toate acestea, poate fi o alegere excelentă pentru liste mici sau ca un exercițiu de învățare pentru a înțelege algoritmii de sortare.

Selecție Sortare

Selection Sort este un algoritm simplu de sortare care funcționează prin selectarea în mod repetat a elementului minim (sau maxim) din partea nesortată a matricei și plasându-l la începutul (sau la sfârșitul) părții sortate. Are o complexitate de timp de O(n²) pentru scenariile medii și cele mai defavorabile, ceea ce îl face ineficient pentru listele mari.

Iată cum funcționează algoritmul de sortare a selecției:

  • Găsiți elementul minim (sau maxim) în partea nesortată a matricei.
  • Schimbați-l cu primul element al părții nesortate.
  • Repetați pașii de mai sus pentru partea rămasă nesortată a matricei, excluzând elementul care tocmai a fost plasat în partea sortată.

Selection Sort se numește astfel deoarece „selectează” cel mai mic (sau cel mai mare) element și îl „bulbează” până la poziția corectă în partea sortată a matricei. În ciuda simplității sale, Selection Sort nu este eficient pentru matrice mari din cauza complexității în timp pătratice.

Spre deosebire de alți algoritmi de sortare, cum ar fi Bubble Sort, Selection Sort nu schimbă continuu elemente în timp ce scanează matricea. Această caracteristică poate fi avantajoasă în situațiile în care schimbarea elementelor este costisitoare.

Sortare prin inserare

Insertion Sort este un algoritm de sortare simplu care construiește matricea sortată finală pe rând. Este un algoritm de sortare bazat pe comparație în care matricea este împărțită într-o parte sortată și una nesortată. În fiecare iterație, algoritmul preia un element din partea nesortată și îl introduce în poziția corectă în partea sortată.

Iată cum funcționează Sortarea prin inserare:

  • Începeți cu al doilea element (indice 1) și comparați-l cu primul element (indice 0).
  • Dacă al doilea element este mai mic (sau mai mare, în funcție de ordinea de sortare) decât primul element, schimbați-le.
  • Treceți la al treilea element (index 2) și comparați-l cu elementele anterioare din partea sortată. Introduceți-l în poziția corectă în piesa sortată, deplasând elementele mai mari la dreapta.
  • Repetați procesul pentru elementele rămase nesortate, inserând de fiecare dată elementul curent în poziția sa corectă în cadrul piesei sortate.

Sortarea prin inserție este eficientă pentru seturi de date mici sau matrice parțial sortate. Are o complexitate liniară în timp de O(n) pentru tablourile sortate. Cu toate acestea, complexitatea de timp în cel mai rău caz este pătratică, ceea ce îl face mai puțin potrivit pentru matrice mari.

În rezumat, Insertion Sort este un algoritm de sortare simplu care este ușor de înțeles și implementat. Deși poate să nu fie cea mai eficientă alegere pentru seturi de date mari, poate fi o opțiune practică pentru matrice mici sau sortate.