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

[Dosaev]

Здравствуйте! Объясните пожалуйста, что делает оператор j-=gap в третьем цикле for? Ведь j в таком случае может быть отрицательным?

Используется синтаксис C

void shellsort(int v[], int n)
{
     int gap, i, j, temp;
     
     for (gap = n/2; gap > 0; gap/=2)
         for (i = gap; i < n; i++)
             for (j = i - gap; j >= 0 && v[j]>v[j+gap]; j-=gap) {
                 temp = v[j];
                 v[j] = v[j+gap];
                 v[j+gap] = temp;
             }
}

[Pavia]

 j-=gap

Это короткая запись для

 j=j-gap

Цитата:

Ведь j в таком случае может быть отрицательным?

А что с того?

for (1; 2; 3)

когда выполняются части кода 1, 2 и 3?

[Dosaev]

Pavia в сообщении #604524 писал(а):

for (1; 2; 3)

когда выполняются части кода 1, 2 и 3?

Всмысле? Это для какого из циклов? Ну вообще 1: это начальное значение чего-нибудь, 2: это обычно условие, при котором цикл выполняется, 3: обычно шаг цикла или какое-нибудь другое действие.

Pavia в сообщении #604524 писал(а):

А что с того?

Ну вот сначала j = i - gap, а до этого i = gap, тогда j = 0, и пусть условие v[j] > v[j+gap] верно, тогда j = j - gap = 0 - gap. А gap > 0, и что будет тогда?

[Pavia]

Цитата:

Всмысле? Это для какого из циклов?

Для любого цикла. Если вас смущает слово "когда", спрошу по другому "где"?

Цитата:

и что будет тогда?

Выполнится следующая команда. А вот какая я бы хотел услышать от вас.

[Dosaev]

Pavia в сообщении #604529 писал(а):

Выполнится следующая команда. А вот какая я бы хотел услышать от вас.

Проверится условие j>= 0 и оно будет неверным, значит будет работать второй цикл for, где i увеличится на единицу? Но почему именно j-=gap? Не понимаю смысл этого действия.

[Pavia]

Dosaev
Тогда я вам советую начать читать Кнута. Искусство программирования.
5.2.1 Метод Шелла
Если кратко, то так.
Вначале рассмотрим кратко сортировку вставками.
Берём массив. Заводим второй массив. Будем брать элементы из первого и вставлять во второй.
Это без труда вы сделаете. А теперь усложним задачу сортировка должна идти без использования дополнительной памяти. Это не сложно сделать если совместить сравнение с перестановкой элементов. И расположить оба массива друг за другом.
Про анализируем скорость вставки. При таком подходе нам придётся перебирать массив в который вставляем элемент за элементом. В среднем это порядка 1/2*N операций для вставки. (странно у Кнута 1/3*N). И того сортировка будет пропорциональна N^2.

Ясно что с этим что-то надо делать. Мы можем для поиска использовать бинарный поиск, но для вставки нам потребуется сместить все элементы. Что не даёт выигрыша.

Но оказывается выигрышь можно получить для средней величины.
Разобьём массив на несколько групп к примеру на 2 группы (A1,A1,...)(...,An-1,An). И будем перемещать элементы из первой во вторую. Тем самым мы видим экономию нам не нужно проверять последовательно все элементы.
А теперь разобьем на 4 группы. Если мы будем делать перемещения внутри групп, то выигрыша нам не видать отсюда понятно что перемещения надо вести между группами. Поэтому в 3 цикле и используется
gap который определяет размер группы.

Что бы это всё понять вы должны сами подумать как сконструировать такой алгоритм.

[Dosaev]

Pavia в сообщении #604565 писал(а):

Разобьём массив на несколько групп к примеру на 2 группы (A1,A1,...)(...,An-1,An). И будем перемещать элементы из первой во вторую. Тем самым мы видим экономию нам не нужно проверять последовательно все элементы.
А теперь разобьем на 4 группы. Если мы будем делать перемещения внутри групп, то выигрыша нам не видать отсюда понятно что перемещения надо вести между группами. Поэтому в 3 цикле и используется
gap который определяет размер группы.

Да спасибо, я вроде как понял.
Это становится ясным после второго уменьшения шага gap = n/4. А вначале, когда две группы (половины), просто идет перемещение элементов из одной половины в другую.