Сортировка Шелла, оптимальный выбор приращений

Сортировка Шелла, оптимальный выбор приращений

Aвтор:this
Дата: 19.11.2002
Просмотров: 198045
реализации(C++: 4шт...) +добавить

[Если вы не знакомы с сортировкой Шелла как таковой, то быстрей прочитайте задачу сортировка Шелла, общий принцип]

Приращение в сортировке Шелла - это расстояние между сортируемыми элементами динамически меняющееся на каждом проходе. Главное требование, чтобы на последней итерации оно было равно 1. Динамика изменения этой величины очень существенно сказывается на производительности алгоритма в целом.

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

Например, Р. Седжвик, предложил такую схему вычисления прирашений:
d[i] = 9*2ⁱ - 9*2^i/2 + 1, если i четно
d[i] = 8*2ⁱ - 6*2^(i+1)/2 + 1, если i нечетно

Было доказано, что используя эту схему производительность алгоритма возрастает ~ O(n^7/6) в среднем и до ~ O(n^4/3) в худшем случае. При расчете приращений по этому методу останавливаться следует на значении d[i-1], если 3*d[i] > n. Обычно расчет начинается с нулевых значений i(=[0,1,2...]) и продолжается до такого i, когда 3*d[i+1] > n, как было сказано ранее. Т.о. данная процедура рассчета запускается перед самой сортировкой Шелла и затем хранит полученную таблицу приращений в памяти, а алгоритм сортировки на каждом шаге к ней обращается за очередным значением.

Например, пусть имеем последовательность из n=35 элементов. Тогда:
Dsedj[0] = 1, Dsedj[1] = 5, Dsedj[2] = 19. Поскольку 3*19 > 35, останавливаемся на значении 5, получая последовательность приращений для данного n=35:[1,5]. Т.е. всего лишь 1 и 5. В базовой реализации мы бы имели:[17, 8, 4, 2, 1].

Алгоритм расчета приращений Седжвика будет иметь вид:

псевдокод: расчет приращений шелла методом Р. Седжвика ссылка

p1 = p2 = p3 = 1
i = -1;
loop
  if (++i % 2) 
    d[i] = 8*p1 - 6*p2 + 1
  else
    d[i] = 9*p1 - 9*p3 + 1
    p2 *= 2
    p3 *= 2
 
  p1 *= 2
  if 3*d[i] >= n
    break
 
if i > 0
  return --i
 
return 0

p1 = p2 = p3 = 1
i = -1;
loop
  if (++i % 2) 
    d[i] = 8*p1 - 6*p2 + 1
  else
    d[i] = 9*p1 - 9*p3 + 1
    p2 *= 2
    p3 *= 2
  
  p1 *= 2
  if 3*d[i] >= n
    break

if i > 0
  return --i

return 0

Cуществует другое мнение: для достаточно больших массивов рекомендуемой можно считать последовательность таких d_i, что:
d_i+1 = 3d_i + 1;
т.е., последовательность включает по порядку приращения: ..., 364, 121, 40, 13, 4, 1. Начинается процесс с d_m-2, где m - наименьшее целое, такое, что d_m >= n;

Для нашего случая с n=35 получим: d=[1,4], поскольку h₃=40 > n=35 => i_max = 3-1 = 1

Алгоритм рассчета таких приращений имеет вид:

псевдокод: рассчет приращений оптимальных для больших сортируемых последовательностях ссылка

i    = 0
d[0] = 1
 
while (d[i] < n)
  i++
  d[i] = 3*d[i-1] + 1
 
if i < 2
  return 0
 
return i-2

i    = 0
d[0] = 1

while (d[i] < n)
  i++
  d[i] = 3*d[i-1] + 1

if i < 2
  return 0

return i-2

Реализации:

C++(4) +добавить

1) Сортировка Шелла с приращениями по Седжвику и последним "пузырьковом" проходе на C++, code #20[автор:this]

Сортировка Шелла при оптимальном выборе приращений по Седжвику и последнем "пузырьковом" проходе ссылка |режим:

/* Рассчитывает последовательность
   приращений по методу Р. Седжвика*/
int Dsedj(int d[], long n) {
    int p1, p2, p3, i;
 
    p1 = p2 = p3 = 1;
    i = -1;
    do {
        if (++i % 2) {
            d[i] = 8*p1 - 6*p2 + 1;
        } else {
            d[i] = 9*p1 - 9*p3 + 1;
            p2 *= 2;
            p3 *= 2;
        }
        p1 *= 2;
    } while(3*d[i] < n);  
 
    return (i > 0) ? --i : 0;
}
 
