Варианты заданий 37 Контрольные вопросы к защите ргр: 39

Вид материала

Контрольные вопросы

Содержание Постановка задачи Понятие сортировки. Анализ эффективности сортировки Некоторые методы сортировок Сортировка простым выбором Сортировка простыми вставками Сортировка бинарными вставками Сортировка Шелла Сортировка простым обменом («Пузырьковая сортировка») Шейкерная сортировка Быстрая сортировка Сортировка слиянием Порядок выполнения работы ПРИМЕР выполнения расчетно-графической РАБОТЫ Варианты ЗАДАНИй Контрольные вопросы к защите РГР Рекомендуемая литература Initgraph ( Встроенные константы Турбо Паскаля, обозначающие цвета, и соответствующие им цифровые коды. DrawPoly(kol, Arr) ... Полное содержание

Подобный материал:

• А внимательно прочитайте вопросы и варианты ответов, 66.8kb.
• А внимательно прочитайте вопросы и варианты ответов, 85.91kb.
• Контрольная работа и ее краткая характеристика дкр, 446.71kb.
• Варианты задания на ргр (по уровням сложности), 35.75kb.
• Контрольные вопросы, тематика тестовых заданий и экзаменационных билетов, 23.19kb.
• План работы комитета ргр по оценке недвижимости на 2011 2012, 46.4kb.
• Общие рекомендации. Внимательно прочитайте каждое задание и предлагаемые варианты ответа,, 59.07kb.
• Учебное пособие Новочеркасск, 2009 удк 343. 8 (075. 8) Ббк 67. 409, 2241.72kb.
• Александр Леонидович Симанов Содержание История философии. Онтология и гносеология., 225.58kb.
• Особенности бухгалтерского учета, 286.34kb.

СОДЕРЖАНИЕ

Постановка задачи

Цели и задачи:

• Изучение основных методов сортировки;
  
• Анализ эффективности методов сортировки;
  
• Построение графиков зависимости количества сравнений и перестановок от длины массива с помощью модуля GRAPH.
  

Задание

Изучить основные методы сортировки данных. Разработать алгоритмы указанных в варианте методов. Оценить эффективность метода в зависимости от длины массива. Построить график зависимости от длины массива (20,40,60,80,…200 элементов).

ПОНЯТИЕ СОРТИРОВКИ.

Сортировка – это процесс упорядочивания информации по определенному признаку. Цель сортировки – облегчение поиска данных. Это почти универсальный вид обработки информации, встречающийся в жизни повсеместно. Мы встречаемся с отсортированными объектами в телефонных книгах, в списках подоходных налогов, в библиотеке, в словарях, на складах – почти везде, где нужно осуществлять поиск и хранение каких-либо объектов. Информационные данные сортируются в целях облегчения последующей обработки данных: поиска, добавления или исключения объектов. Примером может служить поиск книги в библиотечном каталоге или термина в справочной литературе.

Данные можно сортировать:

• по возрастанию (убыванию);
  
• по алфавиту;
  
• по классам
  
• по типам и т.п.
  

Существует огромное количество методов сортировок. Все они различны и каждый “хорош” по-своему, но наилучшего, универсального во всех отношениях не существует. Эффективность алгоритма зависит от множества факторов:

• Количества сортируемых данных;
  
• Степени начальной отсортированности данных;
  
• Необходимости исключения или добавления элементов;
  
• Доступа к сортируемым данным (прямого или последовательного).
  

Принципиальным для выбора метода сортировки является последний фактор. Если данные могут быть расположены в оперативной памяти, то к любому элементу возможен прямой доступ. Обычно в таких случаях данные представляют в виде массива. Если данные размещены на внешнем носителе, то к ним можно обращаться лишь последовательно. В качестве структуры подобных данных можно взять файловый тип. В связи с этим выделяют два класса сортировок: внутренняя сортировка (массивы) и внешняя (файловая).

Мы будем рассматривать различные методы внутренней сортировки данных, когда количество их достаточно мало, так что весь процесс можно провести в оперативной памяти компьютера.

Чаще всего данные, требующие сортировки представляют собой записи. При сортировке в одних случаях может понадобиться физически переставлять записи в памяти так, чтобы их ключи были упорядочены; в других случаях можно обойтись вспомогательной таблицей, определяющей перестановку. Если записи или ключи занимают несколько слов памяти, то часто лучше составить новую таблицу адресных ссылок, которые указывают на записи. Такой метод называется сортировкой таблицы адресов (см. Рисунок 1).

	Запись 1			Запись 2			Запись 3
ключ	53			12			27
	данные			данные			данные
	данные			данные			данные
таблица							до сортировки
адресов
							после сортировки

Рисунок 1


В других схемах сортировки используется вспомогательное поле связи, которое включается в каждую запись. Связи обрабатываются таким образом, что в результате все они оказываются объединенными в линейный список, в котором каждая запись указывает на следующую по порядку запись. Этот способ называется сортировкой списка (см. Рисунок 2) .

Запись1

Запись2

Запись3

ключ

53

12

27

данные

данные

данные

поле

данные

данные

данные

связи

nul

начало списка

A5

Рисунок 2


Мы будем рассматривать сортировку записей и чтобы не отвлекаться на структуру данных представим последние в виде массивов ключей, представленных множеством целых чисел.

Числа можно сортировать:

• по неубыванию – каждый следующий элемент не меньше предыдущего, т.е. A_i ≤ A_i+1;
  
• по возрастанию - каждый следующий элемент больше предыдущего, т.е.
  

A_i < A_i+1;

• по невозрастанию - каждый следующий элемент не больше предыдущего, т.е. A_i ≥ A_i+1;
  
• по убыванию - каждый следующий элемент меньше предыдущего, т.е.
  

A_i > A_i+1.