Python a fost intotdeauna unul dintre limbajele mele de programare preferate, pe care din pacate nu am avut ocazia sa-l utilizez foarte mult. Cateva teme la facultate, cateva proiecte mici si cam atat... Mare pacat, pentru ca sintaxa Python este una dintre cele mai "cool": fara punct si virgula (uimitor, nu-i asa?), fara acolade care sa delimiteze blocurile de cod, fara declaratii de tipuri si cuvinte cheie "inutile".

De la inceput, scopul declarat al acestui limbaj a fost simbioza dintre puterea de calcul si sintaxa clara. Python suporta programarea orientata pe obiecte si functionala, are o librarie standard cuprinzatoare si manageriaza singur memoria. Ca observatie, faptul ca utilizeaza indentarea codului pentru a delimita blocurile de executie este neobisnuit pentru un limbaj de programare dintre cele mai populare.

Acum ca am aflat ce-si propune Python, sa trecem la treaba. In acest tutorial va voi prezenta implementarea a trei algoritmi de sortare in Python, si anume metoda bulelor, sortarea prin interclasare si sortarea prin insertie. Desi pentru a pastra simplitatea programelor am sortat o lista de numere, functiile pe care le voi prezenta pot fi usor alterate pentru a ordona liste de obiecte, ceea ce de fapt ar fi si scopul acestor algoritmi. Pana la urma, daca ceea ce vrei este sa ordonezi o lista de numere, poti utiliza cu succes metoda predefinita sort().

Daca vrei sa afli mai multe despre sintaxa Python si despre cum se instaleaza shell-ul, poti parcurge celelalte tutoriale din seria Introducere in Python, in special cele despre functii si liste.

Metoda bulelor

Desi acest algoritm este unul dintre cele mai simple, trebuie sa retii ca performanta sa pentru vectori de dimensiuni mari este una scazuta. In cazul cel mai defavorabil, complexitatea sa ajunge la O(n²), unde n reprezinta numarul de elemente ordonate. Pentru cei care nu stiu, complexitatea de O(n²) este echivalenta cu doua bucle for imbricate, astfel:

for i from 1 to n 
    for j from 1 to n

ceea ce inseamna ca se executa n * n instructiuni.

Un avantaj al acestei metode este eficienta de detectare ca un vector este deja sortat. Pentru acest caz, performanta bubble-sort ajunge pana la O(n), adica o singura parcurgere a listei de elemente.

Iata cum sunt ordonate elementele unui vector cu metoda bulelor:

Ordonarea unei multimi de elemente cu metoda bulelor Sursa: wikipedia.org

Algoritmul in Python arata in felul urmator:

# functia de sortare cu metoda bulelor
def bule(A):
 
    schimba_elem = 1
 
    # calculeaza lungimea vectorului
    n = len(A) - 1
        
    # cat timp schimba_elem este true(1)
    while schimba_elem:
        
        schimba_elem = 0
        
        i = 0
 
        # i parcurge vectorul pana la penultimul element
        while i < n:
            
            # daca A[i] este mai mare decat A[i+1]
            if A[i] > A[i+1]:
 
                # interschimba cele doua elemente
                aux = A[i+1]
                A[i+1] = A[i]
                A[i] = aux
 
                # seteaza variabila schimba_elem la true(1)
                schimba_elem = 1
 
            i = i + 1
 
# programul principal
vector = [12,5,4,10,7,67,45]
print "Vectorul initial: "
print vector
 
bule(vector)
 
print "Vectorul sortat: "
print vector

Dupa cum poti observa mai sus, functia bule este apelata pentru a ordona un vector de sapte numere. Aceasta functie contine o bucla while ce va fi executata atat timp cat exista elemente neordonate (while schimba_elem). De fiecare data cand aceasta bucla este reluata, este parcurs intreg vectorul (while i < n), iar cand un element mare este gasit inainte unui element mai mic (if A[i] > A[i+1]), cele doua valori sunt interschimbate.

Sortarea prin insertie

