Metoda bulelor, sortarea prin insertie si sortarea prin interclasare in Python

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

Cuvinte cheie:   Python,   sortare,   metoda bulelor,   interclasare

• Introducere in Python - Partea a III-a. Liste si bucla for.
• Introducere in Python - Partea I
• Introducere in Python - Partea a IV-a. Clase si obiecte
• Introducere in Python - Partea a II-a. Functii.