Презентация по сортировкам. Алгоритмы сортировки массивов структурированные типы данных массивы 1
 Скачать 1.31 Mb.
|
|
АЛГОРИТМЫ СОРТИРОВКИ МАССИВОВ Структурированные типы данных: массивы 1 Ахмадулин Р.К. Лозикова И.О. Понятие алгоритма сортировки 2 Алгоритм сортировки – это алгоритм для упорядочивания элементов в списке Использование алгоритмов сортировки 3 Пример использования – сортировка массивов чисел X X 3 1 6 2 1 3 9 4 7 5 2 6 8 7 5 8 4 9 Сортировка Использование алгоритмов сортировки 4 Сортировка массива может осуществляться как по значениям, так и по ключу Ключ сортировки – поле, служащее критерием порядка, в случае, когда элемент списка имеет несколько полей. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма. Пример: сортировка студентов по средней усеваемости Сортировка по ключу 5 Пример использования – сортировка массивов чисел ключ значение ключ значение 3 Сидоров 1 Иванов 6 Николаев 2 Петров 1 Иванов 3 Сидоров 9 Тимофеев 4 Борисов 7 Дмитриев 5 Андреев 2 Петров 6 Николаев 8 Алексеев 7 Дмитриев 5 Андреев 8 Алексеев 4 Борисов 9 Тимофеев Алгоритмы сортировки 6 Сортировка выбором Сортировка вставкой Сортировка обменом Быстрая сортировка Сортировка Шелла Сортировка слиянием Сортировка расчёской Пирамидальная сортировка Плавная сортировка и др. Свойства и классификация 7 Устойчивость устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами Естественность поведения эффективность метода при обработке уже упорядоченных или частично упорядоченных данных алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше Использование операции сравнения алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях Оценка алгоритма сортировки 8 Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти Время – характеризует быстродействие алгоритма и называется вычислительной сложностью. различают худшее, среднее и лучшее поведение алгоритма на разных наборах исходных данных для типичного алгоритма хорошее поведение – O(n log n) и плохое – это O(n 2 ) идеальное поведение для упорядочения – O(n). Память – ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. как правило, такие алгоритмы требуют O(log n) памяти при оценке не учитывается место, которое занимает исходный массив алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте Постановка задачи 9 Имеется массив целых чисел. Отсортировать его в порядке возрастания. const int n=20; int mass [n]; … Sort(n, mass); ПРОСТЕЙШИЕ АЛГОРИТМЫ СОРТИРОВКИ Сортировка выбором, Сортировка вставками, Сортировка обменом 10 Сортировка выбором Линейная сортировка 11 Идея алгоритма: находит в массиве минимальное(максимальное) число и вставляет его на первое место. Затем повторяет операцию для остальных чисел Сортировка выбором 12 Шаги алгоритма: 1. находим номер минимального значения в текущем списке; 2. производим обмен этого значения со значением первой неотсортированной позиции; 3. переходим к шагу 1 и сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы. X X X X X 3 1 1 1 1 4 4 2 2 2 1 3 4 3 3 5 5 5 5 4 2 2 3 4 5 Сортировка выбором 13 Алгоритм неустойчивой сортировки Основан на сравнениях Не требует дополнительного выделения памяти Сложность алгоритма: O(n 2 ) (в лучшем, среднем и худшем случаях) Программа сортировки выбором 14 // линейная сортировка void LineSort ( int n, int mass[ ]) { for (int i = 0 ; i < n-1; i++) for (int j = i+1 ; j < n ; j++) if (mass[ j ]< mass[ i ]) { int temp=mass[i]; mass[ i ] = mass[ j ]; mass[ j ] = temp; } } Сортировка вставками 15 Идея алгоритма: На каждом шаге алгоритма выбирается один из элементов и вставляется на нужную позицию в уже отсортированном списке до тех пор, пока набор входных данных не будет исчерпан. Эффективен на небольших наборах данных (до десяти элементов) Может сортировать список по мере его получения Сортировка вставками 16 Шаги алгоритма: 1. выбираем первый неотсортированный элемент в списке; 2. двигаем его к началу до своей позиции; 3. переходим к шагу 1 и повторяем операцию со следующим элементом. X X X X X 3 3 1 1 1 4 4 3 3 2 1 1 4 4 3 5 5 5 5 4 2 2 2 2 5 Сортировка вставками 17 Алгоритм устойчивой сортировки Основан на сравнениях Эффективен на наборах данных, которые уже частично отсортированы Сложность алгоритма: O(n 2 ) Лучшее время: O(n) Среднее время: O(n 2 ) Худшее время: O(n 2 ) Программа сортировки 18 // сортировка вставками void Sort(int n, int mass[]) { int newElement, location; for (int i = 1 ; i < n; i++) { newElement = mass[i]; location = i - 1; while (location >= 0 && mass[location] > newElement) { mass[location + 1] = mass[location]; location = location - 1; } mass[location + 1] = newElement; } } Сортировка обменом - пузырьковая сортировка 19 Идея алгоритма: Осуществляются перестановки соседних элементов в порядке возрастания до тех пор, пока перестановки не потребуются Сортировка обменом 20 Шаги алгоритма: 1. проходим по массиву сравнивая и, если нужно, меняя местами соседние элементы; 2. если массив не отсортирован, то переходим к шагу 1. X X X X 3 3 1 1 4 1 3 2 1 4 2 3 5 2 4 4 2 5 5 5 Сортировка обменом 21 Алгоритм устойчивой сортировки с естественным поведением Основан на сравнениях Простейший алгоритм, эффективен лишь на небольших массивах, считается учебным Сложность алгоритма: O(n 2 ) Лучшее время: O(n) Среднее время: O(n 2 ) Худшее время: O(n 2 ) Программа сортировки обменом 22 // пузырьковая сортировка void BubbleSort ( int n, int mass[ ]) { bool flag=true; while (flag) { flag=false; for (int i=0 ; i < n-1 ; i++) if (mass[ i ]< mass[ i+1]) { int temp=mass[ i ]; mass[ i ] = mass[i+1]; mass[ i+1 ] = temp; flag= true; } } } УЛУЧШЕННЫЕ АЛГОРИТМЫ СОРТИРОВКИ Быстрая сортировка, Сортировка слиянием, Сортировка Шелла и др. 23 Быстрая сортировка 24 изобретена Чарльзом Хоаром во время работы в МГУ в 1960 г. Идея алгоритма: Выбрать из массива опорный элемент. Сравнить все элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка: «меньшие опорного», «равные» и «большие». Для «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы. Быстрая сортировка 25 Шаги алгоритма: 1. Выбираем в массиве опорный элемент (случайный, средний по положению, среднее арифметическое и т.п.). 2. Реорганизуем массив так, чтобы все элементы со значением <= опорного элемента, оказались слева от него, а все элементы > опорный – справа. Два индекса – l и r, приравниваем к мин. и макс. индексу массива Вычисляем индекс опорного элемента m Индекс l увеличиваем до тех пор, пока l-й элемент не окажется >= опорного Индекс r уменьшаем до тех пор, пока r-й элемент не окажется <= опорного Если r = l – операция разделения закончена, оба индекса указывают на опорный. Если l < r – меняем их местами и продолжаем операцию 3. Рекурсивно упорядочиваем подмассивы слева и справа от опорного, если они содержат более двух элементов. Быстрая сортировка 26 Программа 27 void qs(int *s_arr, int first, int last) { if (first < last) { int left = first, right = last, middle = s_arr[(left + right) / 2]; do { while (s_arr[left] < middle) left++; while (s_arr[right] > middle) right--; if (left <= right) { int tmp = s_arr[left]; s_arr[left] = s_arr[right]; s_arr[right] = tmp; left++; right--; } } while (left <= right); qs(s_arr, first, right); qs(s_arr, left, last); } } Быстрая сортировка 28 Алгоритм неустойчивой сортировки Основан на сравнениях Один из самых быстрых известных универсальных алгоритмов сортировки массивов Сложность алгоритма: O(n log n) Лучшее время: O(n log n) Среднее время: О(n log n) Худшее время: О(n 2 ) Быстрая сортировка – достоинства и недостатки 29 Достоинства: Один из самых быстродействующих алгоритмов внутренней сортировки. Прост в реализации. Допускает естественное распараллеливание. Допускает эффективную модификацию для сортировки по нескольким ключам (отрезок элементов, равных опорному, можно сразу же сортировать по следующему ключу). Недостатки: Сильно деградирует по скорости в худшем или близком к нему случае (при неудачных входных данных). Прямая реализация в виде функции с двумя рекурсивными вызовами может привести к ошибке переполнения стека. Сортировка слиянием 30 изобретена Джоном фон Нейманом в 1945 г. Идея алгоритма: сортировка по принципу «разделяй и властвуй»: задача разбивается на несколько подзадач меньшего размера, каждая из которых решаются с помощью рекурсивного вызова этого же алгоритма. Сортировка слиянием 31 Шаги алгоритма: 1. Сортируемый массив разбивается на две части примерно одинакового размера. 2. Каждая из получившихся частей сортируется отдельно, например – тем же самым алгоритмом. 3. Два упорядоченных массива половинного размера соединяются в один упорядоченный Сортировка слиянием 32 Сортировка слиянием 33 Требуется реализовать: 1. Процедуру для склеивания двух отсортированных половин массива в один отсортированный массив (используется дополнительный массив) 2. Процедуру, которая рекурсивно сортирует массив путем его разбиения на половины, сортировки каждой по отдельности и склеивания результатов Сортировка слиянием 34 Алгоритм устойчивой сортировки Основан на сравнениях Требует O(n) дополнительной памяти Сложность алгоритма: O(n log n) Лучшее время: O(n log n) Среднее время: О(n log n) Худшее время: О(n log n) Сортировка Шелла 35 изобретена Дональдом Шеллом и опубликована в 1959 г. Идея алгоритма: усовершенствованный вариант сортировки вставками; сравниваются элементы, стоящие не только рядом, но и на определённом расстоянии друг от друга. Фактически – это сортировка вставками с предварительными «грубыми» проходами Эффективность обеспечивается тем, что элементы «быстрее» встают на свои места Сортировка Шелла 36 Шаги алгоритма: сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии d ; процедура повторяется для некоторых меньших значений d ; завершается сортировка упорядочиванием элементов при d = 1 (т.е. обычной сортировкой вставками). Сортировка Шелла 37 Сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, однако и преимущества: отсутствие потребности в памяти под стек; худшее гарантированное время для сортировки Шелла лучше, чем худшее время для быстрой сортировки. Среднее время работы алгоритма зависит от длин промежутков d . Существует несколько подходов к выбору этих значений. Например: первоначально используемая Шеллом последовательность длин промежутков: Сортировка Шелла 38 Алгоритм неустойчивой сортировки Основан на сравнениях Сложность алгоритма: O(n log 2 n) Лучшее время: O(n log 2 n) Среднее время: зависит от выбранных шагов Худшее время: О(n 2 ) Сортировка расчёской 39 спроектирован Влодзимежом Добосиевичем в 1980 г. переоткрыт в статье Стивена Лэйси и Ричарда Бокса в 1991 г. Идея алгоритма: улучшает сортировку пузырьком; устраняет «черепах», т.е. маленькие значения в конце списка, которые крайне замедляют сортировку пузырьком Подобно алгоритму Шелла, увеличивает расстояние между сравниваемыми элементами Сортировка расчёской 40 Шаги алгоритма: 1. Сначала расстояние между сравниваемыми элементами берется равным размеру массива, разделённого на фактор уменьшения (результат округляется до ближайшего целого). 2. Затем, пройдя массив с этим шагом, необходимо поделить шаг на фактор уменьшения и пройти по списку вновь. 3. Продолжаем до тех пор, пока разность индексов не достигнет единицы: в этом случае массив досортировывается обычным пузырьком. Оптимальное значение фактора уменьшения равно примерно 1,247 Сортировка расчёской 41 Алгоритм неустойчивой сортировки Основан на сравнениях Сложность алгоритма: O(n log n) Лучшее время: O(n) Худшее время: О(n 2 ) ПРОЧИЕ ИДЕИ, ИСПОЛЬЗУЕМЫЕ В АЛГОРИТМАХ СОРТИРОВКИ представлено без программного кода, изучить и построить самостоятельно 42 Практика Пирамидальная сортировка 43 предложен Дж. Уильямсом в 1964 г. Идея алгоритма: Может рассматриваться как усовершенствованная сортировка пузырьком; элемент всплывает / тонет по многим путям. использует бинарное сортирующее дерево. Пирамидальная сортировка 44 Шаги алгоритма: 1. Выстраиваем элементы массива в виде сортирующего дерева: 2. Удаляем элементы из корня по одному за раз и перестраиваем дерево. на первом шаге обмениваем Array[1] и Array[n] преобразовываем Array[1], Array[2], … , Array[n-1] в сортирующее дерево; переставляем Array[1] и Array[n-1] преобразовываем Array[1], Array[2], … , Array[n-2] в сортирующее дерево … (продолжаем процесс до тех пор, пока в сортирующем дереве не останется один элемент) Пирамидальная сортировка 45 Алгоритм неустойчивой сортировки Основан на сравнениях Требует O(1) дополнительной памяти (т.е. сортирует на месте) Сложность алгоритма: O(n log n) (в худшем, среднем и лучшем случаях ) Недостатки сложен в реализации на почти отсортированных массивах работает столь же долго, как и на хаотических данных Плавная сортировка 46 разработан Эдсгером Дейкстра в 1981 г. Идея алгоритма: разновидность пирамидальной сортировки; в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи; В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо ( L(n) = L(n-1) + L(n-2) + 1 ). Плавная сортировка 47 Алгоритм неустойчивой сортировки Основан на сравнениях Требует O(1) дополнительной памяти (т.е. сортирует на месте) Сложность алгоритма: O(n log n) Лучшее время: O(n) Среднее время: О(n log n) Худшее время: О(n log n) Интроспективная сортировка 48 предложен Дэвидом Мюссером в 1997 г. Идея алгоритма: использует быструю сортировку и переключается на пирамидальную; пирамидальная сортировка применяется в случае, если глубина рекурсии превышает log n. Интроспективная сортировка 49 Алгоритм неустойчивой сортировки Основан на сравнениях Сложность алгоритма: O(n log n) Среднее время: О(n log n) Худшее время: О(n log n) Timsort 50 опубликована Тимом Петерсом в 2002 г. Идея алгоритма: гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием; учитывает то, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы (на таких массивах – быстрее многих других алгоритмов). Основные шаги алгоритма: по специальному алгоритму входной массив разделяется на подмассивы; каждый подмассив упорядочивается сортировкой вставками; отсортированные подмассивы собираются в единый массив с помощью модифицированной сортировки слиянием. Timsort 51 Алгоритм устойчивой сортировки Основан на сравнениях Требует O(n) дополнительной памяти Сложность алгоритма: O(n log n) Лучшее время: О(n) Среднее время: О(n log n) Худшее время: О(n log n) Является стандартным алгоритмом сортировки в Python, OpenJDK 7 и реализован в Android JDK 1.5 Некоторые другие сортировки 52 Устойчивые алгоритмы: Сортировка перемешиванием [ O(n 2 ) ] – разновидность пузырьковой сортировки, в которой изменяются границы рабочей области массива, а сам массив поочередно просматривается слева направо и справа налево. Гномья сортировка [ O(n 2 ) ] – похож на сортировку вставками, но перед вставкой на нужное место производит серию обменов, как в сортировке пузырьком. Сортировка с помощью двоичного дерева, дерева выбора [ O(n log n) ] – строит двоичное дерево поиска по ключам массива, является оптимальной при получении данных путём непосредственного чтения с потока. Некоторые другие сортировки 53 Неустойчивые алгоритмы: Терпеливая сортировка [ O(n log n) ] – находит самую длинную увеличивающуюся подпоследовательность. Поразрядная сортировка (цифровая сортировка) [ O(nk) ] – сортирует числа по разрядам. LSD ( least significant digit) сортировка - с выравниванием в сторону младшего разряда, направо, порядок, уместный для чисел, здесь значения сначала сортируются по единицам, затем сортируются по десяткам, сохраняя отсортированность по единицам внутри десятков, затем по сотням, сохраняя отсортированность по десяткам и единицам внутри сотен, и т. п. MSD (most significant digit) сортировка- с выравниванием в сторону старшего разряда, налево, получается алфавитный порядок, который уместен для сортировки строк текста. Некоторые другие сортировки 54 Непрактичные алгоритмы: Bogosort (случайная сортировка) [ O(n * n!) ] – произвольно перемешать массив, проверить порядок. Используется только в образовательных целях, т.к. массив из 10 элементов будет сортироваться в среднем более года. Глупая сортировка [ O(n 3 ) ] – похож на пузырьковую, но после обмена возврщается в начало массива. Блинная сортировка [ O(n 3 ) ] – единственная операция, допустимая в алгоритме – переворот элементов последовательности до какого-либо индекса. Некоторые другие сортировки 55 Не основанные на сравнениях: Сортировка подсчётом [ O(n + k) ] – используется диапазон чисел (k) сортируемого массива для подсчёта совпадающих элементов. Применение целесообразно лишь тогда, когда сортируемые числа имеют диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством. Устойчивая. Блочная сортировка [ O(n) ] – сортируемые элементы распределяются между конечным числом отдельных блоков так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Требует знания о природе сортируемых данных. Устойчивая. Поразрядная сортировка – см. неустойчивые сортировки. |