Способ сортировки массива это

Конспект обзорной лекция № 33

для студентов специальности «Прикладная математика»

доцента кафедры ИВТ, к.т.н. Ливак Е.Н.

ОСНОВНЫХ АЛГОРИТМОВ ОБРАБОТКИ ДАННЫХ

Основные понятия, факты

Поиск. Алгоритмы поиска. Методы сортировки. Прямые и улучшенные методы сортировки. Оценка их быстродействия. Рекурсивные алгоритмы. Примеры реализации.

Эффективная реализация основных алгоритмов обработки данных.

Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – 2-е изд., испр. – СПб: Невский Диалект, 2001. – 352 с.

Всем алгоритмам присущи некоторые общие свойства. Перечислим эмпирические (подмеченные на практике) свойства:

· понятность (доступность) – все действия, описанные в алгоритме должны быть понятны исполнителю, то есть должны принадлежать системе действий данного исполнителя.

· определенность (детерминированность) – каждое действие должно быть четко и однозначно определено. «Точное предписание», то есть, предписание, задающее алгоритм, должно выполняться однозначно и последовательно для получения конкретного и однозначного результата;

· конечность – выполнение алгоритма должно завершиться за конечное число шагов;

· результативность (сходимость) – достижение после конечного числа шагов искомого результата;

· дискретность (дискретная структура) – исполнение алгоритма должно состоять из отдельных шагов; Алгоритм представляет собой упорядоченное конечное множество шагов для получения результата. А всякое множество обладает свойством дискретности, то есть в любом алгоритме для каждого шага (кроме последнего), можно указать следующий за ним шаг.

· массовость – состоит в том, что алгоритм служит не для решения какой-то одной задачи, а для целого класса однотипных задач. Алгоритм — это единый метод, позволяющий по любому исходному объекту из определенного бесконечного множества исходных объектов получить искомый результат.

· Конструктивность объектов . Исходные объекты, промежуточные и конечные результаты — это конструктивные объекты, которые могут быть построены целиком или допускают кодирование в каких-то алфавитах. Не все математические объекты конструктивны. Например, иррациональные числа, выражающиеся бесконечными десятичными непериодическими дробями, не являются конструктивными объектами, так как иррациональное число не удается ни построить целиком, ни закодировать в каком-то алфавите.

Под алгоритмом понимается единый метод решения определенного класса однотипных задач, обладающий свойством дискретности, массовости, определенности, результативности и оперирующий конструктивными объектами.

Основные (базовые) алгоритмы обработки данных

К основным алгоритмам обработки данных мы будем относить алгоритмы, реализующие наиболее часто встречающиеся в программировании действия.

Такими действиями являются поиск заданного элемента в некотором наборе данных и сортировка наборов данных. Кроме того, к базовым алгоритмам принято относить так называемые рекурсивные алгоритмы в связи с тем, что рекурсия достаточно часто встречается (используется) как в повседневной жизни, так и в математике и компьютерных науках.

Сортировка — это процесс упорядочивания наборов данных одного типа по возрастанию или убыванию значения какого-либо признака.

Например, 25 10 5 76 — неотсортированный массив целых чисел

5 10 15 20 25 — отсортированный по возрастанию массив целых чисел

25 20 15 10 5 — отсортированный по убыванию массив целых чисел

Пусть x : array [1.. n ] of .

Тогда, если для любого k выполнено условие

· x [ k ] x [ k +1], то массив упорядочен по возрастанию

· x [ k ] > x [ k +1], то массив упорядочен по убыванию

· x [ k ] x [ k +1], то массив упорядочен по невозрастанию

· x [ k ] > = x [ k +1], то массив упорядочен по неубыванию

При конструировании эффективных программ (подпрограмм), осуществляющих сортировку массивов, требуется использование

· быстродействующих алгоритмов и

· минимальное использование дополнительной памяти.

В качестве показателя быстродействия алгоритма используют оценку

1) количества операций присваивания;

2) количества операций сравнения.

Методы сортировки делятся на

1. Прямые методы сортировки.

2. Улучшенные методы сортировки.

ПРЯМЫЕ МЕТОДЫ СОРТИРОВКИ

1. Сортировка обменом (метод «пузырька»).

2. Сортировка выбором.

3. Сортировка вставками.

УЛУЧШЕННЫЕ МЕТОДЫ СОРТИРОВКИ

