De ce selecția este mai rapidă decât cea cu bule?

Toate complexitățile pe care le-ați furnizat sunt adevărate, cu toate acestea sunt date în notație O mare , deci toate valorile și constantele aditive sunt omise.

Pentru a răspunde la întrebarea dvs., trebuie să d să se concentreze pe o analiză detaliată a celor doi algoritmi. Această analiză poate fi făcută manual sau poate fi găsită în multe cărți. Voi folosi rezultatele din Arta programării computerizate a lui Knuth .

Numărul mediu de comparații:

• Sortare cu bule : $ \ frac {1} {2} (N ^ 2-N \ ln N – (\ gamma + \ ln2 -1) N) + \ mathcal O (\ sqrt N) $
• Sortare prin inserție : $ \ frac {1} {4} (N ^ 2-N) + N – H_N $
• Sortare selecție : $ (N + 1) H_N – 2N $

Acum, dacă trasați acele funcții, veți obține ceva de genul acesta:

După cum puteți vedea, sortarea cu bule este mult mai rea pe măsură ce numărul de elemente crește, chiar dacă ambele metode de sortare au același asimptotic complexitate.

Această analiză se bazează pe presupunerea că intrarea este aleatorie – ceea ce s-ar putea să nu fie adevărat tot timpul. Cu toate acestea, înainte de a începe sortarea, putem permuta aleatoriu secvența de intrare (folosind orice metodă) pentru a obține cazul mediu.

Am omis analiza complexității timpului, deoarece depinde de implementare, dar pot fi utilizate metode similare.

Comentarii

• Am o problemă cu ” putem permuta aleatoriu secvența de intrare pentru a obține un caz mediu „. De ce se poate face acest lucru mai repede decât timpul necesar pentru sortare?
• Puteți permuta orice succesiune de numere va dura $ N $ timp în care $ N $ este lungimea secvenței. Este ‘ evident că orice algoritm de sortare bazat pe comparație trebuie să aibă cel puțin $ \ mathcal O (N \ log N) $ complexitate, deci chiar dacă îi adăugați $ N $ ‘ complexitatea lui nu va fi ‘ modificată atât de mult. Oricum vorbim despre comparație, nu despre timp, complexitatea timpului depinde de implementare și de funcționarea mașinii, așa cum am menționat în răspuns.
• Cred că am avut somn, ai dreptate, secvența poate fi permutată în timp liniar .
• Deoarece $ H_N = \ Theta (jurnal N) $, comparația dvs. este legată corect pentru sortarea selecției? Se pare că ‘ înseamnă că faci în medie comparații O (n log n).
• Gamma = 0.577216 este Euler-Mascheroni ‘ constantă. Capitolul relevant este ” Arta programării ” vol 3 secțiunea 5.2.2 pag. 109 și 129. Cum ați trasat cazul de sortare a bulelor exact mai ales termenul O (sqrt (N))? Doar l-ați neglijat?

Costul asimptotic sau $ \ mathcal O $ -notație, descrie comportamentul limitativ al unei funcții, deoarece argumentul său tinde spre infinit, adică rata de creștere.

Funcția în sine, de ex. numărul de comparații și / sau swapuri poate fi diferit pentru doi algoritmi cu același cost asimptotic, cu condiția să crească cu aceeași rată.

Mai precis, sortarea cu bule necesită, în medie, $ n / 4 $ swap per intrare (fiecare intrare este mutată elementar din poziția sa inițială în poziția sa finală și fiecare swap implică două intrări), în timp ce Sortarea selecției necesită doar $ 1 $ (odată ce minimul / maximul a fost găsit, acesta este schimbat o dată până la sfârșitul matricei).

În ceea ce privește numărul de comparații, sortarea cu bule necesită comparații $ k \ ori n $, unde $ k $ este distanța maximă dintre poziția inițială a unei intrări și poziția sa finală, care este de obicei mai mare de $ n / 2 $ pentru valorile inițiale distribuite uniform. Sortarea selecției necesită totuși întotdeauna comparații $ (n-1) \ times (n-2) / 2 $.

În rezumat, limita asimptotică vă oferă o impresie bună asupra modului în care costurile unui algoritm cresc în raport cu dimensiunea intrării, dar nu spune nimic despre performanța relativă a diferiților algoritmi din același set.

Comentarii

• acesta este chiar un răspuns foarte bun
• ce carte preferați?
• @GrijeshChauhan: Cărțile sunt o chestiune de gust, așa că luați orice recomandare cu un bob de sare. Îmi plac personal Cormen, Leiserson și Rivest ‘ s ” Introducere în algoritmi „, ceea ce oferă o imagine de ansamblu bună cu privire la o serie de subiecte și Knuth ‘ s ” Arta programării computerizate ” serie dacă aveți nevoie de mai multe / toate detaliile cu privire la orice subiect specific. Poate doriți să verificați dacă întrebarea cărților a fost pusă aici înainte sau să postați această întrebare dacă nu a ‘ t.
• Pentru mine, al treilea paragraf din răspunsul tău este răspunsul propriu-zis. Nu graficele pentru intrări mari, date în alt răspuns.

Sortarea cu bule folosește mai mulți timpi de schimb, în timp ce sortarea selecției evită acest lucru.

Când se utilizează selectarea sortării, se schimbă cel mult n ori. dar atunci când utilizați sortarea cu bule, schimbă aproape n*(n-1). Și, evident, timpul de citire este mai mic decât timpul de scris chiar și în memorie. Timpul de comparare și celelalte durate de rulare pot fi ignorate. Deci, timpul de schimb este blocajul critic al problemei.

Comentarii

• Cred că celălalt răspuns al lui Bartek este mai rezonabil, dar nu pot ‘ să votez sau comentează … BTW Încă cred că timpul de scriere afectează mai mult și sper că poate lua în considerare acest lucru dacă vede acest lucru și este de acord.
• Nu puteți ignora pur și simplu numărul de comparații, deoarece există cazuri de utilizare în care timpul petrecut pentru a compara două articole poate depăși cu mult timpul petrecut pentru a schimba două articole. Luați în considerare o listă legată de șiruri extrem de lungi (să zicem 100k caractere fiecare). Citirea fiecărui șir ar dura mult mai mult decât efectuarea realocării indicatorului.
• @IrvinLim Cred că s-ar putea să aveți dreptate, dar este posibil să trebuiască să văd datele statistice înainte de a mă răzgândi.