/* Сортировка Шелла */
template<class T>
void ShellSortDSedj1(T* x) {
    /* максимальное количество рассчитываемых
       приращений = 20 */
    int d, i, j, dseq[20];
    int di;
 
    /* Рассчитываем последовательность
       приращений */
    di = Dsedj(dseq, n);
 
    while (di >= 0) {
        /* Приращение на данном шаге */
        d = dseq[di--];
 
        /* этот цикл делает проход "пузырька" в том числе и
           для последней последовательности, когда d=1, поэтому
           вызывать в конце InsertSort или какую-либо другую
           элементарную сортировку - не требуется */
        for (i = d; i < n; i++) {
            T tmp = x[i];
            for (j = i-d; (j >= 0) && (x[j] > tmp); j -= d) {
                x[j+d] = x[j];
            }
            x[j+d] = tmp;
        }
    }
    /* Не требуется вызывать InsertSort или BubbleSort
       т.е. ко всей последовательности во вложенном цикле
       уже был применен метод пузырька */
}

/* Рассчитывает последовательность
   приращений по методу Р. Седжвика*/
int Dsedj(int d[], long n) {
    int p1, p2, p3, i;

    p1 = p2 = p3 = 1;
    i = -1;
    do {
        if (++i % 2) {
            d[i] = 8*p1 - 6*p2 + 1;
        } else {
            d[i] = 9*p1 - 9*p3 + 1;
            p2 *= 2;
            p3 *= 2;
        }
        p1 *= 2;
    } while(3*d[i] < n);  

    return (i > 0) ? --i : 0;
}

/* Сортировка Шелла */
template<class T>
void ShellSortDSedj1(T* x) {
    /* максимальное количество рассчитываемых
       приращений = 20 */
    int d, i, j, dseq[20];
    int di;

    /* Рассчитываем последовательность
       приращений */
    di = Dsedj(dseq, n);

    while (di >= 0) {
        /* Приращение на данном шаге */
        d = dseq[di--];

        /* этот цикл делает проход "пузырька" в том числе и
           для последней последовательности, когда d=1, поэтому
           вызывать в конце InsertSort или какую-либо другую
           элементарную сортировку - не требуется */
        for (i = d; i < n; i++) {
            T tmp = x[i];
            for (j = i-d; (j >= 0) && (x[j] > tmp); j -= d) {
                x[j+d] = x[j];
            }
            x[j+d] = tmp;
        }
    }
    /* Не требуется вызывать InsertSort или BubbleSort
       т.е. ко всей последовательности во вложенном цикле
       уже был применен метод пузырька */
}

Реализует алгоритм сортировки Шелла.
Значения приращений рассчитываются одним из самых оптимальных способов: методом Р. Седжвика.
Следует обратить внимание на то, что этот алгоритм является также интересной вариацией алгоритмов Шелла: в конце не нужно ко всей последовательности применять какую-либо элементарную сортировку(вставкой, выбором, пузырьком и проч.), поскольку внутренний цикл осуществляет проход пузырькового метода в том числе и для конечной последовательности, когда d=1.

Производительность: от ~O(n^4/3), до ~O(n^7/6)
Расход памяти: ~ O(n), тратится на хранения рассчитанных значений приращений конечно.

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

2) Сортировка Шелла с приращениями для больших размерностей и последним "пузырьковом" проходе на C++, code #21[автор:this]

Сортировка Шелла c приращениями для больших сортируемых массивов и последнем "пузырьковом" проходе ссылка |режим:

/* Рассчитывает последовательность
   приращений рекомендуюмую при больших
   размерах сортируемой последовательности */
int DForBigN(int d[], long n) {
    int i = 0;
    d[i] = 1;
 
    do {
        i++;
        d[i] = 3*d[i-1] + 1;
    } while (d[i] < n);
 
    return (i < 2) ? 0 : i-2;
}
 
 
 
template<class T>
void ShellSortDForBigN(T* x) {
    /* максимальное количество рассчитываемых
       приращений = 20 */
    int d, i, j, dseq[20];
    int di;
 
    /* Рассчитываем последовательность
       приращений */
    di = DForBigN(dseq, n);
 
    while (di >= 0) {
        /* Приращение на данном шаге */
        d = dseq[di--];
 
        /* этот цикл делает проход "пузырька" в том числе и
           для последней последовательности, когда d=1, поэтому
           вызывать в конце InsertSort или какую-либо другую
           элементарную сортировку - не требуется */
        for (i = d; i < n; i++) {
            T tmp = x[i];
            for (j = i-d; (j >= 0) && (x[j] > tmp); j -= d) {
                x[j+d] = x[j];
            }
            x[j+d] = tmp;
        }
    }
    /* Не требуется вызывать InsertSort или BubbleSort
       т.е. ко всей последовательности во вложенном цикле
       уже был применен метод пузырька */
}