используют те же принципы, что и прямые методы, но улучшают быстродействие сортировки с помощью оригинальных идей.

На практике чаще применяются улучшенные методы сортировки, так как прямые методы имеют относительно низкое быстродействие.

Однако, при небольшой длине массива и/или особом исходном расположении элементов, прямые методы также дают хороший результат.

Рассмотрим принципы основных (прямых) методов сортировки.

Сортировка обменом (метод «пузырька»)

Последовательно сравниваются пары соседних элементов x [ k ] и x [ k +1] ( k = 1,2, . , n -1) и, если их взаиморасположение не удовлетворяет заданному условию, то они переставляются (меняются местами).

Отыскивается максимальный (минимальный) элемент и переносится в конец массива. Затем этот метод применяется ко всем элементам, кроме последнего (он уже находится на своем месте) и т.д.

Другой вариант метода — перенос найденного элемента в начало массива и последующее применение метода ко всем элементам, кроме первого и т.д.

Массив разделяется на две части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть таким образом, что не нарушают упорядоченность элементов. В начале в качестве отсортированной части принимают только один первый элемент.

По числу сравнений все методы имеют квадратичную зависимость от длины массива

По числу присваиваний:

· методы обмена и вставки имеют квадратичную зависимость от длины массива

· метод выбора имеет число присваиваний порядка n * ln ( n )

Специалисты советуют использовать метод выбора для сортировки сложных структур данных, в случаях, когда на одно сравнение выполняется большое число присваиваний.

В среднем методы вставки и выбора оказываются приблизительно эквивалентными и в несколько раз (в зависимости от длины массива) лучше, чем метод обмена.

К улучшенным методам сортировки относятся, например, следующие алгоритмы:

ü сортировка с помощью включений с уменьшающимися расстояниями;

ü сортировка с помощью дерева;

ü сортировка с помощью разделения (быстрая сортировка Хоара)

РЕКУРСИВНЫЕ АЛГОРИТМЫ

Встречаются такие случаи, когда задача разбивается на подзадачи, которые в свою очередь имеют ту же структуру, что и основная задача.

В таких случаях используют механизм, который называется рекурсией.

Способ вызова подпрограммы, в котором подпрограмма вызывает сама себя, называют рекурсией.

Подпрограммы, реализующие рекурсию, называются рекурсивными подпрограммами.

Поясним механизм рекурсивных подпрограмм с помощью классического примера использования рекурсии.

Вычисление факториала числа.

Обоснование выбора способа реализации.

Обратим внимание на то, что вычислить факториал числа N можно следующим образом:

Реализуем такой алгоритм с использованием механизма рекурсии.

Так как подпрограмма будет производить вычисление значения, то реализовывать ее будем в виде функции.

function Fact (n: byte) : integer;

if n = 0 then Fact := 1

else Fact := n * Fact(n-1);

Описанный выше механизм часто называют прямой рекурсии.

Существует еще один рекурсивный механизм — косвенная рекурсия.

Механизм применяется для реализации следующей ситуации.

Первая подпрограмма вызывает вторую, еще не описанную.

Продемонстрируем ситуацию на примере.

procedure A (var x: real);

procedure B (var y: real);

Здесь процедура А обращается к процедуре B и наоборот. Какую процедуру первой мы бы ни описали, в любом случае будет ошибка – обращение к еще не описанной процедуре.

Для того, чтобы избежать такой ситуации, используется предварительное описание подпрограмм.

Предварительное описание состоит из заголовка подпрограммы и директивы (указания компилятору) предварительного описания подпрограмм FORWARD .

Позже подпрограмма описывается без повторения списка параметров и типа возвращаемого результата.

Правильная реализация вышеприведенного примера будет выглядеть следующим образом.

Источник

Сортировки и O-нотация

Задача сортировки массива заключается в том, чтобы расставить его элементы в определённом порядке (чаще всего — по неубыванию: каждый элемент должен быть больше или равен предыдущему).

Будет полезно вместе с описанем алгоритмов смотреть их визуализацию.

Сортировка пузырьком

Наш первый подход будет заключаться в следующем: обозначим за $n$ длину массива и $n$ раз пройдёмся раз пройдемся по нему, меняя два соседних элемента, если первый больше второго.

Как каждую итерацию максимальный элемент «всплывает» словно пузырек к концу массива — отсюда и название.

После $i$ шагов алгоритма сортировки пузырьком последние $(i + 1)$ чисел всегда отсортированы, а значит алгоритм работает корректно.

Упражнение. Алгоритм можно немного ускорить. Подумайте, какие лишние элементы мы перебираем. Как нужно изменить границы в двух циклах for , чтобы не делать никаких бесполезных действий?

Сортировка выбором

Другим способом является сортировка выбором минимума (или максимума).

Чтобы отсортировать массив, просто $n$ раз выберем минимум среди еще неотсортированных чисел и поставим его на свое место. На $i$ -ом шаге будем искать минимум на отрезке $[i, n — 1]$ и менять его местами с $i$ -тым элементом, после чего отрезок $[0, i]$ будет отсортирован.

Содержательная часть будет выглядеть так:

Сортировка вставками

Определение. Префиксом длины $i$ будем называть первые $i$ элементов массива.

Тогда пусть на $i$ -ом шаге у нас уже будет отсортирован префикс до $i$ -го элемента. Чтобы этот префикс увеличить, нужно взять элемент, идущий после него, и менять с левым соседом, пока этот элемент наконец не окажется больше своего левого соседа. Если в конце он больше левого соседа, но меньше правого, то это будет означать, что мы правильно вставили этот элемент в отсортированную часть массива.

Сортировка подсчетом

Предыдущие три алгоритма работали с массивами, в которых лежат абсолютно любые объекты, которые можно сравнивать: любые числа, строки, пары, другие массивы — почти все что угодно.

Но особых случаях, когда элементы принадлежат какому-то маленькому множеству, можно использовать другой алгоритм — сортировку подсчетом.

Пусть, например, нам гарантируется, что все числа натуральные и лежат в промежутке от $1$ до $100$ . Тогда есть такой простой алгоритм:

Создадим массив размера $100$ , в котором будем хранить на $k$ -ом месте, сколько раз число $k$ встретилось в этом массиве.

Пройдемся по всем числам исходного массива и увеличим соответствующее значение массива на $1$ .

После того, как мы посчитали, сколько раз каждое число встретилось, можно просто пройтись по этому массиву и вывести $1$ столько раз, сколько встретилась $1$ , вывести $2$ столько раз, сколько встретилась $2$ , и так далее.

Время работы такого алгоритма составляет $O(M+N)$ , где $M$ — число возможных значений, $N$ — число элементов в массиве. Сейчас мы расскажем, что же это означает.

О-нотация

Часто требуется оценить, сколько времени работает алгоритм. Но тут возникают проблемы:

на разных компьютерах время работы всегда будет слегка отличаться;
чтобы измерить время, придётся запустить сам алгоритм, но иногда приходится оценивать алгоритмы, требующие часы или даже дни работы.

Зачастую основной задачей программиста становится оптимизировать алгоритм, выполнение которого займёт тысячи лет, до какого-нибудь адекватного времени работы. Поэтому хотелось бы уметь предсказывать, сколько времени займёт выполнение алгоритма ещё до того, как мы его запустим.

Для этого сначала попробуем оценить число операций в алгоритме. Возникает вопрос: какие именно операции считать. Как один из вариантов — учитывать любые элементарные операции:

арифметические операции с числами: +, -, *, /
сравнение чисел: , =, ==, !=
присваивание: a[0] = 3

При этом надо учитывать, как реализованы некоторые отдельные вещи в самом языке. Например, в питоне срезы массива ( array[3:10] ) копируют этот массив, то есть этот срез работает за 7 элементарных действий. А swap , например, может работать за 3 присваивания.

Упражнение. Попробуйте посчитать точное число сравнений и присваиваний в сортировках пузырьком, выбором, вставками и подсчетом в худшем случае (это должна быть какая формула, зависящая от $n$ — длины массива).

Чтобы учесть вообще все элементарные операции, ещё надо посчитать, например, сколько раз прибавилась единичка внутри цикла for . А ещё, например, строчка n = len(array) — это тоже действие. Поэтому даже посчитав их, сразу очевидно, какой из этих алгоритмов работает быстрее — сравнивать формулы сложно. Хочется придумать способ упростить эти формулы так, чтобы:

не нужно было учитывать много информации, не очень сильно влияющей на итоговое время;
легко было оценивать время работы разных алгоритмов для больших чисел;
легко было сравнивать алгоритмы на предмет того, какой из них лучше подходит для тех или иных входных данных.

Для этого придумали $O$ -нотацию — асимптотическое время работы вместо точного (часто его ещё называют асимптотикой).

