Shell Sort

Algorytm ten został zaproponowany przez Donalda Shella w 1959 roku. Jest to najszybszy algorytm sortujący w klasie O(n2). Idea jest następująca: Shell zauważył, iż algorytm sortowania przez wstawianie (insertion sort) jest bardzo efektywny, gdy zbiór jest już w dużej części uporządkowany. Wtedy złożoność obliczeniowa jest prawie liniowa - O(n). Jednakże algorytm ten nieefektywnie przestawia elementy w trakcie sortowania - ponieważ porównywane są kolejne elementy na liście uporządkowanej, to ulegają one przesunięciu tylko o jedną pozycję przy każdym obiegu pętli wewnętrznej. Shell wpadł na pomysł modyfikacji algorytmu sortowania przez wstawianie tak, aby porównywane były na początku elementy odległe od siebie, a później ta odległość malała i w końcowej fazie powstawałby zwykły algorytm sortowania przez wstawianie, lecz ze zbiorem jest już w dużym stopniu uporządkowanym.

Osiągnął to dzieląc w każdym obiegu zbiór na odpowiednią liczbę podzbiorów, których elementy są od siebie odległe o stałą odległość g. Następnie każdy z podzbiorów jest sortowany za pomocą sortowania przez wstawianie. Powoduje to częściowe uporządkowanie zbioru. Dalej odległość g jest zmniejszana (najczęściej o połowę), znów są tworzone podzbiory (jest ich teraz mniej) i następuje kolejna faza sortowania. Operacje te kontynuujemy aż do momentu, gdy odległość g osiągnie wartość 0. Wtedy zbiór wyjściowy będzie uporządkowany.

Zasadniczym czynnikiem wpływającym na efektywność algorytmu sortowania metodą Shella jest odpowiedni dobór ciągu kolejnych odstępów. Shell zaproponował przyjęcie na początku odstępu równego połowie liczby elementów w zbiorze, a następnie zmniejszanie tego odstępu o połowę przy każdym obiegu pętli. Nie jest to najbardziej efektywne rozwiązanie, jednak najprostsze w implementacji. Dlatego będziemy z niego korzystać.