Дипломная работа

от 20 дней
от 9999 рублей

Заказать

Курсовая работа

от 10 дней
от 1999 рублей

Заказать

Реферат

от 3 дней
от 699 рублей

Заказать

Контрольная работа

от 3 дней
от 99 рублей
за задачу

Заказать

Диссертация

Сроки и стоимость индивидуальные

Заказать

Главная - Информатика - Курсовой проект.

Курсовой проект. Информатика. Курсовая

  • Тема: Курсовой проект.
  • Автор: Юлия
  • Тип работы: Курсовая
  • Предмет: Информатика
  • Страниц: 21
  • Год сдачи: 2008
  • ВУЗ, город: МГВРК
  • Цена(руб.): 1500 рублей

Заказать персональную работу

Выдержка

Hачать построение пирамиды можно с a[k]...a[n], k = [size/2]. Эта часть массива удовлетворяет свойству пирамиды, так как не существует индексов i,j: i = 2i+1 ( или j = 2i+2 )... Просто потому, что такие i,j находятся за границей массива.
Следует заметить, что неправильно говорить о том, что a[k]..a[n] является пирамидой как самостоятельный массив. Это, вообще говоря, не верно: его элементы могут быть любыми. Свойство пирамиды сохраняется лишь в рамках исходного, основного массива a[0]...a[n].
Далее будем расширять часть массива, обладающую столь полезным свойством, добавляя по одному элементу за шаг. Следующий элемент на каждом шаге добавления - тот, который стоит перед уже готовой частью.
Чтобы при добавлении элемента сохранялась пирамидальность, будем использовать следующую процедуру расширения пирамиды a[i+1]..a[n] на элемент a[i] влево:
1. Смотрим на сыновей слева и справа - в массиве это a[2i+1] и a[2i+2] и выбираем наибольшего из них.
2. Если этот элемент больше a[i] - меняем его с a[i] местами и идем к шагу 2, имея в виду новое положение a[i] в массиве. Иначе конец процедуры.
Новый элемент "просеивается" сквозь пирамиду.
Ниже дана иллюстрация процесса для пирамиды из 8-и элементов:
44 55 12 42 // 94 18 06 67 Справа - часть массива, удовлетворяющая
44 55 12 // 67 94 18 06 42 свойству пирамиды,
44 55 // 18 67 94 12 06 42
44 // 94 18 67 55 12 06 42 остальные элементы добавляются
// 94 67 18 44 55 12 06 42 один за другим, справа налево.
В геометрической интерпретации ключи из начального отрезка a[size/2]...a[n] является листьями в бинарном дереве, как изображено ниже. Один за другим остальные элементы продвигаются на свои места, и так - пока не будет построена вся пирамида.
На рисунках ниже изображен процесс построения. Неготовая часть пирамиды (начало массива) окрашена в белый цвет, удовлетворяющий свойству пирамиды конец массива - в темный.




Фаза 2: собственно сортировка
Итак, задача построения пирамиды из массива успешно решена. Как видно из свойств пирамиды, в корне всегда находится максимальный элемент. Отсюда вытекает алгоритм фазы 2:
1. Берем верхний элемент пирамиды a[0]...a[n] (первый в массиве) и меняем с последним местами. Теперь "забываем" об этом элементе и далее рассматриваем массив a[0]...a[n-1]. Для превращения его в пирамиду достаточно просеять лишь новый первый элемент.
2. Повторяем шаг 1, пока обрабатываемая часть массива не уменьшится до одного элемента.



Очевидно, в конец массива каждый раз попадает максимальный элемент из текущей пирамиды, поэтому в правой части постепенно возникает упорядоченная последовательность.
94 67 18 44 55 12 06 42 // иллюстрация 2-й фазы сортировки
67 55 44 06 42 18 12 // 94 во внутреннем представлении пирамиды
55 42 44 06 12 18 // 67 94
44 42 18 06 12 // 55 67 94
42 12 18 06 // 44 55 67 94
18 12 06 // 42 44 55 67 94
12 06 // 18 42 44 55 67 94
06 // 12 18 42 44 55 67 94

Каково быстродействие получившегося алгоритма ?
Построение пирамиды занимает O(n log n) операций, причем более точная оценка дает даже O(n) за счет того, что реальное время выполнения зависит от высоты уже созданной части пирамиды.
Вторая фаза занимает O(n log n) времени: O(n) раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок (n log n)/2, и отклонения от этого значения сравнительно малы.
Пирамидальная сортировка не использует дополнительной памяти.
Метод не является устойчивым: по ходу работы массив так "перетряхивается", что исходный порядок элементов может измениться случайным образом.
Поведение неестественно: частичная упорядоченность массива никак не учитывается.

Содержание

Содержание

Введение 3
1. Классы алгоритмов сортировки 4
2. Оценка алгоритмов сортировки 5
3. Сортировка выбором 7
4. Пирамидальная сортировка 9
Заключение. 16
Список использованной литературы 17
Приложение 1. Листинг процедуры сортировки выбором 18
Приложение 2. Листинг пирамидальной сортировки 19


































Введение
В общей постановке задача ставится следующим образом. Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого (далее мы будем называть его ключом сортировки). Тип данных ключа должен включать операции сравнения ("=", ">", "=" и "

Литература

1. Дональд Кнут Искусство программирования, том 3. Сортировка и поиск . 2-е изд. М.: «Вильямс», 2007. С. 824.

Форма заказа

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

Тип работы *
Предмет *
Название *
Дата Сдачи *
Количество Листов*
уточните задание
Ваши Пожелания
Загрузить Файлы

загрузить еще одно дополнение
Страна
Город
Ваше имя *
Эл. Почта *
Телефон *
  

Название Тип Год сдачи Страниц Цена
Разработка локальной сети. Курсовая 2007 9 1000
Численные методы Курсовая 2008 27 1500
Алгоритмы_шифрования Курсовая 2008 30 1500
Курсовая работа по дисциплине "Информатика". Курсовая 2008 20 1000
Алгоритмы шифрования Курсовая 2008 30 1500
Стандартизация программных средств и ее место в управлении качеством программных средств Курсовая 2008 33 1000
Метод наименьших квадратов Метод итераций Метод Ньютона (касательных) Метод трапеций и средних прямоугольников Метод дихотомии Метод золотого сечения Курсовая 2008 28 1500
Разработка Корпоративной ИС»:Поликлиника, АРМ регистратора Курсовая 2008 38 1500
Классификация основных видов памяти ПК. Курсовая 2008 20 1000
Метод наименьших квадратов Курсовая 2008 29 1500
курсовые, дипломные, контрольные на заказ скидки на курсовые, дипломные, контрольные на заказ

© 2010-2016, Все права защищены. Принимаем заказы по всей России.