E-learn.ro
Panou utilizatori
Utilizator Parola
Creeaza cont nou    Recupereaza parola
Login
Newsletter
Introdu adresa ta de email
Inscrie-te
Inchide panoul de utilizatori
Add to Google

Tutoriale Python

Descarca toolbar

Toolbar E-learn.ro Facebook Twitter

DEVELOPMENT  /  Python  /  Algoritmi (1)

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

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

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.

Total vizualizari: 25996 25996 afisari   |   Comentarii  4   |   Rating   |   (5 voturi)   |   Timp necesar: 30 min 30 min   |   Nivel de cunostiinte necesar: Mediu  Mediu

Autor: alexandra Expert
Adauga la tutoriale favorit Adauga la tutoriale favorite
Pagina:
1 2 »
comenteaza printeaza

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(n2), unde n reprezinta numarul de elemente ordonate. Pentru cei care nu stiu, complexitatea de O(n2) 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.

 OBS.   Iepuri si testoase
Un concept care mi s-a parut foarte amuzant este acela de "iepuri" si "testoase". Pentru ca elementele de valoare mica de la inceputul unui vector sunt pozitionate corect prin efectuarea unui numar mic de operatii, ele au fost denumite "iepuri". Prin contrast, pozitionarea elementelor mici aflate spre sfarsitul vectorului are nevoie de mai multe operatii, de aceea acestea poarta denumirea de "testoase".

Iata cum sunt ordonate elementele unui vector cu metoda bulelor:

Metoda bulelor, sortarea prin insertie si sortarea prin interclasare in Python - Ordonarea unei multimi de elemente 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.

 OBS.   Pentru ca Python transmite vectorii prin referinta, la returnarea din functia bule vectorul pe care l-am ordonat va fi alterat, deci il putem afisa direct. Retine totusi ca dupa apelarea acestei proceduri, in programul principal nu vei mai dispune de valoarea initiala a vectorului.

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(n2) /4, iar in cazul cel mai favorabil in care vectorul este deja sortat, el devine liniar (adica O(n)).

Metoda bulelor, sortarea prin insertie si sortarea prin interclasare in Python - Ordonarea unei multimi de elemente prin insertie

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
Pagina:
1 2 »
comenteaza printeaza

Cuvinte cheie:   Python,   sortare,   metoda bulelor,   interclasare

Alte tutoriale Python:
Noteaza acest tutorial
Rating tutorial
 
(5 voturi)
Pentru a nota acest tutorial, trebuie sa fii logat!
COMENTARII (4) spune-ti parerea
dutty17 , Marti, 08 Martie 2011, ora 00:10
#4

am incercat sa-l fac si eu ... nu mi-o iesit tot :(... o sa mai incerc.

Raporteaza acest comentariu ca injurios!
Pustiu Pustiu , Marti, 12 Ianuarie 2010, ora 18:36
#3

nu mai stiu eu atata informatica, dar cu siguranta meriti 5 stelute

Raporteaza acest comentariu ca injurios!
alexandra alexandra , Marti, 12 Ianuarie 2010, ora 10:52
#2

Multumesc :). Cine mai vrea sa vada si alti algoritmi implementati in Python, nu trebuie decat sa zica :).

Raporteaza acest comentariu ca injurios!
cborodescu cborodescu , Luni, 11 Ianuarie 2010, ora 21:49
#1

Imi aduci aminte de liceu prin algoritmii astia si de facultate prin limbajul utilizat. Good job!

Raporteaza acest comentariu ca injurios!
Posteaza un comentariu
Pentru a posta un comentariu, trebuie sa fii logat!
0 TOP UTILIZATORI* 0 0
Tutoriale scrise de claibornelara
claibornelara Rang utilizator claibornelara - Incepator
4435
Tutoriale scrise de mcuemica
mcuemica Rang utilizator mcuemica - Incepator
4335
Tutoriale scrise de ellarichards
ellarichards Rang utilizator ellarichards - Incepator
4295
Tutoriale scrise de emonclercheap
emonclercheap Rang utilizator emonclercheap - Incepator
4135
Tutoriale scrise de kheops
kheops Rang utilizator kheops - Mediu
4084
* Acest top reprezinta punctajele acumulate in ultimele 30 de zile.
HTML Vista Fireworks Dreamweaver Verilog Swift 3D Powerpoint Python Photoshop Flash PSD Gimp XML SWF JSON Excel Lightroom XHTML COREL DRAW RoR Bridge Java Ruby on Rails Outlook Action Script Fotografie StyleSheet MySQL Illustrator SEO CSS Word Javascript AJAX Sony Vegas PHP
Promovare:
Daca faci parte din comunitatea E-learn.ro si doresti promovarea acesteia, poti accesa pagina de promovare.
Arhiva newsletter:
Daca ai ratat un numar mai vechi, sau vrei sa revezi care au fost noutatile E-learn.ro la un moment dat, poti accesa arhiva de newslettere.
  Copyright © 2008-2013 E-LEARN.ro. Toate drepturile rezervate. Termeni si conditii.
Conceput si realizat de Neokinetics Software