2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Сортировка Шелла
Сообщение09.08.2012, 17:50 
Аватара пользователя
Здравствуйте! Объясните пожалуйста, что делает оператор 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;
             }
}

 
 
 
 Re: Сортировка Шелла
Сообщение09.08.2012, 18:26 
Аватара пользователя
Код:
j-=gap

Это короткая запись для
Код:
j=j-gap


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

А что с того?
Код:
for (1; 2; 3)

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

 
 
 
 Re: Сортировка Шелла
Сообщение09.08.2012, 18:37 
Аватара пользователя
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, и что будет тогда?

 
 
 
 Re: Сортировка Шелла
Сообщение09.08.2012, 18:47 
Аватара пользователя
Цитата:
Всмысле? Это для какого из циклов?

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

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

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

 
 
 
 Re: Сортировка Шелла
Сообщение09.08.2012, 19:23 
Аватара пользователя
Pavia в сообщении #604529 писал(а):
Выполнится следующая команда. А вот какая я бы хотел услышать от вас.

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

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

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

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

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

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


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

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group