В данной статье рассматриваются алгоритмы сортировки массивов. Для начала представляются выбранные для тестирования алгоритмы с кратким описанием их работы, после чего производится непосредственно тестирование, результаты которого заносятся в таблицу и производятся окончательные выводы.
Алгоритмы сортировок очень широко применяются в программировании, но иногда программисты даже не задумываются какой алгоритм работает лучше всех (под понятием «лучше всех» имеется ввиду сочетание быстродействия и сложности как написания, так и выполнения).
В данной статье постараемся это выяснить. Для обеспечения наилучших результатов все представленные алгоритмы будут сортировать целочисленный массив из 200 элементов. Компьютер, на котором будет проводится тестирование имеет следующие характеристики: процессор AMD A6-3400M 4x1.4 GHz, оперативная память 8 GB, операционная система Windows 10 x64 build 10586.36.
Для проведения исследования были выбраны следующие алгоритмы сортировки:
Selection sort (сортировка выбором) – суть алгоритма заключается в проходе по массиву от начала до конца в поиске минимального элемента массива и перемещении его в начало. Сложность такого алгоритма O(n2).
Bubble sort (сортировка пузырьком) – данный алгоритм меняет местами два соседних элемента, если первый элемент массива больше второго. Так происходит до тех пор, пока алгоритм не обменяет местами все неотсортированные элементы. Сложность данного алгоритма сортировки равна O(n^2).
Insertion sort (сортировка вставками) – алгоритм сортирует массив по мере прохождения по его элементам. На каждой итерации берется элемент и сравнивается с каждым элементом в уже отсортированной части массива, таким образом находя «свое место», после чего элемент вставляется на свою позицию. Так происходит до тех пор, пока алгоритм не пройдет по всему массиву. На выходе получим отсортированный массив. Сложность данного алгоритма равна O(n^2).
Quick sort (быстрая сортировка) – суть алгоритма заключается в разделении массива на два под-массива, средней линией считается элемент, который находится в самом центре массива. В ходе работы алгоритма элементы, меньшие чем средний будут перемещены в лево, а большие в право. Такое же действие будет происходить рекурсивно и с под-массива, они будут разделяться на еще два под-массива до тех пор, пока не будет чего разделать (останется один элемент). На выходе получим отсортированный массив. Сложность алгоритма зависит от входных данных и в лучшем случае будет равняться O(n×2log2n). В худшем случае O(n^2). Существует также среднее значение, это O(n×log2n).
Comb sort (сортировка расческой) – идея работы алгоритма крайне похожа на сортировку обменом, но главным отличием является то, что сравниваются не два соседних элемента, а элементы на промежутке, к примеру, в пять элементов. Это обеспечивает от избавления мелких значений в конце, что способствует ускорению сортировки в крупных массивах. Первая итерация совершается с шагом, рассчитанным по формуле (размер массива)/(фактор уменьшения), где фактор уменьшения равен приблизительно 1,247330950103979, или округлено до 1,3. Вторая и последующие итерации будут проходить с шагом (текущий шаг)/(фактор уменьшения) и будут происходить до тех пор, пока шаг не будет равен единице. Практически в любом случае сложность алгоритма равняется O(n×log2n).
Для проведения тестирования будет произведено по 5 запусков каждого алгоритма и выбрано наилучшее время. Наилучшее время и используемая при этом память будут занесены в таблицу. Также будет проведено тестирование скорости сортировки массива размером в 10, 50, 200 и 1000 элементов чтобы определить для каких задач предназначен конкретный алгоритм.
Полностью неотсортированный массив:
Частично отсортированный массив (половина элементов упорядочена):
Результаты, предоставленые в графиках:
В результате проведенного исследования и полученных данных, для сортировки неотсортированного массива, наиболее оптимальным из представленных алгоритмов для сортировки массива является быстрая сортировка. Несмотря на более длительное время выполнения алгоритм потребляет меньше памяти, что может быть важным в крупных проектах. Однако такие алгоритмы как сортировка выбором, обменом и вставками могут лучше подойти для научных целей, например, в обучении, где не нужно обрабатывать огромное количество данных. При частично отсортированном массиве результаты не сильно отличаются, все алгоритмы сортировки показывают время примерно на 2-3 миллисекунды меньше. Однако при сортировке частично отсортированного массива быстрая сортировка срабатывает намного быстрее и потребляет меньшее количество памяти.
Введение.
Около трех с половиной десятилетий минуло с тех пор, как в педвузах введено в качестве учебной дисциплины программирование для ЭВМ. При колоссальной скорости изменений в самом предмете, всегда существенно превышавшей скорость центральных издательских механизмов, специально ориентированные на программы педвузов книги выходили не чаще, чем раз в десятилетие – едва ли не соразмерно скорости смены поколений ЭВМ. Сегодня полки книжных магазинов ломятся от изданий по информатике. Однако преподавателю (а более всего студенту) специальные учебные книги, содержание и направленность которых отвечают заданному учебному плану и программе все-таки очень нужны. Сейчас помимо программирования на некоторых специальностях в педвузах введены и другие более сложные спецкурсы, находящиеся на стыке прикладной (дискретной) математики и информатики.
В данной курсовой работе можно познакомится с массивами и узнать о простых и сложных методах их сортировки, а также о том, какие из них наиболее эффективны и в каких случаях.
1. Задачи сортировки.
1.1.Общие положения.
Основная задача – продемонстрировать различные методы сортировки и выделить наиболее эффективные из них. Сортировка – достаточно хороший пример задачи, которую можно решать с помощью многих различных алгоритмов. Каждый из них имеет и свои достоинства, и свои недостатки, и выбирать алгоритм нужно, исходя из конкретной постановки задачи.
В общем сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки – облегчить последующий поиск элементов в таком отсортированном множестве. Это почти универсальная, фундаментальная деятельность. Мы встречаемся с отсортированными объектами в телефонных книгах, в списках подоходных налогов, в оглавлениях книг, в библиотеках, в словарях, на складах – почти везде, где нужно искать хранимые объекты.
Таким образом, разговор о сортировке вполне уместен и важен, если речь идет об обработке данных. Первоначальный интерес к сортировке основывается на том, что при построении алгоритмов мы сталкиваемся со многими весьма фундаментальными приемами. Почти не существует методов, с которыми не приходится встречаться при обсуждении этой задачи. В частности, сортировка – это идеальный объект для демонстрации огромного разнообразия алгоритмов, все они изобретены для одной и той же задачи, многие в некотором смысле оптимальны, большинство имеет свои достоинства. Поэтому это еще и идеальный объект, демонстрирующий необходимость анализа производительности алгоритмов. К тому же на примерах сортировок можно показать, как путем усложнения алгоритма, хотя под рукой и есть уже очевидные методы, можно добиться значительного выигрыша в эффективности.
Выбор алгоритма зависит от структуры обрабатываемых данных – это почти закон, но в случае сортировки такая зависимость столь глубока, что соответствующие методы разбили на два класса – сортировку массивов и сортировку файлов (последовательностей). Иногда их называют внутренней и внешней сортировкой, поскольку массивы хранятся в быстрой, оперативной, внутренней памяти машины со случайным доступом, а файлы обычно размещаются в более медленной, но и более емкой внешней памяти, на устройствах, основанных на механических перемещениях (дисках или лентах).
, a, …… , а то сортировка есть перестановка этих элементов в массив аk, ak, …… ,akгде ak <= ak <= ….. <= ak.Считаем, что тип элемента определен как INTEGER .
Constn=???; //здесь указывается нужная длина массива
Var A: array of integer;
Выбор INTEGER до некоторой степени произволен. Можно было взять и
другой тип, на котором определяется общее отношение порядка.
Метод сортировки называют устойчивым, если в процессе сортировки относительное расположение элементов с равными ключами не изменяется. Устойчивость сортировки часто бывает желательной, если речь идет об элементах, уже упорядоченных (отсортированных) по некотором вторичным ключам (т.е. свойствам), не влияющим на основной ключ.
1.2. Постановка задачи сортировки массивов.
Основное условие: выбранный метод сортировки массивов должен экономно использовать доступную память. Это предполагает, что перестановки, приводящие элементы в порядок, должны выполняться на том же месте т. е. методы, в которых элементы из массива а передаются в результирующий массив b, представляют существенно меньший интерес. Мы будем сначала классифицировать методы по их экономичности, т. е. по времени их работы. Хорошей мерой эффективности может быть C – число необходимых сравнений ключей и M – число пересылок (перестановок) элементов. Эти числа суть функции от n – числа сортируемых элементов. Хотя хорошие алгоритмы сортировки требуют порядка n*logn сравнений, мы сначала разберем несколько простых и очевидных методов, их называют прямыми, где требуется порядка n2 сравнений ключей. Начинать разбор с прямых методов, не трогая быстрых алгоритмов, нас заставляют такие причины:
1. Прямые методы особенно удобны для объяснения характерных черт основных принципов большинства сортировок.
2. Программы этих методов легко понимать, и они коротки.
3. Усложненные методы требуют большого числа операций, и поэтому для достаточно малых n прямые методы оказываются быстрее, хотя при больших n их использовать, конечно, не следует.
Методы сортировки “ на том же месте “ можно разбить в соответствии с определяющими их принципами на три основные категории:
· Сортировки с помощью включения (byinsertion).
· Сортировки с помощью выделения (byselection).
· Сортировка с помощью обменов (byexchange).
Теперь мы исследуем эти принципы и сравним их. Все программы оперируют массивом а.
Constn=<длина массива>
a: array ofinteger;
2. Методы сортировки массивов.
2.1. Простые методы сортировки массивов.
2.1.1. Сортировка с помощью прямого включения.
Такой метод широко используется при игре в карты. Элементы мысленно делятся на уже “готовую” последовательность а
, … , а и исходную последовательность. При каждом шаге, начиная с I = 2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i- й элементы и перекладывается в готовую последовательность, при этом он вставляется на нужное место.ПРОГРАММА 2.1. ССОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ВКЛЮЧЕНИЯ.
I,J,N,X:INTEGER;
A:ARRAY OF INTEGER;
WRITELN(‘Введите длину массива’);
WRITELN(‘Введитемассив’);
FOR I:=1 TO N DO READ(A[I]);
FOR I:=2 TO N DO
WHILE X
WRITELN("Результат:"); FOR I:=1 TO N DO WRITE(A[I]," ") Такой типичный случай повторяющегося процесса с двумя условиями окончания позволяет нам воспользоваться хорошо известным приемом “барьера” (sentinel). Анализ метода прямого включения. Число сравнений ключей (Ci) при i- м просеивании самое большее равно i-1, самое меньшее – 1; если предположить, что все перестановки из n ключей равновероятны, то среднее число сравнений – I/2. Число же пересылок Mi равно Ci + 2 (включая барьер). Поэтому общее число сравнений и число пересылок таковы: Cmin = n-1 (2.1.) Mmin = 3*(n-1) (2.4.) Cave = (n2+n-2)/4 (2.2.) Mave = (n2+9*n-10)/4 (2.5.) Cmax = (n2+n-4)/4 (2.3.) Mmax = (n2+3*n-4)/2 (2.6.) Алгоритм с прямыми включениями можно легко улучшить, если обратить внимание на то, что готовая последовательность, в которую надо вставить новый элемент, сама уже упорядочена. Естественно остановиться на двоичном поиске, при котором делается попытка сравнения с серединой готовой последовательности, а затем процесс деления пополам идет до тех пор, пока не будет найдена точка включения. Такой модифицированный алгоритм сортировки называется методом с двоичным включением (binaryinsertion). ПРОГРАММА 2.2. СОРТИРОВКА МЕТОДОМ ДЕЛЕНИЯ ПОПОЛАМ. I,J,M,L,R,X,N:INTEGER; A:ARRAY OF INTEGER; WRITELN("Введи длину массива"); WRITELN("Введи массив"); FOR I:=1 TO N DO READ(A[I]); FOR I:=2 TO N DO X:=A[I];L:=1;R:=I; IF A[M]<=X THEN L:=M+1 ELSE R:=M 8 Сортировка вставкой
9 А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом вставки Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. f f=1 f – условие выхода из цикла (если f=1, то выход) Val Val – промежуточное значение, используемое для перемещения элементов массив Постановка задачи
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма." title="10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма." class="link_thumb">
10
10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма.
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма.">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма.">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма." title="10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма.">
title="10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма.">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает" title="11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает" class="link_thumb">
11
11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает данное условие?
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает данное условие?">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает" title="11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает">
title="11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" class="link_thumb">
12
12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение j =2 ?
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение j =2 ?">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">
title="12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" class="link_thumb">
13
13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение i =2 ?
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение i =2 ?">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">
title="13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои" title="14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои" class="link_thumb">
14
14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли происходит обмен входного j элемента с отсортированным элементом?
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли происходит обмен входного j элемента с отсортированным элементом?">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои" title="14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои">
title="14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за" title="15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за" class="link_thumb">
15
15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли заменить цикл ПОКА и ЕСЛИ одним циклом ПОКА с условием i>=2 и A>A[i] ?
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли заменить цикл ПОКА и ЕСЛИ одним циклом ПОКА с условием i>=2 и A>A[i] ?">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за" title="15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за">
title="15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен" title="16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен" class="link_thumb">
16
16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен этот оператор?
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен этот оператор?">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен" title="16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен">
title="16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен">
18 Суть сортировки: Выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива. Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов.
Сортировка выбором Отсортиро- ванная часть Отсортированная часть Массив отсортирован по возрастанию
20 Постановка задачи А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом выбора. Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. min min – минимальное число в массиве. Imin Imin – номер минимального числа в массиве
25 Суть сортировки: Последовательно просматривается массив и сравнивается каждая пара элементов между собой. При этом "неправильное" расположение элементов устраняется путем их перестановки. Процесс просмотра и сравнения элементов повторяется до просмотра всего массива.
26 Сортировка обменом
27 А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом обмена Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. Val Val – промежуточное значение, используемое для перемещения элементов массива Постановка задачи
2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни" title="28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни" class="link_thumb">
28
28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг Шаг i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседних элементов Обмен соседних элементов местами, в случае если левый больше правого Формируется отсортированная часть
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни">
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседних элементов Обмен соседних элементов местами, в случае если левый больше правого Формируется отсортированная часть">
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни" title="28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни">
title="28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни">
2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та" title="29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та" class="link_thumb">
29
29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг Шаг i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие такое?
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та">
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие такое?">
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та" title="29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та">
title="29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та">
2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j" title="30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j" class="link_thumb">
30
30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг Шаг i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j уменьшается? Можно ли увеличивать? Что нужно изменить?
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j">
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j уменьшается? Можно ли увеличивать? Что нужно изменить?">
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j" title="30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j">
title="30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j">
35 12 Сортировка Шелла шаг. 4 группы из 2-х элементов шаг. 2 группы из 4-х элементов 36 Сортировка Шелла шаг. 1 группа из 8-ми элементов Массив отсортирован по возрастанию 37 А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом Шелла Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. M M- оптимальный шаг P P– промежуточное значение, используемое для перемещения элементов массива Постановка задачи
45 Суть сортировки: Выбирается некоторое значение (x)- барьерный элемент, который определяется округлением до целого деления количества сортируемых элементов на 2; Просматриваем массив, двигаясь слева направо, пока не найдется элемент, больший x Затем просматриваем его справа налево, пока не найдется элемент, меньший x
46 Суть сортировки: Меняем найденные элементы местами. В случае, если не найден наибольший или наименьший элементы, местами меняется средний элемент с найденным наибольшим или наименьшим элементом; Дойдя до середины имеем 2 части массива; Процесс продолжается для каждой части, пока массив не будет отсортирован
7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт" title="47 Быстрая сортировка 812371911416 Барьерный элемент 4378123 4 Барьерный элемент 8121119 Барьерный элемент 1219 1619 8>7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт" class="link_thumb">
47
47 Быстрая сортировка Барьерный элемент Барьерный элемент Барьерный элемент >7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэтому меняем местами 7 и 12 4>3 Отсортиро- ванная часть 12>11 переносим в правую часть, т. к >11 не переносим, 811 переносим в правую часть, т. к. 16>11, 12>11,не переносим, 11 11=11 поэтому меняем местами 11 и 19 Отсортированная часть 19>12 переносим в правую часть, т. к. 16>12,не переносим, 12 12=12 поэтому меняем местами 12 и 19 19>16 Массив отсортирован по возрастанию Меньше равно 7 Больше 7
7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт">
7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэтому меняем местами 7 и 12 4>3 Отсортиро- ванная часть 12>11 переносим в правую часть, т. к. 8 12 16>11 не переносим, 811 переносим в правую часть, т. к. 16>11, 12>11,не переносим, 11 11=11 поэтому меняем местами 11 и 19 Отсортированная часть 19>12 переносим в правую часть, т. к. 16>12,не переносим, 12 12=12 поэтому меняем местами 12 и 19 19>16 Массив отсортирован по возрастанию Меньше равно 7 Больше 7">
7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт" title="47 Быстрая сортировка 812371911416 Барьерный элемент 4378123 4 Барьерный элемент 8121119 Барьерный элемент 1219 1619 8>7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт">
title="47 Быстрая сортировка 812371911416 Барьерный элемент 4378123 4 Барьерный элемент 8121119 Барьерный элемент 1219 1619 8>7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт">
48 А n Пусть нужно отсортировать массив А по возрастанию, в котором n элементов быстрым методом Вспомогательные переменные: t – t –конечный элемент массива m - m - начальный элемент массива x – x – элемент относительно которого перемещаются все остальные элементы. w – w – промежуточное значение, используемое для перемещения элементов массива Постановка задачи
58 Устойчивость – отсортированный массив не меняет порядок элементов с одинаковыми значениями. Взаимное расположение равных элементов с ключом 1 и дополнительными полями "a", "b", "c" Параметры оценки алгоритмов
59 Естественность поведения - эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведет себя естественно, если учитывает эту характеристику входной последовательности и работает лучше Параметры оценки алгоритмов 60 Оценка алгоритма сортировки выбором Общее количество сравнений C =N-l + N = (N 2 -N)/2 Общее количество операций n + (n-1) + (n-2) + (n-3) = 1/2 * (n 2 +n) = Theta(n 2) Число обменов
63 Оценка алгоритма сортировки вставкой Для массива потребуется N-1 сравнение. Для массива потребуется (N 2 -N)/2 сравнение. Общее количество операций Theta(n 2)
66 Не эффективный метод, так как включение элемента связано со сдвигом всех предшествующих элементов на одну позицию, а эта операция неэкономна В совокупности устойчивость и естественность поведения алгоритма, делает метод хорошим выбором в соответствующих ситуациях
70 Сравнение методов простой сортировки N N – количество элементов, M M – кол-во пересылок, C – кол-во сравнений МинимумМаксимум Простые включения M=2(n-1) C = n-1 M=2(n-1) С=(n 2 -n)/2 М=(n+3n-4)/2 М=(n 2 +3n-4)/2 Простой обмен C=(n 2 -n)/2M=3(n-1) С=(n 2 -n)/2 М=n/4+3(n-1) М=n 2 /4+3(n-1) Простой выбор C=(n 2 -n)/2 M = 0 С=(n 2 -n)/2 М=(n-n)*1,5 М=(n 2 -n)*1,5 ? Чему будет равно количество пересылок
72 Оценка алгоритма Шелла n 1.2 Время выполнения пропорционально n 1.2, т. к. при каждом проходе используется небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных
73 Оценка алгоритма быстрой сортировки N=2g X N N/2N/2 Если размер массива равен числу, являющемуся степенью двойки (N=2g), и при каждом разделении элемент X находится точно в середине массива, тогда при первом просмотре выполняется N сравнений и массив разделится на две части размерами N/2. Для каждой из этих частей N/2 сравнений и т. д. Следовательно C=N+2*(N/2)+4*(N/4)+...+N*(N/N). N Если N не является степенью двойки, то оценка будет иметь тот же порядок
74 Theta(n). Общее количество операций Theta(n). log n O(n log n) Количество шагов деления (глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n) O(n 2) Если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности, тогда быстродействие O(n 2)
77 Контрольные вопросы? Что такое «сортировка»? ? В чем заключается метод сортировки отбором? ? В чем заключается метод сортировки вставками? ? В чем заключается метод пузырьковой сортировки? ? В чем заключается метод быстрой сортировки? ? В чем заключается метод сортировки Шелла?
78 Контрольные вопросы? Какой алгоритм сортировки считается самым простым? ? Какой алгоритм сортировки считается самым эффективным? ? Сколько существует групп алгоритмов сортировки? ? По каким признакам характеризуются алгоритмы сортировки? ? Что нужно учитывать при выборе алгоритма сортировки?
Существует три общих метода сортировки массивов:
Чтобы понять, как работают эти методы, представьте себе колоду игральных карт. Чтобы отсортировать карты методом обмена
, разложите их на столе лицом вверх и меняйте местами карты, расположенные не по порядку, пока вся колода не будет упорядочена. В методе выбора
разложите карты на столе, выберите карту наименьшей значимости и положите ее в руку. Затем из оставшихся карт снова выберите карту наименьшей значимости и положите ее на ту, которая уже находится у вас в руке. Процесс повторяется до тех пор, пока в руке не окажутся все карты; по окончании процесса колода будет отсортирована. Чтобы отсортировать колоду методом вставки
, возьмите все карты в руку. Выкладывайте их по одной на стол, вставляя каждую следующую карту в соответствующую позицию. Когда все карты окажутся на столе, колода будет отсортирована. Сортировка вставками
Сортировка вставками
- простой алгоритм сортировки. Хотя этот алгоритм уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ: · эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим; · эффективен на наборах данных, которые уже частично отсортированы; · это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы); · может сортировать список по мере его получения; Минусом -высокая сложность алгоритма: O(n
²) Вообще говоря, в худших случаях сортировка вставками настолько же плоха, как и пузырьковая сортировка и сортировка посредством выбора, а в среднем она лишь немного лучше. Описание
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Анализ Алгоритма
Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим - массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных - θ(n²). Реализация на java
public void
addingSort() { for
(Node cur = first.next; cur != null
; cur = cur.next) { Node n = cur.prev; Object val = cur.value; for
(; n != null
; n = n.prev) { if
(((Comparable) n.value).compareTo(val)
> 0) { n.next.value = n.value; } else
{ if
(n != null
) { n.next.value = val; } else
{ first.value = val; Сначала он сортирует два первых элемента. Затем алгоритм вставляет третий элемент в соответствующую порядку позицию по отношению к первым двум элементам. После этого он вставляет четвертый элемент в список из трех элементов. Этот процесс повторяется до тех пор, пока не будут вставлены все элементы. Например
, при сортировке массива dcab
каждый проход алгоритма будет выглядеть следующим образом: Начало d c a b
Проход 1 c d a b
Проход 2 a c d b
Проход 3 a b c d
Сортировка выбором
Описание
При сортировке из массива выбирается элемент с наименьшим значением и обменивается с первым элементом. Затем из оставшихся n
- 1 элементов снова выбирается элемент с наименьшим ключом и обменивается со вторым элементом, и т.д. Эти обмены продолжаются до двух последних элементов. Например
, если применить метод выбора к массиву dcab
, каждый проход будет выглядеть так: Анализ
К сожалению, как и в пузырьковой сортировке, внешний цикл выполняется n
- 1 раз, а внутренний - в среднем n
/2 раз. Следовательно, сортировка посредством выбора требует 1/2(n
2 -n
)
сравнений. Таким образом, это алгоритм порядка n
2 , из-за чего он считается слишком медленным для сортировки большого количества элементов. Несмотря на то, что количество сравнений в пузырьковой сортировке и сортировке посредством выбора одинаковое, в последней количество обменов в среднем случае намного меньше, чем в пузырьковой сортировке. Реализация на java
public void
SelectSort() { for
(Node a = first; a != last; a = a.next) { Node min = last; for
(Node b = a; b != last; b = b.next) { if
(((Comparable) b.val).compareTo(min.val)
< 0) { a.val = min.val; Сортировка Обменом
Самый известный алгоритм - пузырьковая сортировка
. Его популярность объясняется интересным названием и простотой самого алгоритма. Тем не менее, в общем случае это один из самых худших алгоритмов сортировки. Пузырьковая сортировка относится к классу обменных сортировок, т.е. к классу сортировок методом обмена. Ее алгоритм содержит повторяющиеся сравнения (т.е. многократные сравнения одних и тех же элементов) и, при необходимости, обмен соседних элементов. Элементы ведут себя подобно пузырькам воздуха в воде - каждый из них поднимается на свой уровень. Чтобы наглядно показать, как работает пузырьковая сортировка, допустим, что исходный массив содержит элементы dcab
. Ниже показано состояние массива после каждого прохода: Начало d c a b
Проход 1 a d c b
Проход 2 a b d c
Проход 3 a b c d
При анализе любого алгоритма сортировки полезно знать, сколько операций сравнения и обмена будет выполнено в лучшем, среднем и худшем случаях. Поскольку характеристики выполняемого кода зависят от таких факторов, как оптимизация, производимая компилятором, различия между процессорами и особенности реализации, мы не будем пытаться получить точные значения этих параметров. Вместо этого сконцентрируем свое внимание на общей эффективности каждого алгоритма. В пузырьковой сортировке количество сравнений всегда одно и то же, поскольку два цикла for повторяются указанное количество раз независимо от того, был список изначально упорядочен или нет. Это значит, что алгоритм пузырьковой сортировки всегда выполняет (n
2 -n
)/2 сравнений, где n
- количество сортируемых элементов. Данная формула выведена на том основании, что внешний цикл выполняется n
- 1 раз, а внутренний выполняется в среднем n
/2 раз. Произведение этих величин и дает предыдущее выражение. Обратите внимание на член n
2 в формуле. Говорят, что пузырьковая сортировка является алгоритмом порядка n
2 , поскольку время ее выполнения пропорционально квадрату количества сортируемых элементов. Необходимо признать, что алгоритм порядка n
2 не эффективен при большом количестве элементов, поскольку время выполнения растет экспоненциально в зависимости от количества сортируемых элементов. В алгоритме пузырьковой сортировки количество обменов в лучшем случае равно нулю, если массив уже отсортирован. Однако в среднем и худшем случаях количество обменов также является величиной порядка n
2 . Похожая информация.
Элементарные методы сортировки
В качестве нашей первой экскурсии в область алгоритмов сортировки, мы изучим некоторые «элементарные» методы которые хорошо работают для небольших файлов или файлов специальной структуры. Существует несколько причин, по которым желательно изучение этих простых методов. Во-первых, они дают нам относительно безболезненный способ изучить терминологию и основные механизмы работы алгоритмов сортировки, что позволяет получить необходимую базу для изучения более сложных алгоритмов. Во-вторых, для многих задач сортировки бывает лучше использовать простые методы, чем более сложные алгоритмы. И, наконец, некоторые из простых методов можно расширить до более хороших методов или использовать их для улучшения более сложных.В некоторых программах сортировки лучше использовать простые алгоритмы. Программы сортировки часто используются только один раз (или несколько раз). Если количество элементов, которые нужно отсортировать не велико (скажем меньше чем 500 элементов), то может статься, что использование простого алгоритма будет более эффективно, чем разработка и отладка сложного алгоритма. Элементарные методы всегда пригодны для маленьких файлов (скажем меньших, чем 50 элементов); маловероятно, что сложный алгоритм было бы разумно использовать для таких файлов, если конечно не нужно сортировать большое количество таких файлов.Как правило, элементарные методы, которые мы будем обсуждать, производят около операций для сортировки N
произвольно взятых элементов. Если N
достаточно мало, то это может и не быть проблемой, и если элементы распределены не произвольным образом, то эти алгоритмы могут работать даже быстрее, чем сложные. Однако следует запомнить то, что эти алгоритмы не следует использовать для больших, произвольно упорядоченных файлов, с одним единственным исключением для алгоритма оболочечной сортировки, который часто используется во многих программах.Правила Игры
Перед тем, как рассматривать какой-либо конкретный алгоритм, было бы полезно изучить терминологию и некоторые основные соглашения об алгоритмах сортировки. Мы будем изучать алгоритмы для сортировки файлов записей содержащих ключи . Ключи, которые являются только частью записи (часто очень маленькой их частью), используются для управления процессом сортировки. Целью алгоритма сортировки является переорганизация записей в файле так, чтобы они располагались в нем в некотором строго определенном порядке (обычно в алфавитном или числовом).
Если сортируемый файл целиком помещается в память (или целиком помещается в массив), то для него мы используем внутренние методы сортировки. Сортировка данных с ленты или диска называется внешней сортировкой. Главное отличие между ними состоит в том, что при внутренней сортировке любая запись легко доступна, в то время как при внешней сортировке мы можем пользоваться записями только последовательно, или большими блоками. Большинство алгоритмов сортировки, которые мы рассмотрим - внутренние.
Обычно, главное, что будет нас интересовать в алгоритме - это время его работы. Первые четыре алгоритма, которые мы рассмотрим, для сортировки N элементов имеют время работы пропорциональное, в то время как более сложные алгоритмы используют время пропорциональное. (Можно показать, что никакой алгоритм сортировки не может использовать менее, чем сравнений между ключами.) После изучения простых методов мы рассмотрим более сложные методы, время работы которых пропорционально и методы использующие бинарные свойства ключей для уменьшения общего времени работы до N.
Количество используемой дополнительной памяти алгоритма сортировки - это еще один важный фактор, который мы будем принимать во внимание. Вообще говоря, методы сортировки делятся на три типа:
методы сортировки, которые сортируют без использования дополнительной памяти, за исключением, возможно, небольшого стека и / или массива;
методы, которые используют для сортировки связанные списки и поэтому используют N дополнительных указателей хранящихся в памяти;
и методы, которые нуждаются в дополнительной памяти для хранения копии сортируемого файла.
Стабильность - еще одна немаловажная характеристика методов сортировки. Метод сортировки называется стабильным, если он сохраняет относительных порядок следования записей с одинаковыми ключами. Например, если алфавитный список группы сортируется по оценкам, то стабильный метод создает список, в котором фамилии студентов с одинаковыми оценками будут упорядочены по алфавиту, а нестабильный метод создаст список в котором, возможно, исходный порядок будет нарушен. Большинство простых методов стабильны, в то время как большинство хорошо известных сложных методов - нет. Если стабильность необходима, то она может быть достигнута посредством добавления к ключу небольшого индекса перед сортировкой или посредством удлинения, каким-либо образом, ключа. Стабильность с легкостью принимается за норму; к нестабильности люди относятся с недоверием. На самом же деле, лишь немногие методы достигают стабильности без использования дополнительного времени или места.
Следующая программа, для сортировки трех записей, предназначена для иллюстрации основных соглашений, которые мы будем использовать. В частности, главная программа любопытна тем, что она работает только для N=3; смысл в том, что любая программа сортировки может быть сведена к процедуре sort3 этой программы.
Три оператора присвоения, каждый из которых сопровождается оператором if, на деле реализуют операцию «обмена». Мы вставляем ее непосредственно в программный код вместо использования вызова процедуры, поскольку они являются основой многих алгоритмов и часто попадают внутрь цикла.
Чтобы сконцентрироваться на алгоритмических вопросах, мы будем работать с алгоритмами, которые просто сортируют массивы целых в численном порядке. В общем, очень легко адаптировать такие алгоритмы для практического использования, включающего в себя работу с большими ключами или записями. В основном программы сортировки работают с записями двумя способами: либо они сравнивают и сортируют только ключи, либо передвигают записи целиком. Большинство алгоритмов, которые мы изучим можно применять, посредством их переформулировки в терминах этих двух операций, для произвольных записей. Если сортируемые записи довольно большие, то обычно пытаются избежать передвижения их посредством «косвенной сортировки»: при этом сами записи не переупорядочиваются, а вместо этого переупорядочивается массив указателей (индексов), так, что первый указатель указывает на самый маленький элемент и так далее. Ключи могут храниться либо с записями (если они большие), либо с указателями (если они маленькие). Если необходимо, то после сортировки записи можно упорядочить. Это описано дальше.
Программа sort3 использует даже более ограниченный доступ к файлу: это три операции вида «сравнить две записи и обменять их, если нужно, чтобы поместить запись с меньшим ключом на первое место». Программы, ограниченные такими операциями интересны, поскольку они подходят для реализации на аппаратном уровне. Мы изучим их более подробно позднее.
Все примеры программ используют для сортировки глобальный массив. Это не означает, что такой подход лучше или хуже чем передача массива как параметра. Все зависит от точки зрения и конкретного алгоритма. Массив сделан глобальным только потому, что тогда примеры становятся короче и понятней.
Сортировка выбором Один из самых простых методов сортировки работает следующим образом: находим наименьший элемент в массиве и обмениваем его с элементом находящимся на первом месте. Потом повторяем процесс со второй позиции в файле и найденный элемент обмениваем со вторым элементном и так далее пока весь массив не будет отсортирован. Этот метод называется сортировка выбором, поскольку он работает, циклически выбирая наименьший из оставшихся элементов, как показано на рисунке 1. При первом проходе символ пробела уходит на первое место, обмениваясь с буквой `П". На втором проходе элемент `В" обменивается с элементом `Р" и так далее.Следующая программа дает полную реализацию этого процесса. Для каждого i от 1 до N - 1 , она обменивает наименьший элемент из a [i ..N] с a[i ]:По мере продвижения указателя i слева направо через файл, элементы слева от указателя находятся уже в своей конечной позиции (и их больше уже не будут трогать), поэтому массив становится полностью отсортированным к тому моменту, когда указатель достигает правого края.Этот метод - один из простейших, и он работает очень хорошо для небольших файлов. Его «внутренний цикл» состоит из сравнения a[i ]Для этого мы можем использовать следующую процедуру, которая физически упорядочивает записи файла используя при этом N перестановок:
Сортировка Шелла Сортировка вставкой работает медленно потому, что она обменивает только смежные элементы. Оболочечная сортировка является простейшим расширением сортировки вставкой, которая увеличивает скорость работы алгоритма за счет того, что позволяет обменивать элементы находящиеся далеко друг от друга.Основная идея алгоритма состоит в том, чтобы отсортировать все группы файла состоящие из элементов файла отстоящих друг от друга на расстояние h. Такие файлы называются h-сортированными. Когда мы h-сортируем файл по некоторому большому h, мы передвигаем его элементы на большие растояния. Это облегчает работу сортировки для меньших значений h. Процесс заканчивается когда h уменьшается до 1.Приведенная программа использует последовательность… 1093, 364, 121, 40, 13, 4, 1. Могут существовать и другие последовательности - одни лучше, другие хуже.
Свойство 6 Оболочечная сортировка никогда не делает более чем N 1.5 сравнений для вышеуказанной последовательности h.
Подсчет распределения Во многих случаях мы знаем, что значения ключей в файле лежат в каких либо пределах. В этих ситуациях применим алгоритм, именуемый подсчет распределения. Здесь приведена программа для этого простого алгоритма.
