Curs de Python 3 - Liceu - Sortare prin interschimbare directă (<b>Exchange Sort</b>)

ALGORITMI

PROGRAMARE

Sortare prin interschimbare directă

Acasă > Lecții online > Metode de sortare

Sortarea prin interschimbare directă (Exchange Sort) este unul dintre cei mai intuitivi algoritmi de sortare. Ideea din spatele lui este simplă: fiecare element este comparat cu toate elementele aflate după el, iar atunci când se găsește unul mai mic, cele două elemente sunt interschimbate. Prin repetarea acestui proces, cele mai mici valori ajung treptat la începutul tabloului, iar tabloul devine ordonat.

Important ⚠️ În algoritmica clasică se folosește frecvent termenul vector sau tablou. Python dispune atât de liste (list), cât și de tablouri (array), însă, pentru simplitate și deoarece sunt utilizate cel mai frecvent, toate exemplele din această secțiune folosesc liste.

Mecanismul

Algoritmul sortează un tablou în ordine crescătoare prin comparații directe între un element fixat (pe poziția i) și toate elementele aflate după el (de pe pozițiile j). Dacă este găsit un element mai mic, cele două valori sunt interschimbate imediat. La finalul fiecărui pas i, pe poziția i se află cel mai mic element din partea rămasă nesortată.

▶️ Efectuează simularea de mai jos:

Complexitatea algoritmului

🕒 Timp (viteză de execuție): O(n²) în toate cazurile (defavorabil, mediu și chiar favorabil, deoarece cele două bucle se execută complet indiferent dacă tabloul era deja sortat).

💾 Spațiu (consum de memorie): O(1), este un algoritm in-place, adică nu necesită memorie suplimentară. Aceasta înseamnă că algoritmul folosește o cantitate de memorie constantă, indiferent cât de mare este volumul de date primit.

Observații

Deși acestă metodă este ușor de înțeles și de implementat, ea nu este eficientă pentru tablouri mari, deoarece numărul de comparații crește foarte rapid odată cu dimensiunea datelor. Din acest motiv, în aplicațiile reale este înlocuită de algoritmi mai performanți, precum Merge Sort sau Quick Sort.

În practică, atunci când lucrăm în Python, rareori implementăm manual acest algoritm. Limbajul oferă funcțiile sort() și sorted(), care folosesc algoritmi mult mai eficienți. Totuși, este important să înțelegem cum funcționează Sortarea prin interschimbare directă, deoarece ea ne ajută să înțelegem principiile de bază ale algoritmilor de sortare: comparațiile dintre elemente, interschimbările și modul în care un tablou ajunge treptat să fie ordonat. Odată înțelese aceste concepte, algoritmii mai avansați vor fi mult mai ușor de învățat.

Avantaje

Există situații în care sortarea prin interschimbare directă poate fi preferată altor algoritmi. De exemplu, aceasta poate fi utilă pentru sortarea tablourilor foarte mici sau a celor care sunt deja aproape sortate. În astfel de cazuri, implementarea unui algoritm mai complex poate să nu aducă beneficii suficiente pentru a justifica complexitatea suplimentară.

Un alt avantaj al sortării prin interschimbare directă este că este un algoritm stabil, ceea ce înseamnă că păstrează ordinea relativă a elementelor egale. Acest aspect poate fi important în anumite aplicații, de exemplu atunci când se sortează înregistrări care conțin mai multe câmpuri.

Program complet


				def sortare(v):

				    for i in range(len(v) - 1):

				        for j in range(i + 1, len(v)):

				            if v[i] > v[j]:

				                v[i], v[j] = v[j], v[i]  # interschimbare

				    return v



				# Program principal

				n = int(input("Numărul de elemente: "))



				v = []

				for i in range(n):

				    x = int(input(f"v[{i}] = "))

				    v.append(x)



				sortare(v)



				print("Tabloul sortat este:")

				print(v)