Системы счисления
Автор работы: Пользователь скрыл имя, 01 Октября 2013 в 09:11, курсовая работа
Краткое описание
В последние годы произошла компьютерная революция, затронувшая все сферы социальной, культурной и научной деятельности человека. Эта компьютерная революция ещё не завершена и недавно вошла в новый этап, связанный с Интернетом. В связи с быстрым развитием компьютерной техники скоро в мире не останется людей, которых бы не затронула компьютерная революция.
Прикрепленные файлы: 1 файл
курсак.doc
— 347.00 Кб (Скачать документ)
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) преимущество метода Шелла станет еще заметнее.
Используемая литература
- Алексеев А.П. Информатика 2002. М.: Солон, 2002.- 400с.
- Вирт Н. Систематическое программирование. Введение.-М.: Мир, 1977. [Метод пошагового уточнения].
- Каймин В. Информатика. Учебник.-2-е изд. - М.: Инфра-М, 2001.
- Книттель Брайан. Использование Microsoft Windows XP Professional. Специальное задание. / Книттель Брайан, Коварт Роберт. / пер. с англ. – М.: Издательский дом «Вильямс», 2004. -752 с.
- Погорелов Г.З., Утюшев Р.Н., Моренис В.Е. Windows 95: Учебное пособие для студентов всех форм обучения / Красноярский гос. ун-т - Красноярск, 2001. 40 с.
Приложение А
Блок-схема сортировок