Определение. Пусть $f(n)$ — это какая-то функция. Говорят, что алгоритм работает за $O(f(n))$ , если существует число $C$ , такое что алгоритм работает не более чем за $C \cdot f(n)$ операций.

В таких обозначениях можно сказать, что

сортировка пузырьком работает за $O(n^2)$ ;
сортировка выбором работает за $O(n^2)$ ;
сортировка вставками работает за $O(n^2)$ ;
сортировка подсчетом работает за $O(n + m)$ .

Это обозначение удобно тем, что оно короткое и понятное, а также оно не зависит от умножения на константу или прибавления константы. Например, если алгоритм работает за $O(n^2)$ , то это может значить, что он работает за $n^2$ , за $n^2 + 3$ , за $\frac<2>$ или даже за $1000 \cdot n^2 + 1$ действие. Главное — что функция ведет себя как $n^2$ , то есть при увеличении $n$ (в данном случае это длина массива) он увеличивается как некоторая квадратичная функция. Например, если увеличить $n$ в 10 раз, время работы программы увеличится приблизительно в 100 раз.

Все рассуждения про то, сколько операций в swap или считать ли отдельно присваивания, сравнения и циклы — отпадают. Каков бы ни был ответ на эти вопросы, они меняют ответ лишь на константу, а значит асимптотическое время работы алгоритма никак не меняется.

Первые три сортировки именно поэтому называют квадратичными — они работают за $O(n^2)$ . Сортировка подсчетом может работать намного быстрее — она работает за $O(n + m)$ , а если в задаче $M \leq N$ , то это вообще линейная функция $O(n)$ .

Упражнение. Найдите асимптотику данных функций, маскимально упростив ответ (например, до $O(n)$ , $O(n^2)$ и т. д.):

Упражнение. Найдите асимптотическое время работы данных функций:

Упражнение. Найдите лучшее время работы алгоритмов, решающих данные задачи:

Написать числа от $1$ до $n$ .
Написать все тройки чисел от $1$ до $n$ .
Найти разницу между максимумом и минимумом в массиве.
Найти число единиц в бинарной записи числа $n$ .

Сортировки за $O(n \log n)$

Сортировка очень часто применяется как часть решения олимпиадных задач. В таких случаях обычно не пишут её заново, а используют встроенную.

Пример на Python:

В разных языках она может быть реализована по-разному, но везде она работает за $O(n \log n)$ , и, обычно, неплохо оптимизирована. Далее мы опишем два подхода к её реализации.

Сортировка слиянием

Найти количество пар элементов $a$ и $b$ в отсортированном массиве, такие что $b — a > K$ .

Наивное решение: бинарный поиск. Будем считать, что массив уже отсортирован. Для каждого элемента $a$ найдем первый справа элемент $b$ , который входит в ответ в паре с $a$ . Нетрудно заметить, что все элементы, большие $b$ , также входят в ответ. Итоговая асимптотика $O(n\log n)$ .

А можно ли быстрее?

Да, давайте перебирать два указателя — два индекса $first$ и $second$ . Будем перебирать $first$ просто слева направо и поддерживать для каждого $first$ первый элемент справа от него, такой что $a[second] — a[first] > K$ как $second$ . Тогда в пару к $a=a[first]$ подходят ровно $n-second$ элементов массив начиная с $second$ .

За сколько же работает это решение? С виду может показаться, что за $O(n^2)$ , но давайте посмотрим сколько раз меняется значение переменной $second$ . Так как оно изначально равняется нулю, только увеличивается и не может превысить $n$ , то суммарно операций мы сделаем $O(n)$ .

Это называется метод двух указателей — так как мы двигаем два указателя first и second одновременно слева направо по каким-то правилам. Обычно его используют на одном отсортированном массиве.

Давайте разберем еще примеры.

Слияние

Еще пример двух указателей на нескольких массивах.

Пусть у нас есть два отсортированных по неубыванию массива размера $n$ и $m$ . Хотим получить отсортированный массив размера $n + m$ из исходных.

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

Итоговая асимптотика: $O(n + m)$ .

Сортировка слиянием

Давайте подробно опишем как использовать операцию слияния для сортировки за $O(n\log n)$ .

Пусть у нас есть какой-то массив.

