Najlepsza odpowiedź
Przede wszystkim należy zapytać, po co używać algorytmu sortowania kwadratowego, skoro istnieją asymptotycznie szybsze alternatywy, takie jak scalanie lub quicksort. W przypadku małych tablic (mniej niż 20-30 elementów) zarówno sortowanie przez wstawianie, jak i sortowanie przez wybieranie są zwykle szybsze niż alternatywy O (n * logn). W rzeczywistości wiele algorytmów sortowania opartych na paradygmacie dziel i rządź przełącza się na sortowanie przez wstawianie lub sortowanie przez wybór, gdy tablica jest wystarczająco mała.
Między sortowaniem przez wstawianie a sortowaniem przez wybieranie, kiedy użyć którego?
Zwykle sortowanie przez wstawianie wykonuje mniej porównań niż sortowanie przez wybór, w zależności od stopnia „posortowania” tablicy. Podczas gdy sortowanie przez wybór musi skanować pozostałe części tablicy podczas umieszczania elementu, sortowanie przez wstawianie skanuje tylko tyle elementów, ile potrzeba. Oznacza to, że gdy tablica jest już posortowana lub prawie posortowana, sortowanie przez wstawianie wykonuje się w czasie O (n).
Jedną z zalet sortowania przez wybór nad sortowaniem przez wstawianie jest to, że liczba zapisów (zamian) jest równa O (n), podczas gdy w sortowaniu przez wstawianie jest w O (n ^ 2). Może to być ważne, jeśli na przykład sortujesz w pamięci Flash, ponieważ zapisy skracają żywotność pamięci Flash.
Odpowiedź
W sortowaniu przez wybór, dla każdego elementu, który ma zostać dodany do posortowanej sekcji, musisz przeskanować całą nieposortowaną część listy, aby znaleźć minimum pozostałych elementów. Podczas sortowania przez wstawianie musisz przeszukać sekcję posortowaną , aby dowiedzieć się, dokąd zmierza następny element, ale wyszukiwanie kończy się po znalezieniu punktu wstawiania (około połowy średnio przez posortowaną sekcję).
Tak więc sortowanie przez wybór wymaga średnio N / 2 porównań dla każdego elementu, który ma zostać dodany do posortowanej sekcji, a sortowanie przez wstawianie wymaga średnio N / 4 porównań. Jednak sortowanie przez wstawianie ma dodatkową karę czasową podczas sortowania tablicy. Każde z porównań N / 4 (średnio) wymaga przesunięcia elementu w górę, więc są również ruchy N / 4, a także porównania. Sortowanie przez wybieranie wymaga tylko jednej zamiany.
Ogólnie rzecz biorąc, sortowanie przez wstawianie zwykle wygrywa wyścig. Jest to szczególnie ważne, jeśli istnieją szybkie funkcje „przesuwania bloków” (dla tablic).