Acest algoritm este unul simplu, bazandu-se pe construirea treptata a listei sortate, adaugand element cu element. Este mult mai putin eficient decat alti algoritmi ca sortarea rapida, sortarea prin interclasare, heapsort, dar are anumite avantaje, cum ar fi usurinta de implementare si eficienta pentru liste de dimensiuni mici.

Timpul mediu de executie este O(n²) /4, iar in cazul cel mai favorabil in care vectorul este deja sortat, el devine liniar (adica O(n)).

Ordonarea unei multimi de elemente prin insertie Sursa: wikipedia.org

Functionarea algoritmului poate fi descrisa astfel:

1. Presupunem ca exista o functie denumita Insert, al carui scop este inserarea unei valori intr-o lista sortata aflata la inceputului unui vector. Ea porneste de la sfarsitul listei si muta fiecare element cu o pozitie spre dreapta, pana gaseste o pozitie convenabila pentru noul element. In consecinta, aceasta functie va rescrie valoarea aflata imediat dupa secventa sortata.

Ca exemplu, sa presupunem ca am ordonat partial urmatorul vector, ajungand la cel de-al cincilea element (7):

[4,5,10,12,7,67,45]

In acest caz, lista sortata este reprezentata de sub-vectorul [4,5,10,12] si urmatorul element (7) trebuie inserat in ea. Pentru fiecare pas, vectorul nostru va arata astfel:

[4, 5, 10, 12, 12, 67, 45]
[4, 5, 10, 10, 12, 67, 45]

2. Pentru a realiza sortarea unui vector, se realizeaza parcurgerea acestuia, invocand procedura Insert pentru fiecare element in parte. Fiecare insertie rescrie o singura valoare, si anume cea inserata. In final, deoarece procedura Insert a rescris incorect cel de-al cincilea element, valoarea acestuia (7) va fi copiata la pozitia a treia din lista, marind lungimea sub-vectorului sortat:

[4, 5, 7, 10, 12, 67, 45]

Pentru a clarifica lucrurile, iata implementarea acestui algoritm in Python:

# functie de sortare prin insertie
def insertie(B):
 
    # parcurge vectorul de la al doilea element (i=1)
    # la ultimul element
    i = 1
 
    while i <= len(B) - 1:
 
        # retine elementul la care a ajuns,
        # deoarece acest element va fi rescris ulterior
        val = B[i]
        j = i - 1
 
        # parcurge vectorul de la pozitia i - 1 catre inceput,
        # pana gaseste o pozitie convenabila pentru valoarea val
        
        while j >= 0 and B[j] > val:
            # muta elementele cu o pozitie spre dreapta
            B[j + 1] = B[j]
            j = j - 1
 
        # retine elementul rescris (B[i]) in B[j+1]
        B[j + 1] = val
    
        i = i + 1
 
# programul principal
vector = [12,5,4,10,7,67,45]
 
print "Vectorul initial:"
print vector
 
insertie(vector)
 
print "Vectorul sortat:"
print vector

Dupa cum poti observa, in acest exemplu procedura Insert este reprezentata de fapt de cel de-al doilea ciclu while (while j >= 0 and B[j] > val). In rest, ea functioneaza dupa cum am descris mai sus.

Sortarea prin interclasare

Sortarea prin interclasare sau merge-sort este un algoritm recursiv de tipul divide-et-impera, cu un timp de executie O(n log n). Functionarea acestui algoritm poate fi descrisa astfel:

1. Daca lista este de lungime 0 sau 1, atunci este deja sortata. Altfel:

2. Imparte lista nesortata in doua liste de lungimi egale (stanga si dreapta).

3. Sorteaza cele doua sub-liste recursiv prin aplicarea aceluiasi algoritm de sortare.

4. Uneste cele doua sub-liste intr-una singura prin apelarea unei proceduri.

