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: 25745 25745 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
 OBS.   Nu uita, in Python elementele unei liste sunt numerotate de la 0 la n-1, unde n reprezinta numarul de elemente din lista.

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.

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

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:

Metoda bulelor, sortarea prin insertie si sortarea prin interclasare in Python - Sortarea prin interclasare a unei liste de 7 numere intregi

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!

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
4325
Tutoriale scrise de mcuemica
mcuemica Rang utilizator mcuemica - Incepator
4190
Tutoriale scrise de ellarichards
ellarichards Rang utilizator ellarichards - Incepator
4170
Tutoriale scrise de kheops
kheops Rang utilizator kheops - Mediu
4084
Tutoriale scrise de emonclercheap
emonclercheap Rang utilizator emonclercheap - Incepator
4010
* Acest top reprezinta punctajele acumulate in ultimele 30 de zile.
Ruby on Rails XHTML Verilog Python SEO Vista Illustrator Dreamweaver PSD RoR PHP JSON HTML Outlook Fotografie Action Script Java Gimp Word Javascript Fireworks COREL DRAW MySQL Lightroom Swift 3D SWF StyleSheet CSS Bridge AJAX Powerpoint XML Excel Flash Sony Vegas Photoshop
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