Системы счисления

 

 

 

3-сортировки

1 3 2 4 7 6 5 11 10 9 8  14 13 12 18 17 16 15 

1 3 2 4 7 6 5 8  10 9 11 14 13 12 18 17 16 15 

1 3 2 4 7 6 5 8  10 9 11 14 13 12 15 17 16 18 

 

1-сортировка

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

 

N = 7, поэтому:

t= trunc(log 7) = 2

k= 22-1 = 3     {начнем с 3-сортировки}

p= 7 mod 3 = 1             {кол-во длинных подпоследовательностей}

s= (7 div 3)+1 = 3    {длина длинной подпоследовательности}

3-сортировки:

5 3 1 -> 1 3 5  {3 сдвига: 7 пересылок, 5 сравнений}

 

 

3 6   -> 3 6    {0 сдвигов: 0 пересылок, 1 сравнение}

4 2   -> 2 4 {1 сдвиг: 3 пересылки, 2 сравнения}

Всего 4 сдвига: 10 пересылок, 8 сравнений Итог 3-сортировок: 1 3 2 3 6 4 5

1-сортировка:

Состояние массива  Сдвиги  Сравнения  Пересылки данных

           

0 шаг:        1323645       

1 шаг:        1323645       0         1    0

2 шаг:        1323645       1        1+1   1+2

3 шаг:        1233645       0         1    0

4 шаг:        1233645       0         1    0

5 шаг:        1233645       1        1+1   1+2

6 шаг:        1233465       1       1+1   1+2

результат:    1233456       3         9    9

 

При сортировке методом  Шелла в сумме получилось 7 сдвигов (19 пересылок и 17 сравнений). Выигрыш  по сравнению с методом простых  вставок составляет 53% (24% экономится на пересылках и 15% - на сравнениях).

Кроме того, не нужно забывать, что в нашем примере последовательность очень коротка: N = 7. Для больших N (скажем, N = 10000) преимущество метода Шелла станет еще заметнее.

 
Используемая литература

 

1. Алексеев А.П. Информатика 2002. М.: Солон, 2002.- 400с.
2. Вирт Н. Систематическое программирование. Введение.-М.: Мир, 1977. [Метод пошагового уточнения].
3. Каймин В. Информатика. Учебник.-2-е изд. - М.: Инфра-М, 2001.
4. Книттель Брайан. Использование Microsoft Windows XP Professional. Специальное задание. / Книттель Брайан, Коварт Роберт. / пер. с англ. – М.: Издательский дом «Вильямс», 2004. -752 с.
5. Погорелов Г.З., Утюшев Р.Н., Моренис В.Е. Windows 95: Учебное пособие для студентов всех форм обучения / Красноярский гос. ун-т - Красноярск, 2001. 40 с.

 

 

 

Приложение А

Блок-схема сортировок