Алгоритмы сортировки.

Соpтиpовка Шелла.

Этот алгоритм - модификация сортировки простыми вставками.

Идея, например, в случае 16 чисел n₁ ... n₁₆ такова:

Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов (n₁, n₉), (n₂, n₁₀), ... , (n₈, n₁₆).

Потом сортируем каждую из четырех групп по 4 элемента (n₁, n₅, n₉, n₁₃), ..., (n₄, n₈, n₁₂, n₁₆). Далее сортируем 2 группы по 8 элементов, начиная с (n₁, n₃, n₅, n₇, n₉, n₁₁, n₁₃, n₁₅). А в конце сортируем вставками все 16 элементов.

Очевидно, лишь последняя сортировка необходима, чтобы расположить все элементы по своим местам. Так зачем нужны остальные ?

На самом деле они продвигают элементы максимально близко к соответствующим позициям, так что в последней стадии число перемещений будет весьма невелико. Они и так почти рассортированы.

Были проведены многочисленные исследования по вопросу, какова должна быть последовательность расстояний между сортируемыми элементами, в зависимости от прохода (инкремент).

Набор ..., 8, 4, 2, 1 - не хороший выбор, особенно, когда N - степень двойки. Гораздо лучше подойдет последовательность

Ее можно вычислить рекуррентно:

При этой последовательности количество операций даже в наихудшем случае - порядка N^3/2.

Для случайной последовательности при N < 60000 количество операций, приблизительно, N^1.25, однако при N > 50 QuickSort быстрее.

Исходник на Си.

void shell(unsigned long n, float a[])
{
    unsigned long i, j, inc; 
	float v; 
	inc=1;                             // начальный инкремент 
	do {
	    inc *=3; 
		inc++; 
	} while (inc <= n); 
	do {                               // Цикл частичных сортировок
	    inc /=3; 
		for (i=inc+1; i<=n; i++) {  // Внутренний цикл простых вставок
		    v=a[i]; 
			j=i; 
			while ( a[j-inc] > v) {
			    a[j] = a[j-inc]; 
				j -= inc; 
				if ( j <= inc ) break; 
			}
			a[j]=v; 
		}
	} while ( inc > 1 ); 
}

Вверх по странице, к оглавлению и навигации.