Сделаем такое предположение. Пусть мы уже умеем как-то сортировать массив размера $n$ . Тогда научимся сортировать массив размера $2n$ . Давайте разобьем наш массив на две половины, отсортируем каждую из них, а после это сделаем слияние двух массивов, которое мы научились делать за $O(n)$ в данных условиях. Также заметим, что массив размера $1$ уже отсортирован, тогда мы можем делать это процедуру рекурсивно. Тогда для данного массива $a$ это будет выглядеть следующим образом:

Так сколько же работает это решение?

Пускай $T(n)$ — время сортировки массива длины $n$ , тогда для сортировки слиянием справедливо $T(n)=2T(n/2)+O(n)$ $O(n)$ — время, необходимое на то, чтобы слить два массива длины n. Распишем это соотношение:

Количество инверсий

Пусть у нас есть некоторая перестановка $a$ . Инверсией называется пара индексов $i$ и $j$ такая, что $i и \(a[i] > a[j]$ .

Найти количество инверсий в данной перестановке.

Очевидно, что эта задача легко решается обычным перебором двух индексов за $O(n^2)$ :

Внезапно эту задачу можно решить используя сортировку слиянием, слегка модифицируя её. Оставим ту же идею. Пусть мы умеем находить количество инверсий в массиве размера $n$ , научимся находить количество инверсий в массиве размера $2n$ .

Заметим, что мы уже знаем количество инверсий в левой половине и в правой половине массива. Осталось лишь посчитать число инверсий, где одно число лежит в левой половине, а второе в правой половине. Как же их посчитать?

Давайте подробнее рассмотрим операцию merge левой и правой половины (которую мы ранее заменили на вызов встроенной функции merge). Первый указатель указывает на элемент левой половины, второй указатель указывает на элемент второй половины, мы смотрим на минимум из них и этот указатель вдигаем вправо.

Рассмотрим число $A$ в левой половине. В скольки инверсиях между половинами оно участвует? В стольки, сколько чисел в правой половине меньше, чем оно. Знаем ли мы это количество? Да! Ровно в тот момент, когда мы число $A$ вносим в слитый массив, второй указатель указывает на первое число в правой половине, которое больше чем $A$ .

Значит в тот момент, когда мы добавляем число $A$ из левой половины, к ответу достаточно прибавить индекс второго указателя (минус начало правой половины). Так мы учтем все инверсии между половинами.

Быстрая сортировка

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

Давайте оценим асимптотику данной сортировки. На случайных данных она работает за $O(NlogN)$ , так как каждый раз мы будем делить массив на две примерно равные части, то есть суммарно размер рекурсии будет около логарифма и при этом на каждом этапе рекурсии мы просмотрим не более, чем размер массива. Однако можно легко найти две проблемы, одна — одинаковые числа, а вторая — если вдруг середина — минимум или максимум.

Существуют несколько выходов из этой ситуации :

Давайте если быстрая сортировка работает долго, то запустим любую другую сортировку за $NlogN$ .

Давайте делить массив не на две, а на три части(меньше, равны, больше).

Чтобы избавиться от проблемы с максимумом/минимумом в середине, давайте брать случайный элемент.

Поиск $k$ -ой порядковой статистики за $O(N)$

Пусть дан массив $A$ длиной $N$ и пусть дано число $K$ . Задача заключается в том, чтобы найти в этом массиве $K$ -ое по величине число, т.е. $K$ -ую порядковую статистику.

Давайте поймем, что в быстрой сортировке мы можем узнать, сколько элементов меньше данного, тогда рассмотрим три случая

количество чисел, меньше данного = $k — 1$ , тогда наше число — ответ.

количество чисел, меньше данного >= $k$ , тогда спускаемся рекурсивно в левую часть и ищем там ответ.

количество чисел, меньше данного $k$ , спускаемся в правую ищем ( $k$ — левая — 1) — ое число.

За сколько же это работает, из быстрой сортировки мы имеем, что размер убывает приблизительно в 2 раза, то есть мы имеем сумму $\sum_^n <2 ^ k>= <2^-1>$ что в нашем случае это максимум равно $2 * N — 1$ , то есть $O(N)$ .

Также в C++ эта функция уже реализована и называется nth_element .

Источник

Способ сортировки массива это

Сортировки

Содержание

Классификация сортировок [ править ]

Время работы [ править ]

Память [ править ]

Устойчивость [ править ]

Количество обменов [ править ]

Детерминированность [ править ]

Сравнение сортировок [ править ]