Сравнение эффективности методов сортировки массивов: Метод прямого выбора и метод сортировки с помощью дерева (WinWord&C) [Лабораторная]

---

запомнить в избранное   искать в этом разделе

---

ВНИМАНИЕ !!! Это сокращенная версия файла. Предназначена она только для того, чтобы вы могли предварительно ознакомиться с документом, перед тем как его скачать. Здесь нет картинок, не сохранен формат, шрифт, размеры и положение на странице.
Чтобы скачать полную версию, нажмите ссылки которые находятся чуть-чуть ниже (Info File Mail)

---

Info File Mail

Файл относится к разделу:
ПРОГРАММИРОВАHИЕ, БАЗЫ ДАHHЫХ

---

Лабораторная работа № 1
Сравнить эффективность методов сортировки массивов:
Метод прямого выбора и метод сортировки с помощью дерева.
Сортировка с помощью прямого выбора
Этот прием основан на следующих принципах:
1. Выбирается элемент с наименьшим ключом.
2. Он меняется местами с первым элементом ai.
3. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент.
Процесс работы этим методом с теми же восемью ключами, что и в табл. 2.1, приведен в табл. 2.2. Алгоритм формулируется так:
FORi=ITO n-1 DO
присвоить k индекс наименьшего из a[i],,, a[nJ; поменять местами a[i] и a[j];
END
Такой метод - его называют прямым выбором - в некотором смысле противоположен прямому включению. При прямом включении на каждом шаге рассматриваются только один очередной элемент исходной последовательности и все элементы готовой последовательности, среди которых отыскивается точка включения; при прямом выборе для поиска одного элемента с наименьшим ключом просматриваются все элементы исходной последовательности и найденный помещается как очередной элемент в готовую последовательность. Полностью алгоритм прямого выбора приводится в прогр. 2.3.
Таблица 2.2. Пример сортировки с помощью прямого выбора
Начальные ключи
44 55 12 42 94 18 06 67
06 55 12 42 94 18 44 67
06 12 55 42 94 18 44 67
06 12 18 42 94 55 44 67
05 12 18 42 94 55 44 67
05 12 13 42 44 55 94 67
06 12 18 42 44 55 94 67
06 12 18 42 44 55 67 94
PROCEDURE StraightSfcleclion;
VAR i,j,k: index; x: item; BEGIN
FORi=1 TO n-1 DO k= i; x = a[i]; FORj= i+1TO n DO
IF a[j] Прогр. 2.3. Сортировка с помощью прямого выбора,
Анализ прямого выбора. Число сравнений ключей (С), очевидно, не зависит от начального порядка ключей. Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение прямого включения. Для С имеем
с (n2 - n)/2
Число перестановок минима

• подписаться на рассылку. • добавить в избранное. • нашли ошибки ?

Это место