Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и...

Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и...

^ Теоретические сведения:
Наружные сортировки, обычно, используются для упорядочения огромного количества частей, расположенных на наружных носителях. При всем этом доступ к элементам осуществляется поочередно.

Большая часть алгоритмов наружных сортировок употребляют слияние.

Слияние - объединение Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... 2-ух либо более последовательностей в одну, упорядоченную неким образом, при помощи циклического выбора из доступных на этот момент частей.
^ Обычное слияние
Разглядим двухфазную сортировку обычным слиянием.

Пусть дана некая последовательность A. Для работы Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... метода потребуются 2 вспомогательные последовательности B и C.

Фаза 1, проход 1 – по 1 элементу

А: 7 15 2 3 10 4 9 12 11 5 1

В: 7 2 10 9 11 1

С: 15 3 4 12 5

Фаза 2, проход 1

А: 7 15 2 3 4 10 9 12 5 11 1

Фаза 1, проход 2– по 2 элемента

А: 7 15 2 3 4 10 9 12 5 11 1

В: 7 15 4 10 5 11

С: 2 3 9 12 1

Фаза 2, проход 2

А: 2 3 7 15 4 9 10 12 1 5 11

Сущность метода заключается в чередующемся выполнении 2-ух Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... его фаз: фазы рассредотачивания и фазы слияния частей. В первой фазе элементы "распределяются" определённым образом из последовательности A в последовательности B и C. Во 2-ой фазе элементы "соединяются" из последовательностей B Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... и C в последовательность A.

В итоге каждого такового прохода, состоящего из 2-ух фаз, упорядоченность последовательности A будет возрастать: в итоге первого прохода будет упорядочена любая пара частей, в итоге второго прохода будет упорядочена Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... любая четвёрка частей и т.д. Работа метода завершается тогда, когда последовательность A будет упорядочена стопроцентно.

Число проходов, нужных для упорядочения последовательности, логарифмически находится в зависимости от количества частей. К примеру, для упорядочения Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... 1.000 частей будет нужно 10 проходов, для упорядочения 1.000.000 частей будет нужно около 20 проходов, для 1.000.000.000 частей - около 30 проходов и т.д.

Анализ сортировки при помощи слияния. Так как на каждом проходе р умножается Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... и сортировка завершается при р >= n,то всего требуется [log n] проходов. На каждом проходе по опреде­лению копируются по одному разу все п частей. Потому об­щее число пересылок

M=n*[log n Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... ]

Число сравнений ключей С даже меньше М, так как при ко­пировании остатков никаких сравнений не делается. Одна­ко так как сортировки слиянием обычно употребляются в си­туациях, где приходится воспользоваться наружными Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... запоминающи­ми устройствами, то издержки на операции пересылки на несколько порядков превосходят издержки на сопоставления. Потому детализированный анализ числа сравнений особенного практического энтузиазма не пред­ставляет. Метод сортировки слиянием выдерживает сопоставление Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... даже с улучшенными способами, разбиравшимися ранее. Но, хотя тут относительно высоки издержки на работу с индексами, самым значимым недочетом явля­ется необходимость работать с памятью размером 2п. Потому сортировка слиянием для Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... массивов, т. е. для данных, размещаемых в оперативки, употребляется изредка.
^ Естественное слияние
Сортировка естественным слиянием является другим усовершенствованием сортировки обычным слиянием. В ней вводится понятие серии частей как последовательности частей, в какой Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... каждый следующий элемент больше (меньше) предшествующего.

Фаза 1, проход 1 – рассредотачивание серий

А: 7 15 2 3 10 4 9 12 11 5 1

В: 7 15 4 9 12 5

С: 2 3 10 11 1

Фаза 2, проход 1 – слияние

А: 2 3 7 10 11 15 1 4 5 12 5

Фаза 1, проход 2 – рассредотачивание серий

В: 2 3 7 10 11 15 5

С: 1 4 9 12

Фаза 2, проход 2– слияние

А: 1 2 3 4 7 9 10 11 12 15 5

В сортировке обычным слиянием серии составлялись без учёта Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... начального расположения частей в начальной последовательности. Поначалу длина серий была равна 1, потом 2, 4 и т.д. Естественное слияние учитывает первоначальное размещение частей в последовательности. В итоге этого удаётся уменьшить число проходов, нужных для упорядочения последовательности. В Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... остальном же сортировка естественным слиянием подобна обычному слиянию: серии частей из последовательности A распределяются поочерёдно в последовательности B и C. Потом элементы "соединяются" назад в последовательность A, образуя при всем этом серии Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... большей длины, чем сначало, и т.д.
^ Многопутевое равновесное слияние
В прошлых методах наружных сортировок рассредотачивание частей происходило в две последовательности. Во многопутевом слиянии число таких последовательностей (путей) может быть хоть каким Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... целым числом n  2. Чем больше путей употребляется в сортировке, тем меньше проходов пригодится для полного упорядочения последовательности. Многопутевое равновесное слияние употребляет серии естественной длины, и каждый проход состоит из Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... одной фазы. Разглядим работу метода на примере. Число путей равно 3. Подготовительный проход 1 – рассредотачивание серий

S1: 7 15 2 3 10 4 9 12 11 5 1

S2:

S3:

S4: 7 15 11

S5: 2 3 10 5

S6: 4 9 12 1

Проход 2

S1: 1 2 3 4 7 9 10 12 15

S2: 1 5 11


Проход 3

S4: 1 2 3 4 5 7 9 10 11 12 15
^ Пример дизайна:


Рис. 1. Окно задания характеристик сортировок.



Рис Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и....2. Итог тестирования.



Рис. 3. Свойства тестирования наружных сортировок.


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



  1. Какова сущность метода каждой сортировки?

  2. Анализ каждого метода?

  3. Какой метод более эффективен?

  4. От каких характеристик зависит время выполнения сортировки?

  5. Какой функции пропорционально время?


^ Задание на Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... лабораторную работу:


ВАРИАНТ 1.

  1. Обрисовать структуру с именованием STUDENT, содержащую последующие поля:

  1. Массив чисел в интервале [-20, 50].



ВАРИАНТ 2.

  1. Обрисовать структуру с именованием Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... AEROFLOT, содержащую последующие поля:

  1. Массив чисел в интервале [-50, 50].



ВАРИАНТ 3.

  1. Обрисовать структуру с именованием WORKER, содержащую последующие поля:

сортировка по году поступления на работу

  1. Массив чисел в интервале [-120, 50].



ВАРИАНТ 4.

  1. Обрисовать структуру с именованием TRAIN, содержащую последующие поля:

сортировка по номеру поезда

  1. Массив чисел в интервале [-5, 100].



ВАРИАНТ 5.

  1. Обрисовать структуру с именованием MARSH, содержащую последующие поля:

сортировка по номеру маршрута

  1. Массив чисел Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... в интервале [-10, 25].



ВАРИАНТ 6.

  1. Обрисовать структуру с именованием NOTE, содержащую последующие поля:

сортировка по номеру телефона

  1. Массив чисел в интервале [-10, 40].



ВАРИАНТ 7.

  1. Обрисовать структуру с именованием Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... ZNAK, содержащую последующие поля:

сортировка по дате рождения.

  1. Массив чисел в интервале [-40, 50].



ВАРИАНТ 8.

  1. Обрисовать структуру с именованием PRICE Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... содержащую последующие поля:

сортировка по цены продукта.

  1. Массив чисел в интервале [-20, 100].



ВАРИАНТ 9.

  1. Обрисовать структуру с именованием ORDER, содержащую последующие поля:

сортировка по перечисляемой сумме.

  1. Массив чисел в интервале [-20, 10].



ВАРИАНТ 10.

  1. Обрисовать структуру с именованием Tovar, содержащую последующие поля:

сортировка по стоимости продукта.

  1. Массив чисел в интервале [-50, 50].



ВАРИАНТ 11.

  1. Обрисовать структуру с именованием Baza, содержащую последующие поля:

сортировка по году рождения.

  1. Массив чисел в интервале [-20, 50].



ВАРИАНТ 12.

  1. Обрисовать Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... структуру с именованием Systema, содержащую последующие поля:

сортировка по поперечнику.

  1. Массив чисел в интервале [-30, 30].



ВАРИАНТ 13.

  1. Обрисовать структуру с именованием Systema, содержащую последующие поля Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и...:

сортировка по объему.

  1. Массив чисел в интервале [-35, 12].



ВАРИАНТ 14.

  1. Обрисовать структуру с именованием Спорт, содержащую последующие поля:

сортировка дате установления Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... рекорда.

  1. Массив чисел в интервале [-100, 50].



ВАРИАНТ 15.

  1. Обрисовать структуру с именованием Rasp, содержащую последующие поля:

сортировка по протяженности пути.

  1. Массив чисел в интервале [-100, 100].



ВАРИАНТ 16.

  1. Обрисовать структуру Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... с именованием Post, содержащую последующие поля:

сортировка по цены .

  1. Массив чисел в интервале [-65, 15].



ВАРИАНТ 17.

  1. Обрисовать структуру с именованием Boln, содержащую последующие поля Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и...:

сортировка по возрасту.

  1. Массив чисел в интервале [-60, 20].



ВАРИАНТ 18.

  1. Обрисовать структуру с именованием Boln, содержащую последующие поля:

сортировка по дате поступления.

  1. Массив чисел Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и... в интервале [-40, 40].



ВАРИАНТ 19.

  1. Обрисовать структуру с именованием Doc, содержащую последующие поля:

сортировка по количеству знаков.

  1. Массив чисел в интервале [-20, 50].



ВАРИАНТ 20.

  1. Обрисовать структуру с именованием Katalog Теоретические сведения - Учебное пособие подготовлено на кафедре "Естественно-научных и технических дисциплин" и..., содержащую последующие поля:

сортировка по количеству страничек.

  1. Массив чисел в интервале [-5, 10].





teoreticheskoe-obuchenie-lekcii-seminarskie-prakticheskie-zanyatiya.html
teoreticheskoe-rukovodstvo.html
teoreticheskoe-zadanie-ocenivaetsya-po-desyatiballnoj-sisteme-po-sleduyushim-kriteriyam-pravilnost-otveta-2-balla-polnota-otveta-2-balla.html