/* Рассчитывает последовательность
   приращений рекомендуюмую при больших
   размерах сортируемой последовательности */
int DForBigN(int d[], long n) {
    int i = 0;
    d[i] = 1;

    do {
        i++;
        d[i] = 3*d[i-1] + 1;
    } while (d[i] < n);

    return (i < 2) ? 0 : i-2;
}



template<class T>
void ShellSortDForBigN(T* x) {
    /* максимальное количество рассчитываемых
       приращений = 20 */
    int d, i, j, dseq[20];
    int di;

    /* Рассчитываем последовательность
       приращений */
    di = DForBigN(dseq, n);

    while (di >= 0) {
        /* Приращение на данном шаге */
        d = dseq[di--];

        /* этот цикл делает проход "пузырька" в том числе и
           для последней последовательности, когда d=1, поэтому
           вызывать в конце InsertSort или какую-либо другую
           элементарную сортировку - не требуется */
        for (i = d; i < n; i++) {
            T tmp = x[i];
            for (j = i-d; (j >= 0) && (x[j] > tmp); j -= d) {
                x[j+d] = x[j];
            }
            x[j+d] = tmp;
        }
    }
    /* Не требуется вызывать InsertSort или BubbleSort
       т.е. ко всей последовательности во вложенном цикле
       уже был применен метод пузырька */
}

Реализует алгоритм сортировки Шелла.
Значения приращений рассчитываются методом, рекомендуемым при больших размерностях сортируемой последовательности.
Следует обратить внимание на то, что этот алгоритм является также интересной вариацией алгоритмов Шелла: в конце не нужно ко всей последовательности применять какую-либо элементарную сортировку(вставкой, выбором, пузырьком и проч.), поскольку внутренний цикл осуществляет проход пузырькового метода в том числе и для конечной последовательности, когда d=1.

Производительность: точно не оценивалась, но значительно быстрее чем ~O(n²)
Расход памяти: ~ O(n), тратится на хранения рассчитанных значений приращений конечно.

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

3) Модификация базовой сортировки Шелла с приращениями по методу Р. Седжвика на C++, code #22[автор:this]

Модификация базовой сортировки Шелла с приращениями по методу Р. Седжвика ссылка |режим:

template<class T>
void swap(T* x, int i, int j) {
    T tmp;
    tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}
 
/* Рассчитывает последовательность
   приращений по методу Р. Седжвика */
int Dsedj(int d[], long n) {
    int p1, p2, p3, i;
 
    p1 = p2 = p3 = 1;
    i = -1;
    do {
        if (++i % 2) {
            d[i] = 8*p1 - 6*p2 + 1;
        } else {
            d[i] = 9*p1 - 9*p3 + 1;
            p2 *= 2;
            p3 *= 2;
        }
        p1 *= 2;
    } while(3*d[i] < n);  
 
    return (i > 0) ? --i : 0;
}
 
/* Сортировка Шелла */
template<class T>
void BaseShellSortDSedj(T* x) {
    /* максимальное количество рассчитываемых
       приращений = 20 */
    int d, i, j, dseq[20];
    int di;
 
    /* Рассчитываем последовательность
       приращений */
    di = Dsedj(dseq, n);
    while (di > 0) {
        /* Приращение на данной итерации */
        d = dseq[di--];
        int i = 0, j = 0;
 
        /* Делает проход пузырька для групп
           пока расстояние между сортируемыми
           элементами не станет = 1 */
        while (j = i + d < n) {
            if (x[i] > x[j]) {
                swap(x, i, j);
            }
            i++;
        }
    }
    /* Заключительная элементарная сортировка
       полученной последовательности из 2-х 
       отсортированных групп */
    InsertSort(x);
}

template<class T>
void swap(T* x, int i, int j) {
    T tmp;
    tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}

/* Рассчитывает последовательность
   приращений по методу Р. Седжвика */
int Dsedj(int d[], long n) {
    int p1, p2, p3, i;

    p1 = p2 = p3 = 1;
    i = -1;
    do {
        if (++i % 2) {
            d[i] = 8*p1 - 6*p2 + 1;
        } else {
            d[i] = 9*p1 - 9*p3 + 1;
            p2 *= 2;
            p3 *= 2;
        }
        p1 *= 2;
    } while(3*d[i] < n);  

    return (i > 0) ? --i : 0;
}

