Beste antwoord
Allereerst moet men zich afvragen waarom een kwadratisch sorteeralgoritme wordt gebruikt als asymptotisch snellere alternatieven bestaan, zoals mergesort of quicksort. Voor kleine arrays (minder dan 20-30 elementen) zijn zowel invoegsortering als selectiesortering doorgaans sneller dan de O (n * logn) -alternatieven. In feite schakelen veel sorteeralgoritmen die gebaseerd zijn op het verdeel en heers-paradigma over naar invoegsortering of selectiesortering als de array klein genoeg is.
Wanneer moet je welke sortering tussen invoegsortering en selectiesortering gebruiken?
Gewoonlijk zal invoegsortering minder vergelijkingen uitvoeren dan selectiesortering, afhankelijk van de mate van “sortering” van de array. Terwijl selectiesortering de resterende delen van de array moet scannen bij het plaatsen van een element, scant invoegsortering alleen zoveel elementen als nodig is. Dat betekent dat wanneer de array al gesorteerd of bijna gesorteerd is, invoegsortering in O (n) -tijd wordt uitgevoerd.
Een voordeel van selectiesortering boven invoegsortering is dat het aantal schrijfbewerkingen (swaps) in O (n), terwijl het in invoegsortering in O (n ^ 2) staat. Dit kan belangrijk zijn als u bijvoorbeeld sorteert op Flash-geheugen, omdat schrijfbewerkingen de levensduur van Flash-geheugen verkorten.
Antwoord
Bij een selectie sorteert u voor elk element dat moet toegevoegd aan de gesorteerde sectie, moet u het volledige ongesorteerde deel van de lijst scannen om het minimaal resterende element te vinden. Bij een invoegsortering moet u in het gesorteerde gedeelte zoeken om erachter te komen waar het volgende element naartoe gaat, maar de zoekopdracht eindigt zodra u het invoegpunt hebt gevonden (ongeveer de helft gemiddeld door de gesorteerde sectie).
Dus voor het sorteren van selectie zijn gemiddeld N / 2 vergelijkingen vereist voor elk element dat aan de gesorteerde sectie moet worden toegevoegd en voor het sorteren van invoegingen zijn gemiddeld N / 4 vergelijkingen nodig. Invoegsortering heeft echter een extra tijdstraf bij het sorteren van een array. Elk van de N / 4 (gemiddeld) vergelijkingen vereist dat het element naar boven wordt verschoven, dus er zijn ook N / 4 bewegingen en vergelijkingen. Selectie sorteren vereist slechts een enkele omwisseling.
Over het algemeen wint invoegsortering meestal de race. Dit is vooral het geval als er snelle “blokverplaatsings” -functies zijn (voor arrays).