Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Использование алгоритмов сортировки ⇐ ПредыдущаяСтр 6 из 6
Цель работы: ознакомится с различными методами сортировки данных, освоить способы программирования алгоритмов сортировки.
Краткие теоретические сведения Под сортировкой понимают процесс перестановки объектов данного множества в определенном порядке. Цель сортировки - облегчить последующий поиск элементов в отсортированном множестве. В этом смысле сортировка присутствует почти во всех задачах обработки информации. С сортировкой связаны многие фундаментальные приемы построения алгоритмов, которые и будут нас интересовать в первую очередь. В частности, сортировка является идеальным примером огромного разнообразия алгоритмов, выполняющих одну и ту же задачу, многие из которых в некотором смысле оптимальные, а большинство имеет какие-либо преимущества по сравнению с остальными. Поэтому на примере сортировки мы убеждаемся в необходимости сравнительного анализа алгоритмов. Зависимость выбора алгоритмов от структуры данных - явление довольно частое, а в случае сортировки она настолько сильна, что методы сортировки обычно разделяются на две категории: · сортировка массивов (внутренняя сортировка) · сортировка файлов (внешняя сортировка).
ПОСТАНОВКА ЗАДАЧИ ДАНО ТРЕБУЕТСЯ СВЯЗЬ и последовательность является перестановкой исходной последовательности. Основное требование к методам внутренней сортировки - экономное использование памяти. Это означает, что переупорядочивание элементов надо выполнять на том же месте. Методы внутренней сортировки можно разбить на четыре основных класса в зависимости от лежащего в их основе приема: · сортировка включением(вставкой), · сортировка выбором, · сортировка обменом, · разделением.
СОРТИРОВКА ВКЛЮЧЕНИЕМ. Этот метод состоит в том, что на каждом шаге берут i-ый элемент последовательности и передают его в готовую отсортированную часть последовательность, вставляя его на свое место. Алгоритм сортировки включениями выглядит следующим образом:
FOR I:= 2 TO N DO BEGIN X:= a[I]; < вставить X на подходящее место в a[1], a[2],...,a[I] > END СОРТИРОВКА ВЫБОРОМ. Этот метод основан на следующем правиле. Выбирается минимальный (максимальный) элемент последовательности и обменивается с первым элементом (элементом) последовательности. Очевидно, один элемент при этом встанет на свое место в отсортированной части последовательности. Далее все выше изложенное надо повторить в не отсортированной части последовательности и т.д.
FOR I = 1 TO N-1 DO BEGIN < присвоить K индекс наименьшего элемента из a[I]...a[N] > < поменять местами a[I] и a[K] > END СОРТИРОВКА ОБМЕНОМ. Алгоритм обмена основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы. В качестве примера рассмотрим сортировку методом пузырька.
FOR I:= 2 TO N DO FOR J:= N DOWNTO I DO IF a[J-1] > a[J] THEN BEGIN X:= a[J-1]; a[J-1]:= a[J]; a[J]:= X END
СОРТИРОВКА РАЗДЕЛЕНИЕМ. Алгоритм разделением основан на разбиении последовательности на две подпоследовательности по некоторому правилу. При этом каждая из них может не являться упорядоченной, но последовательное применение указанного правила приводит к упорядоченности последовательности. Примером этого класса алгоритмов является алгоритм быстрой сортировки. Procedure quicksort (S); begin if < S содержит один элемент> then <возвратить S > else begin <выбрать произвольный элемент a из S >; <пусть S 1, S 2 и S 3 - последовательности элементов из S, соответственно меньших, равных и больших a >; < возвратить quicksort(S1), затем S2,, затем quicksort(S3) > end end
Внешняя сортировка, т.е. сортировка данных, находящихся на внешних запоминающих устройствах, имеет свои особенности. · Существенную долю времени в этих сортировках тратится на обмен информации с внешним запоминающим устройством, поэтому нужны алгоритмы, которые минимизируют число таких операций. · Оперативная память имеет ограниченные размеры и поэтому в каждый момент времени может быть доступна только часть данных. Рассмотрим один из алгоритмов внешней сортировки.
СОРТИРОВКА СЛИЯНИЕМ. Главная идея, которая лежит в основе этой сортировки это представлении файла в виде постепенно увеличивающихся серий, т.е. упорядоченных подпоследовательностей. Если есть, по крайней мере, два файла и число серий в них равно или отличается на единицу, то последовательным слиянием отсортированных серий в новый файл можно уменьшить количество серий, по крайней мере, в два раза.
Отчет о выполнении
Отчет выполняется в электронном виде. Если заданий несколько, то повторить всю систему отчета необходимое количество раз.
Контрольные вопросы: 1. Что такое одномерный массив? 2. Что такое двухмерный массив? 3. Что такое сортировка массива? 4. Какие методы сортировки вы знаете? Варианты индивидуальных заданий
|
|||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-04-13; просмотров: 118; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.225.10.116 (0.02 с.) |