- Comparate
- Interschimbate
- La locul lor
Sortarea prin metoda bulelor
Metoda bulelor parcurge lista iar și iar, compară fiecare pereche de vecini și îi interschimbă când cel din stânga e mai mare. După fiecare trecere, cea mai mare valoare care nu e încă la locul ei urcă, precum o bulă, până la final. Redați sortarea la orice viteză sau parcurgeți-o câte o comparație și urmăriți contoarele de comparații, interschimbări și treceri. Apăsați Redare pentru a urmări sortarea sau Pas și Înapoi pentru a avansa câte o comparație. Trageți glisorul pentru pași ca să săriți oriunde. Casetele numără comparațiile, interschimbările și trecerile. Alegeți câte bare sunt, cum încep sau introduceți propriile numere. Cu tabla selectată, săgețile avansează câte un pas, bara de spațiu pornește și pune pauză, iar Home și End sar la început și la sfârșit.
Cum funcționează
- Alegeți câte bare sunt și cum încep: aleatoriu, aproape sortate, inversate sau cu puține valori distincte. Sau introduceți propriile numere.
- Apăsați Redare sau folosiți Pas și Înapoi ca să avansați câte o comparație. Trageți glisorul pentru pași ca să săriți oriunde în sortare.
- Urmăriți cum casetele numără comparațiile, interschimbările și trecerile și comparați-le cu cel mai rău caz.
Cum funcționează metoda bulelor
Începeți din stânga. Comparați primele două valori; dacă cea din stânga e mai mare, interschimbați-le. Mutați-vă o poziție la dreapta și comparați din nou, până la capătul listei. Aceasta e o trecere și lasă cea mai mare valoare pe ultimul loc. Următoarea trecere se oprește cu o poziție mai devreme. Continuați până când o trecere nu face nicio interschimbare sau rămâne o singură valoare.
Cât lucru presupune
Pentru n valori, prima trecere face n − 1 comparații, următoarea n − 2 și așa mai departe, deci o sortare completă face cel mult n(n − 1)/2 comparații. Numărul de interschimbări este mereu egal cu numărul de inversiuni din lista inițială: perechi de valori aflate în ordine greșită. O listă inversată are cele mai multe, n(n − 1)/2. O listă sortată nu are niciuna și, cu oprirea timpurie, necesită o singură trecere de n − 1 comparații.
Întrebări frecvente
De ce se numește metoda bulelor?
Pentru că valorile mari urcă spre capătul listei ca bulele în apă. La fiecare trecere, cea mai mare valoare care nu e încă la locul ei se mută pas cu pas spre dreapta până ajunge pe locul final.
Câte comparații și interschimbări face metoda bulelor?
Cel mult n(n − 1)/2 comparații pentru n valori: 45 pentru 10 valori, 780 pentru 40. Numărul de interschimbări este mereu egal cu numărul de inversiuni din lista inițială, de la zero pentru o listă sortată până la n(n − 1)/2 pentru una inversată.
Ce face oprirea timpurie?
Dacă o trecere întreagă nu face nicio interschimbare, toți vecinii sunt în ordine, deci lista e sortată și sortarea se poate opri. Cu oprirea timpurie activă, o listă sortată necesită o singură trecere. Fără ea, metoda bulelor face mereu toate cele n − 1 treceri.
Se folosește metoda bulelor în practică?
Rar. Este simplă și stabilă, dar în medie durează un timp proporțional cu n². Sortarea prin inserție face aceeași treabă în mai puțini pași pe liste scurte sau aproape sortate, iar sortarea prin interclasare și quicksort sunt mult mai rapide pe liste mari.
Numerele mele sunt trimise undeva?
Nu. Sortarea rulează în browserul dvs., iar ultimele setări rămân în stocarea locală a acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor