Sortare cu bule

PerformanceEdit

Sortarea cu bule are cel mai rău caz și o complexitate medie de О (n2), unde n este numărul de elemente sortate. Majoritatea algoritmilor de sortare practici au o complexitate semnificativ mai bună în cazul cel mai rău sau mediu, adesea O (n log n). Chiar și alți algoritmi de sortare О (n2), cum ar fi sortarea prin inserție, rulează în general mai repede decât sortarea cu bule și nu sunt mai complexe. Prin urmare, sortarea cu bule nu este un algoritm practic de sortare.

Singurul avantaj semnificativ pe care îl are sortarea cu bule față de majoritatea celorlalți algoritmi, chiar și rapid, dar nu și sortare prin inserție, este că abilitatea de a detecta că lista este sortată eficient este integrat în algoritm. Când lista este deja sortată (cel mai bine caz), complexitatea sortării cu bule este doar O (n). În schimb, majoritatea celorlalți algoritmi, chiar și cei cu o complexitate mai bună a cazului mediu, își realizează întregul proces de sortare pe set și, prin urmare, sunt mai complexi. Cu toate acestea, sortarea prin inserție nu numai că împărtășește acest avantaj, dar are și o performanță mai bună pe o listă care este sortată substanțial (având un număr mic de inversiuni). În plus, dacă se dorește acest comportament, acesta poate fi adăugat în mod banal la orice alt algoritm verificând lista înainte ca algoritmul să ruleze.

Sortarea cu bule trebuie evitată în cazul colecțiilor mari. Nu va fi eficient în cazul unei colecții ordonate invers.

Iepuri și TurtlesEdit

Distanța și direcția pe care trebuie să le mute elementele în timpul sortării determină performanța sortării cu bule, deoarece elementele se deplasează în direcții diferite la viteze diferite. Un element care trebuie să se deplaseze spre sfârșitul listei se poate mișca rapid, deoarece poate lua parte la swapuri succesive. De exemplu, cel mai mare element din listă va câștiga fiecare swap, deci se mută la poziția sa sortată la prima trecere, chiar dacă începe aproape de început. Pe de altă parte, un element care trebuie să se deplaseze spre începutul listei nu se poate mișca mai repede decât un pas pe trecere, astfel încât elementele se deplasează spre început foarte încet. Dacă cel mai mic element se află la sfârșitul listei, va fi nevoie de n-1 treceri pentru a-l muta la început. Acest lucru a condus la aceste tipuri de elemente numite iepuri și, respectiv, broaște țestoase, după personajele din fabula lui Esop din Broasca testoasa si iepurele.

Diverse s-au făcut eforturi pentru a elimina broaștele țestoase pentru a îmbunătăți viteza sortării cu bule. Sortarea de cocktailuri este un tip de bule bidirecțional care merge de la început până la sfârșit, și apoi se inversează, mergând de la sfârșit la început. Poate mișca țestoasele destul de bine, dar păstrează complexitatea în cel mai rău caz O (n2). Sortarea pe pieptene compară elementele separate prin goluri mari și poate muta broaștele țestoase extrem de repede înainte de a trece la goluri din ce în ce mai mici pentru a netezi lista. Viteza sa medie este comparabilă cu algoritmi mai rapizi precum quicksort.

Exemplu pas cu pas Editați

Luați o matrice de numere „5 1 4 2 8” și sortați matricea din cea mai mică număr la cel mai mare număr folosind sortarea cu bule. În fiecare etapă, se compară elemente scrise cu caractere aldine. Vor fi necesare trei treceri;

Prima trecere (5 1 4 2 8) → (1 5 4 2 8), Aici, algoritmul compară primele două elemente și swapuri de la 5 > 1. (1 5 4 2 8) → (1 4 5 2 8), swap de la 5 > 4 (1 4 5 2 8) → (1 4 2 5 8), Schimb de la 5 > 2 (1 4 2 5 8) → (1 4 2 5 8), Acum, deoarece aceste elemente sunt deja în ordine (8 > 5), algoritmul nu le schimbă. A doua trecere (1 4 2 5 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 2 4 5 8), swap de la 4 > 2 ( 1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8)

Acum, matricea este deja sortată, dar algoritmul nu știe dacă este finalizat . Algoritmul are nevoie de o singură trecere fără niciun swap pentru a ști că este sortat.