|
|
Sortowanie przez wstawianie
|
Ważne definicje:
Algorytmy sortowania:
|
Algorytm ten jest usprawnieniem sortowania przez wstawianie, polegającym na tym, że do wyszukania pozycji dla elementu wstawianego do ciągu uporządkowanego, stosowany jest algorytm wyszukiwania binarnego. Dzięki temu usprawnieniu algorytm sortowania przez wstawianie osiąga efektywność zbliżoną do efektywności najlepszych algorytmów sortowania. Należy jednak pamiętać, że chociaż algorytm ten jest bardzo efektywny ze względu na liczbę wykonywanych porównań, to jednak operacja wstawienia elementu do ciągu uporządkowanego powoduje przesunięcie tej części elementów, które są większe od wstawianego. Jeżeli sortowanie odbywa się w tablicy, to takie przesunięcie generuje dużą liczbę zamian elementów miejscami - w sumie rzędu n2. Ponieważ w poniższej demonstracji główny nacisk jest położony na operacje porównania, algorytm osiąga wydajność porównywalną lub lepszą z efektywnością algorytmów sortowania szybkiego i sortowania stogowego. Praktycznie jednak duża liczba zamian zmienia nieco ten obraz.
|
Sortowanie przez wstawianie (z binarnym wyszukiwaniem)
Strona główna Sortowanie bąbelkowe Sortowanie przez wstawianie Sortowanie przez binarne wstawianie Sortowanie przez wybór Sortowanie przez scalanie Sortowanie przez scalanie - rozszerzone Sortowanie szybkie Sortowanie stogowe Sortowanie stogowe rozszerzone Porównanie algorytmów