Sa presupunem ca avem un vector C cu n elemente de la C[0] la C[n-1]. Vom calcula mijlocul acestui vector ca m = n /2, apoi il vom imparti in doua liste: (C[0],C[1], ..., C[m-1]) si (C[m],C[m+1],...,C[n-1]) si vom apela procedura de sortare pentru fiecare sub-lista in parte. Dupa cele doua jumatati au fost ordonate, ele vor fi unite pentru a forma un singur vector.

Ordonarea unei multimi de elemente prin interclasare Sursa: wikipedia.org

Iata cum arata acest algoritm in Python:

# functie ce realizeaza sortarea prin interclasare
def interclasare(C):
 
    # daca vectorul are mai putin de un element,
    # nu avem ce sorta
    if len(C) <= 1:
        return C
 
    rezultat = []
    stanga = []
    dreapta = []
 
    # calculeaza mijlocul vectorului
    mijloc = len(C) / 2
 
    # imparte vectorul in doi sub-vectori (stanga si dreapta)
    i = 0
 
    # stanga va contine elementele de la 0 la mijloc - 1
    while i < mijloc:
        stanga.append(C[i])
        i = i + 1
 
    # dreapta va contine elementele de la mijloc pana la sfarsitul vect.
    while i < len(C):
        dreapta.append(C[i])
        i = i + 1
 
    # realizeaza interclasarea pentru cei doi subvectori
    stanga = interclasare(stanga)
    dreapta = interclasare(dreapta)
 
    # daca ultimul element din stanga este mai mare
    # decat primul element din dreapta 
    if stanga[len(stanga) - 1] > dreapta[0]:
        # interclaseaza cei doi vectori
        rezultat = uneste(stanga,dreapta)
    else:
 
        # altfel, copiaza elementele din stanga
        # si apoi dreapta in rezultat
        for item in stanga:
            rezultat.append(item)
 
        for item in dreapta:
            rezultat.append(item)
 
    return rezultat
    
#programul principal
vector = [38,27,43,3,9,82,10]
 
print "Vectorul initial:"
print vector
 
print "Vectorul sortat:"
print interclasare(vector)

Functia uneste este apelata doar daca in sub-vectorul stanga exista elemente mai mari decat in dreapta. Ea arata astfel:

# functie ce realizeaza unirea cei doi sub-vectori
def uneste(stanga,dreapta):
 
    rezultat = []
 
    # cat timp si stanga si dreapta au elemente
    while len(stanga) > 0 and len(dreapta) > 0:
 
        # daca primul element din stanga este mai mic
        # decat primul element din dreapta
        if stanga[0] <= dreapta[0]:
 
            # copiaza primul element din stanga in rezultat
            rezultat.append(stanga[0])
 
            # sterge elementul copiat din vectorul stanga
            del stanga[0]
 
        # altfel
        else:
 
            # copiaza primul element din dreapta in rezultat
            rezultat.append(dreapta[0])
 
            # sterge elementul copiat din vectorul dreapta
            del dreapta[0]
 
    # daca mai exista elemente necopiate in stanga
    if len(stanga) > 0:
 
        # copiaza toate elementele din stanga in rezultat
        i = 0
        while i < len(stanga):
            rezultat.append(stanga[i])
            i = i + 1
 
    # altfel inseamna ca mai avem elemente necopiate in dreapta
    else:
 
        # copiaza toate elementele din dreapta in rezultat
        i = 0
        while i < len(dreapta):
            rezultat.append(dreapta[i])
            i = i + 1
 
    # returneaza vectorul rezultat
    return rezultat

Dupa cum poti observa, desi necesita doua functii, algoritmul este destul de usor de inteles. Pentru a face lucrurile si mai clare, iata cum va fi sortat un vector cu 7 elemente:

Sortarea prin interclasare a unei liste de 7 numere intregi Sursa: wikipedia.org

Sper ca acesti algoritmi sa-ti fie de folos pentru programele tale in Python. Nu uita, ei pot fi modificati pentru a lucra cu liste de obiecte, in functie de scopul programului tau.

Daca ai intrebari, nu ezita sa lasi un comentariu sau sa-mi trimiti un mesaj. Spor la lucru!