Записки программиста Программирование и не только

Сортировка Шелла

Начну собирать коллекцию алгоритмов.

Итак, прошу любить и жаловать: Сортировка Шелла (англ. Shell sort)

Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, идея которого состоит в сравнении элементов, стоящих не только рядом, но и на расстоянии друг от друга. Иными словами — сортировка вставками с предварительными «грубыми» проходами.

При сортировке Шелла сначала сравниваются и сортируются между собой ключи, отстоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть, обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки вставками или пузырьком (но она не предпочтительна, так как все равно остается медленной) каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, при сортировке Шелла же это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
- отсутствие потребности в памяти под стек
- отсутствие деградации при неудачных наборах данных — qsort легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла

Часто оказывается, что сортировка Шелла есть самый лучший способ сортировки до, примерно, 1000 элементов. (текст взят ЗДЕСЬ)

И собственноручно написанный боевой пример:

void shellSort(int kolEl, arr &mArray)
{
    int sub = kolEl/2;
	kolEl = kolEl-1;
    do
    {
        int i = sub;
        do
        {
            int j = i-sub;
            bool c = true;
            do
            {
                if(mArray.at(j) < = mArray.at(j+sub))
                {
                    c = false;
                }
                else
                {
			int tmp = mArray.at(j);
			mArray.at(j) = mArray.at(j+sub);
			mArray.at(j+sub) = tmp;
                }
                j = j-1;
            }
            while( (j >= 0) && (c) );
            i++;
        }
        while(i < = kolEl);
        sub = sub / 2;
    } while(sub > 0);
}

kolEl - Колличество элементов массива
arr &mArray - typedef vector <int> arr;