/* Сортировка Шелла */
template<class T>
void BaseShellSortDSedj(T* x) {
    /* максимальное количество рассчитываемых
       приращений = 20 */
    int d, i, j, dseq[20];
    int di;
    
    /* Рассчитываем последовательность
       приращений */
    di = Dsedj(dseq, n);
    while (di > 0) {
        /* Приращение на данной итерации */
        d = dseq[di--];
        int i = 0, j = 0;

        /* Делает проход пузырька для групп
           пока расстояние между сортируемыми
           элементами не станет = 1 */
        while (j = i + d < n) {
            if (x[i] > x[j]) {
                swap(x, i, j);
            }
            i++;
        }
    }
    /* Заключительная элементарная сортировка
       полученной последовательности из 2-х 
       отсортированных групп */
    InsertSort(x);
}

Модификация базового алгоритма сортировки Шелла.
Значения приращений рассчитываются методом Р. Седжвика

Производительность: от ~ O(n^4/3) до ~ O(n^7/6)
Расход памяти: ~ O(n), тратится на хранение последовательности рассчитанных значений приращений конечно.

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

4) Модификация базовой сортировки Шелла с приращениями для больших N на C++, code #23[автор:this]

Модификация базовой сортировки Шелла с приращениями рекомендуемыми для больших сортируемых последовательностях ссылка |режим:

template<class T>
void swap(T* x, int i, int j) {
    T tmp;
    tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}
 
/* Рассчитывает последовательность
   приращений рекомендуюмую при больших
   размерах сортируемой последовательности */
int DForBig2(int d[], long n) {
    int i = 0;
    d[i] = 1;
 
    do {
        i++;
        d[i] = 3*d[i-1] + 1;
    } while (d[i] < n);
 
    return (i < 2) ? 0 : i-2;
}
 
/* Сортировка Шелла */
template<class T>
void BaseShellSortDForBigN(T* x) {
    /* максимальное количество рассчитываемых
       приращений = 20 */
    int d, i, j, dseq[20];
    int di;
 
    /* Рассчитываем последовательность
       приращений */
    di = DForBigN(dseq, n);
    while (di > 0) {
        /* Приращение на данной итерации */
        d = dseq[di--];
        int i = 0, j = 0;
 
        /* Делает проход пузырька для групп
           пока расстояние между сортируемыми
           элементами не станет = 1 */
        while (j = i + d < n) {
            if (x[i] > x[j]) {
                swap(x, i, j);
            }
            i++;
        }
    }
    /* Заключительная элементарная сортировка
       полученной последовательности из 2-х 
       отсортированных групп */
    InsertSort(x);
}

template<class T>
void swap(T* x, int i, int j) {
    T tmp;
    tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}

/* Рассчитывает последовательность
   приращений рекомендуюмую при больших
   размерах сортируемой последовательности */
int DForBig2(int d[], long n) {
    int i = 0;
    d[i] = 1;

    do {
        i++;
        d[i] = 3*d[i-1] + 1;
    } while (d[i] < n);

    return (i < 2) ? 0 : i-2;
}

/* Сортировка Шелла */
template<class T>
void BaseShellSortDForBigN(T* x) {
    /* максимальное количество рассчитываемых
       приращений = 20 */
    int d, i, j, dseq[20];
    int di;
    
    /* Рассчитываем последовательность
       приращений */
    di = DForBigN(dseq, n);
    while (di > 0) {
        /* Приращение на данной итерации */
        d = dseq[di--];
        int i = 0, j = 0;

        /* Делает проход пузырька для групп
           пока расстояние между сортируемыми
           элементами не станет = 1 */
        while (j = i + d < n) {
            if (x[i] > x[j]) {
                swap(x, i, j);
            }
            i++;
        }
    }
    /* Заключительная элементарная сортировка
       полученной последовательности из 2-х 
       отсортированных групп */
    InsertSort(x);
}

Модификация базового алгоритма сортировки Шелла.
Значения приращений рассчитываются методом, рекомендуемым при больших размерностях сортируемой последовательности.

Производительность: точно не определена, но значительно быстрее чем ~ O(n²)
Расход памяти: ~ O(n), тратится на хранение последовательности рассчитанных значений приращений конечно.

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

<< назад наверх

*	можно кириллицей (недопустимые символы:?&+=\/%#)
**	только для зарегистрированных пользователей

Популярные задачи:

Сортировка Шелла, оптимальный выбор приращений

Реализации: