La ce este bun un sort cu bule? [închis] (Programare, Algoritm, Agnostic De Limbă, Sortare, Bubble Sort)

Jason Baker a intrebat.

Sortarea cu bule are vreo utilizare în lumea reală? De fiecare dată când văd unul menționat, este întotdeauna fie:

  1. Un algoritm de sortare pentru a învăța.
  2. Un exemplu de algoritm de sortare nu de utilizat.

16 răspunsuri
Remy Sharp

Depinde de modul în care sunt distribuite datele tale – dacă poți face unele presupuneri.

Unul dintre cele mai bune link-uri pe care le-am găsit pentru a înțelege când să folosiți o sortare cu bule – sau o altă sortare, este acesta – o vedere animată asupra algoritmilor de sortare:

http://www.sorting-algorithms.com/

Comentarii

  • Îmi place foarte mult această animație! Conform acesteia, se pare că sortarea în coajă este cea mai bună în general pentru dimensiunea 50. –  > Por lkessler.
  • aceste animații sunt grozave. un site grozav –  > Por Johannes Schaub – litb.
  • sorting-algorithms.com are și el câteva animații bune! –  > Por RCIX.
  • Știu că această întrebare este veche, dar link-ul este rupt… –  > Por Trufa.
  • @Trufa Link-urile funcționează acum. Mare resursă –  > Por Chen A..
Jerry Coffin

Sortarea cu bule este (în mod demonstrabil) cea mai rapidă sortare disponibilă sub o foarte circumstanțe specifice. Inițial, a devenit cunoscut în primul rând pentru că a fost unul dintre primii algoritmi (de orice fel) care a fost analizat riguros și s-a demonstrat că este optim în circumstanțele sale limitate.

Luați în considerare un fișier stocat pe o unitate de bandă și o memorie cu acces aleatoriu atât de mică (sau chei atât de mari) încât puteți încărca doar două înregistrări în memorie la un moment dat. Reîntoarcerea benzii este suficient de lentă pentru ca accesul aleatoriu în cadrul fișierului să fie în general nepractic – dacă este posibil, doriți să procesați înregistrările în mod secvențial, nu mai mult de două la un moment dat.

Pe vremea când unitățile de bandă erau obișnuite, iar mașinile cu doar câteva mii (cuvinte|bytes) de memorie RAM (de orice fel) erau obișnuite, acest lucru era suficient de realist pentru a merita să fie studiat. Această circumstanță este acum rară, astfel încât studierea tipului de bule nu are deloc sens – dar și mai rău, circumstanța în care este optimă nu este oricum predată, astfel încât, chiar și atunci când/dacă ar apărea situația potrivită, aproape nimeni nu ar face-o realiza de ea.

În ceea ce privește faptul de a fi cel mai rapid pe un set de date extrem de mic și/sau aproape sortat, deși acest lucru poate acoperi slăbiciunea sortării cu bule (cel puțin într-o oarecare măsură), o sortare prin inserție va fi în esență întotdeauna mai bună pentru oricare/ambele dintre acestea.

Comentarii

  • Dar dacă aveți la dispoziție o bandă în plus, o sortare prin îmbinare ar fi în continuare mai bună. –  > Por Mark Ransom.
  • @Mark: Oh, da – slăbiți aproape orice dintre restricții, și Bubblesort va pierde aproape întotdeauna, și de obicei destul de rău. –  > Por Jerry Coffin.
  • Ați putea să explicați mai detaliat exemplul cu unitatea de bandă? –  > Por gen.
  • @gen: Nu sunt sigur ce să adaug. Ce vi se pare neclar? –  > Por Jerry Coffin.
  • @gen Cred că limitarea definitorie este următoarea: sortarea cu bule este bună atunci când accesul secvențial este mult mai rapid decât accesul aleatoriu și puteți păstra doar două obiecte în memorie. Cu o unitate de bandă, este mecanic deja se deplasează secvențial, așa că ai putea la fel de bine să faci cât mai multă muncă în timp ce o face, fără a încetini/opri/întoarce mașina de bandă. –  > Por kibibu.
Bill Șopârla

Nu se folosește prea mult în lumea reală. Este un bun instrument de învățare, deoarece este ușor de înțeles și rapid de implementare. Are o performanță medie și în cel mai rău caz (O(n^2)). Are performanțe bune în cel mai bun caz atunci când știți că datele sunt aproape sortate, dar există o mulțime de alți algoritmi care au această proprietate, cu performanțe mai bune în cel mai rău caz și în medie.

Comentarii

  • De fapt, mi se pare uimitor faptul că sortarea cu bule este (adesea) predată înainte de sortarea prin inserție sau selecție. Ambele mi se par incredibil de intuitive. Dacă nu mă înșel, majoritatea oamenilor fac una sau alta atunci când sortează o carte de joc. Sortarea cu bule necesită un pic mai multă gândire. –  > Por Thomas Eding.
  • Acest lucru este foarte vechi, dar m-am gândit să arunc 5 cenți pentru oricine care dă peste acest comentariu cu 4 upvoted. Aveți dreptate în ceea ce privește inserția pe sortarea prin selecție, care este mai intuitivă decât încercarea de a face un elev să vadă o bulă care plutește într-un vector. Cu toate acestea, dacă elevii au puțină experiență în programare, un cod de 4 linii este mai ușor de explicat cartografiere de la cod la vizualizare sau abstractizare. Multe concepte de la invariantul bulelor pot trece, de exemplu, la un Sort de inserție. De exemplu, ideea unei frontiere care se deplasează de-a lungul primei bucle care împarte matricea în ordonată și încă de ordonat. –  > Por Oeufcoque Penteano.
  • Sortarea prin inserție este atât mai intuitivă, cât și mai practică decât alți algoritmi de sortare cu caz mediu O(n^2). De fapt, pentru liste mici, este CEL mai rapid algoritm. Iar oamenii îl folosesc și pentru a sorta cărți. –  > Por Xwtek.
  • Pentru a adăuga la comentariu. Din modul în care am învățat eu, sortarea cu bule, sortarea prin selecție și sortarea prin inserție sunt similare; toate O(N^2) în cel mai rău caz, dar fiecare este puțin mai bună decât cealaltă. Astfel, Bubble sort fiind cel mai rău, puteți vedea cum poate fi îmbunătățit puțin câte puțin, Insertion sort(când este sortat parțial în condiții normale) fiind de două ori mai rapid decât Bubble sort și puțin mai bun decât Selection sort. Sortarea prin inserție este predată înainte de sortarea rapidă, deoarece este utilizată la sfârșitul acesteia. Sortare cu bule = O(n^2) timp pentru comparații și schimburi, sortare prin selecție = O(n^2) pentru comparații, dar O(n) pentru schimburi. –  > Por eaglei22.
workmad3

Am dat recent peste o utilizare excelentă a acestuia într-o anecdotă de optimizare. Un program avea nevoie de un set de sprite sortate în ordine de adâncime în fiecare cadru. Ordinea spritelor nu s-ar schimba prea mult între cadre, așa că, ca o optimizare, acestea au fost sortate cu bule cu o singură trecere la fiecare cadru. Acest lucru s-a făcut în ambele direcții (de sus în jos și de jos în sus). Astfel, spritele au fost întotdeauna aproape ordonate cu un algoritm O(N) foarte eficient.

Comentarii

  • De fapt, sortarea prin inserție este încă mai bună pentru acest lucru. O mulțime de sisteme de redare în timp real utilizează sortarea prin inserție pentru liste foarte mari de lucruri, din motivul că lucrurile tind să fie „aproape” ordonate pentru fiecare cadru. Totuși, sortarea cu bule este foarte asemănătoare. –  > Por TM..
  • @TM Cred că ați ratat partea în care este două treceri fixe pe cadru. În cele din urmă se va rezolva, dar s-ar putea să dureze câteva (sute) de cadre. O singură trecere de sortare prin inserție pe cadru va asigura că primul (sau ultimul) element se află în locul potrivit. O bulă va face ca toate spritele să se deplaseze spre locul lor corect. –  > Por kibibu.
