Paras vastaus
Ensinnäkin on kysyttävä, miksi käytetään asteen lajittelualgoritmia, kun asymptoottisesti nopeammat vaihtoehdot ovat olemassa, kuten mergesort tai pikalajitelma. Pienille matriiseille (alle 20-30 elementtiä) sekä lisäys- että valintalajittelu ovat tyypillisesti nopeampia kuin O (n * logn) -vaihtoehdot. Itse asiassa monet jakamis- ja valloitusparadigmaan perustuvat lajittelualgoritmit siirtyvät lisäyslajitteluun tai valintalajitteluun, kun taulukko on riittävän pieni.
Milloin käyttää lisäyslajittelun ja valintalajittelun välillä?
Yleensä lisäyslajittelu tekee vähemmän vertailuja kuin valintalajittelu, taulukon ”lajitteluperusteesta” riippuen. Valintalajittelun on skannattava matriisin jäljellä olevat osat laitettaessa elementtiä, lisäyslajittelu skannaa vain niin monta elementtiä kuin tarvitaan. Tämä tarkoittaa, että kun taulukko on jo lajiteltu tai melkein lajiteltu, lisäyslajittelu suoritetaan O (n) -ajalla.
Yksi valintalajittelun etu verrattuna lisäyslajitteluun on, että kirjoitusmäärä on O (n), kun taas lisäyslajittelussa se on O: ssa (n ^ 2). Tämä voi olla tärkeää, jos lajittelet esimerkiksi Flash-muistia, koska kirjoitukset lyhentävät Flash-muistin käyttöikää.
Vastaa
Valintajärjestyksessä jokaiselle elementille, joka on Jos haluat lisätä lajiteltuun osioon, sinun on skannattava luettelon koko lajittelematon osa löytääksesi jäljellä olevan vähimmäisosan. Lisälajittelussa sinun on haettava lajiteltu -osiosta saadaksesi selville, mihin seuraava elementti menee, mutta haku päättyy, kun olet löytänyt lisäyskohdan (noin puolet keskimäärin läpi lajitellun osan).
Joten valintalajittelu edellyttää keskimäärin N / 2 vertailua jokaiselle elementille, joka lisätään lajiteltuun osioon, ja lisäyslajittelu vaatii keskimäärin N / 4 vertailua. Lisälajittelulla on kuitenkin ylimääräinen aikaraja taulukon lajittelussa. Jokainen N / 4 (keskimäärin) vertailu vaatii elementin siirtämistä ylöspäin, joten siellä on myös N / 4 siirtoa sekä vertailuja. Valintalajittelu vaatii vain yhden vaihdon.
Kaiken kaikkiaan lisäyslaji voittaa kilpailun. Tämä pätee erityisesti, jos (lohkojen) ympärillä on nopeita ”lohkonsiirtotoimintoja”.