10.4. Compararea metodelor de sortare

În lecțiile anterioare am studiat trei metode. Selecția minimului și metoda bulelor sunt metode bazate pe comparații. Lista de frecvențe exploatează proprietățile domeniului valorilor și numără aparițiile.

Comparații și interschimbări

Selecția minimului face aproximativ n(n-1)/2 comparații indiferent de ordinea inițială, dar numărul interschimbărilor poate fi mai mic. Bulele fără oprire anticipată are ordin O(n²). Cu oprire anticipată, o listă deja sortată poate fi tratată în O(n).

Frecvențele

Dacă m este dimensiunea domeniului, timpul este O(n+m), iar memoria suplimentară este O(m). Metoda este atractivă când domeniul este mic și cunoscut.

Nu există o singură metodă potrivită pentru orice listă. Alegerea depinde de proprietățile datelor: dimensiunea listei, domeniul valorilor și cât de aproape este lista de ordinea finală.

Putem număra comparațiile și interschimbările pentru a realiza un experiment. Aceste instrumente nu înlocuiesc analiza teoretică, ci o completează.

def selectie(a):
    comparatii = 0
    interschimbari = 0
    n = len(a)
    for i in range(n - 1):
        poz_min = i
        for j in range(i + 1, n):
            comparatii += 1
            if a[j] < a[poz_min]:
                poz_min = j
        if poz_min != i:
            a[i], a[poz_min] = a[poz_min], a[i]
            interschimbari += 1
    return comparatii, interschimbari

def bule(a):
    comparatii = 0
    interschimbari = 0
    n = len(a)
    for i in range(n - 1):
        schimbat = False
        for j in range(n - 1 - i):
            comparatii += 1
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                interschimbari += 1
                schimbat = True
        if not schimbat:
            break
    return comparatii, interschimbari

Algoritm Comparare
alege aceeași listă de test
aplică selecția minimului și numără comparațiile și interschimbările
aplică metoda bulelor și numără comparațiile și interschimbările
dacă domeniul valorilor este mic și cunoscut atunci
    construiește lista de frecvențe
    compară timpul și memoria necesare
sfârșit dacă
interpretează rezultatele și alege metoda potrivită
SFÂRȘIT ALGORITM

• Același ordin de complexitate nu înseamnă același număr exact de operații în orice situație.
• Alegerea metodei depinde de n, domeniu, repetări și ordinea inițială.
• Frecvențele pot fi rapide, dar memoria suplimentară este proporțională cu domeniul.
• Pentru comparații experimentale folosim exact aceleași date.
• Testarea experimentală verifică exemple; justificarea algoritmică explică de ce soluția este corectă.

Problemă

Pentru 200 de punctaje întregi între 0 și 100, compară selecția minimului, bulele și frecvențele.

Analiză

n=200, iar domeniul are m=101 valori posibile. Selecția minimului are 200·199/2 = 19 900 comparații. Bulele are ordin O(n²), iar numărul exact depinde de date dacă folosim oprirea anticipată. Frecvențele necesită parcurgerea celor 200 de valori și a domeniului de 101 valori, apoi reconstrucția rezultatelor.

Concluzie

Pentru punctaje între 0 și 100, lista de frecvențe este o alegere foarte bună deoarece domeniul este mic și cunoscut. Pentru un domeniu enorm, această metodă poate deveni nepotrivită din punctul de vedere al memoriei.

Testarea

Testează o listă aleatorie, una sortată, una descrescătoare, una cu valori egale și una aproape sortată. La bule, urmărește oprirea anticipată; la frecvențe, urmărește dimensiunea domeniului.

Justificarea soluției

Selecția minimului și bulele sunt metode de ordin pătratic în cazul general. Frecvențele folosesc domeniul restrâns și au ordin O(n+m). Alegerea corectă se bazează pe timp, memorie și proprietățile datelor.

1. Completează tabelul pentru n=10: numărul de comparații al selecției minimului.
2. Compară două liste de lungime 20: una sortată și una descrescătoare, folosind bulele cu oprire anticipată.
3. Pentru note 1–10, explică de ce frecvențele sunt potrivite.
4. Pentru valori între 0 și 10^9, explică de ce frecvențele pot fi nepotrivite.
5. Alege metoda pentru note 1–10, 100 de numere reale și 500 de temperaturi între -20 și 40.

1. Pentru n=200, calculează exact numărul de comparații al selecției minimului.
2. Explică diferența dintre cazul favorabil și nefavorabil al bulelor cu oprire anticipată.
3. Pentru n=1000 și m=11, compară O(n²) cu O(n+m).
4. Realizează un experiment care numără comparațiile și interschimbările pe aceleași cinci liste.
5. Scrie un paragraf argumentativ: „Cea mai bună metodă de sortare depinde de date”.