Cristian Libardo

Este probabil cel mai rapid pentru mici seturi.

Apropo de educație. Un link către ultima scenă din sortare de sortare, , este uimitoare. Un film care trebuie văzut neapărat.

Comentarii

  • Nu, nu este. Nu ar trebui să fie educat pentru programatorii începători, la fel ca și goto-urile. –  > Por Stephan Eggermont.
  • +1 pentru că m-a făcut să strig „GO QUICKSORT GO!” pentru prima dată în viața mea. –  > Por Juliet.
Arhetipul Paul

Este bun pentru seturi de date mici – motiv pentru care unele implementări qsort trec la el atunci când dimensiunea partiției devine mică. Dar sortarea prin inserție este în continuare mai rapidă, așa că nu există niciun motiv întemeiat pentru a o folosi, cu excepția unui ajutor didactic.

Tetha

am folosit recent bubblesort într-o demonstrație de optimalitate pentru un algoritm. A trebuit să transformăm o soluție optimă arbitrară reprezentată de o secvență de obiecte într-o soluție găsită de algoritmul nostru. Deoarece algoritmul nostru era doar „Sortează după acest criteriu”, a trebuit să demonstrăm că putem sorta o soluție optimă fără să o înrăutățim. În acest caz, sortarea cu bule a fost un algoritm foarte bun de utilizat, deoarece are invarianta plăcută de a schimba pur și simplu două elemente care sunt unul lângă celălalt și sunt în ordine greșită. Folosirea unor algoritmi mai complicați acolo ar fi topit creierele, cred.

Salutări.

Jay Conrod

Cred că este un bun algoritm „didactic” pentru că este foarte ușor de înțeles și de implementat. De asemenea, poate fi util pentru seturi mici de date din același motiv (deși unii dintre algoritmii O(n lg n) sunt și ei destul de ușor de implementat).

Brian

Nu mă pot abține să nu răspund la orice remarcă privind sortarea cu bule prin menționarea celui mai rapid (pare a fi O(nlogn), dar acest lucru nu este cu adevărat dovedit) Sortare în pieptene. Rețineți că Comb sort este un pic mai rapid dacă folosiți un tabel precalculat. Comb sort este exact la fel ca bubble sort, cu excepția faptului că nu începe inițial prin schimbarea elementelor adiacente. Este aproape la fel de ușor de implementat/înțeles ca și sortarea cu bule.

sergtk

Sortare cu bule este ușor de implementat și este suficient de rapid atunci când aveți seturi de date mici.

Bubble sort este suficient de rapid atunci când setul dvs. este aproape sortat (de exemplu, unul sau mai multe elemente nu se află în pozițiile corecte), în acest caz este mai bine să intercalați trecerile de la 0-index la n-index și de la n-index la 0-index.Folosind C++ poate fi implementat în felul următor:

void bubbleSort(vector<int>& v) { // sort in ascending order
  bool go = true;
  while (go) {
    go = false;
    for (int i = 0; i+1 < v.size(); ++i)
      if (v[i] > v[i+1]) {
         swap(v[i], v[j]);
         go = true;
      }
    for (int i = (int)v.size()-1; i > 0; --i) 
      if (v[i-1] > v[i]) {
         swap(v[i-1], v[i]);
         go = true;
      }
  }
}

Aceasta poate fi bună dacă schimbarea a două elemente adiacente este un cip, iar schimbarea unor elemente arbitrare este costisitoare.

Donald Knuth, în faimoasa sa lucrare „The Art of Computer Programming”, a concluzionat că „sortarea cu bule pare să nu aibă nimic care să o recomande, cu excepția unui nume atrăgător și a faptului că duce la unele probleme teoretice interesante.”.

Deoarece acest algoritm este ușor de implementat, este ușor de susținut, iar în ciclul de viață al aplicațiilor reale este important să se reducă efortul de susținere.

Comentarii

  • Nu este ușor de susținut. Orice programator real va simți un impuls aproape insurmontabil de a-l înlocui cât mai curând posibil 🙂 –  > Por Stephan Eggermont.
EvilTeach

Obișnuiam să îl folosesc în unele cazuri pentru N mici pe TRS-80 Model 1. Folosind o buclă for, se putea implementa sortarea completă pe o singură linie de program.

În afară de asta, este bun pentru predare și, uneori, pentru liste care sunt aproape în ordine sortată.

Mark Ransom

L-am folosit odată pentru un caz în care în marea majoritate a timpului ar fi sortat două elemente.

Data următoare când am văzut acel cod, cineva îl înlocuise cu cel din bibliotecă. Sper că au făcut mai întâi o analiză comparativă!

Comentarii

  • sortarea a două elemente? (a < b)? (swap):(do-not-swap)? –  > Por Lazer.
  • @Lazer, deși în majoritatea timpului era vorba de 2, tot trebuia să se ocupe de cazul în care erau mai mult de 2. În retrospectivă, aș fi putut să tratez acest lucru ca două cazuri diferite, cu cod diferit pentru fiecare dintre ele, și am fost sfătuit că sortarea din bibliotecă funcționează în general în acest fel oricum. –  > Por Mark Ransom.
Brian Knoblauch

Este rapid și ușor de codificat și (aproape imposibil de greșit). Își are locul dacă nu faceți muncă grea și nu există suport pentru sortare în bibliotecă.

buti-oxa

Este sortarea pe care o folosesc cel mai des, de fapt. (În proiectul nostru, nu putem folosi nicio bibliotecă externă).

Este util atunci când știu sigur că setul de date este foarte mic, deci nu-mi pasă deloc de viteză și vreau cel mai scurt și mai simplu cod.

Bubble nu este cel mai mic lucru pe care îl puteți face. Recent, am fost într-o situație în care trebuia să sortez exact trei elemente. Am scris ceva de genul acesta:

// Use sort of stooge to sort the three elements by cpFirst

SwapElementsIfNeeded(&elementTop, &elementBottom);
SwapElementsIfNeeded(&elementTop, &elementMiddle);
SwapElementsIfNeeded(&elementMiddle, &elementBottom);

*pelement1 = elementTop;
*pelement2 = elementMiddle;
*pelement3 = elementBottom;

Stephan Eggermont

O, da, este un mecanism de selecție bun. Dacă îl găsești în codul scris de cineva, nu-l angajezi.

Comentarii

  • Chiar dacă funcționează perfect în suitația specifică? –  > Por pierrotlefou.
  • Da. Dacă poți regla situația astfel încât bubblesort să fie răspunsul perfect, ar fi trebuit să poți regla situația astfel încât să nu fie. –  > Por Stephan Eggermont.
  • haha, am folosit deja acest criteriu pentru a respinge candidatul 🙂 –  > Por sergtk.
  • Incredibil, câte voturi negative primește acest lucru… –  > Por Stephan Eggermont.
  • @Stephan: Primește voturi negative (inclusiv al meu) pentru că regulile generale de genul acesta nu sunt doar prostești, sunt de-a dreptul… greșite. Bubblesort are nevoie de foarte puține instrucțiuni, în timp ce în multe cazuri este „suficient de rapid”. Cu siguranță nu aș angaja pe nimeni pentru un proiect încorporat care nu ar putea prevedea că aceste proprietăți sunt utile. –  > Por Nicholas Knight.
Thomas Hansen

În mare parte nimic. Utilizați QuickSort sau SelectionSort în schimb…!