🗊Презентация Основы программирования. Эффективные алгоритмы сортировки

Основы программирования Эффективные алгоритмы сортировки

Задача сортировки элементов массива Дан массив значений . Необходимо найти такую перестановку индексов , что для последовательности выполняется . - это некоторая перестановка чисел , поэтому общее количество потенциальных решений задачи равно числу перестановок из элементов, т.е. Минимальная гарантированная трудоемкость в наихудшем для сортировки, основанной на сравнениях: Алгоритмы с такой трудоемкостью мы будем считать эффективными.

Рекуррентное слияние (снизу вверх) Пусть – текущая длина серий в массиве (в исходном массиве серий и ). Проход в сортировке слиянием: массив A содержит текущих серий длины пары смежных серий сливаются в серий длины в рабочий массив D новые серии копируются из D в A. Проходы повторяются при , пока (т.е. ). Общее число проходов составляет . На каждом проходе в слиянии участвуют все элементов, поэтому

Рекуррентное слияние (снизу вверх) В общем случае , поэтому на любом проходе возможны варианты: число текущих серий нечетно последняя серия имеет длину Поэтому при слиянии серий необходимо учесть, что 2-я серия может быть короче 1-й или вообще пустой. В приведенном ниже алгоритме вычисляются индексы b,c и e, которые задают границы сливаемых серий: A[b…c] и A[c+1…e].

Рекуррентный алгоритм слияния void merge_sort(double *A, int n) { int s, b, c, e; double *D = new double[n]; for (s = 1; s < n; s *= 2) { for (b = 0; b < n; b += s*2) { c = min(b+s-1, n-1); e = min(c+s, n-1); merge_series(A, b, c, e, D); } for (b = 0; b < n; b++) A[b] = D[b]; } delete [] D; }

Сортировка Шелла Основана на сортировке вставками (или обменной): элемент добавляется к уже отсортированной последовательности элементов . Для этого сравнивается и меняется с , пока . Общее число сравнений для всех : Чем меньше в массиве инверсий, тем быстрее он сортируется.

Сортировка Шелла: h-цепочки Зафиксируем и рассмотрим -цепочки – последовательности элементов с индексами: … Всего будет цепочек длиной .

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

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

Сортировка Шелла: выбор шага h Д. Кнут показал: Выбор шага - неудачный, т.к. при этом Цепочки хорошо перемешиваются при выборе взаимно простых . Хорошие последовательности для значений : . При выборе таких последовательностей:

Сортировка Шелла: алгоритм Используется последовательность , начальное значение вычисляется таким образом, чтобы начальные цепочки содержали элементов. void shell_sort(double *A, int n) { int i, j, h; for (h = 1; h <= n / 9; h = h * 3 + 1); while (h >= 1) { for (i = h; i < n; i++) for (j=i-h; j>=0&& A[j]>A[j+h]; j-=h) swap(A[j], A[j+h]); h = (h - 1) / 3; } }

Пирамидальная сортировка В алгоритме строится пирамида (бинарная куча), которую можно представить в виде бинарного дерева: каждой вершине соответствует элемент массива каждая вершина имеет 2 вершин-сыновей заполнены все уровни, кроме, возможно, последнего значение-отец всегда не меньше значений-сыновей.  Просеивание в пирамиде (если нарушено условие): 9 <= 2 8 8 / \ / \ / \ 8 6 2 6 5 6 / \ / \ => / \ / \ => / \ / \ 5 3 1 4 5 3 1 4 2 3 1 4 / \ / \ / / \ / \ / / \ / \ / 0 2 3 1 0 0 2 3 1 0 0 2 3 1 0

Свойства пирамиды (бинарной кучи) В корне пирамиды располагается максимальный элемент. Если пирамида имеет уровней и все уровни заполнены, то общее число вершин . Если , то -й уровень заполнен не до конца. Пирамида с вершинами имеет уровней, поэтому максимальное число сравнений при просеивании . Пирамиду можно построить непосредственно на массиве: для любого элемента-отца сыновьями будут и условие пирамиды:

Идея сортировки Пусть на массиве длины построена пирамида и номер ее последнего элемента . Если поменять местами элементы с индексами 0 и , то максимальный элемент встанет на свое (последнее) место в упорядоченном массиве. Для 0-го элемента условие пирамиды будет нарушено. Чтобы восстановить пирамиду, этот элемент нужно просеять, не изменяя положение максимального элемента , т.е. в пирамиде длины . Далее необходимо повторить эти действия для всех значений , убывающих от до 1. Трудоемкость сортировки:

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

Трудоемкость построения пирамиды Пусть пирамида имеет уровней, и все они заполнены. Тогда: на уровне находятся вершин, которые не надо просеивать на уровне находятся вершин, которые при просеивании могут сместиться только на 1 уровень на уровне находятся вершин, которые при просеивании могут сместиться только на 2 уровня и т.д. вплоть до 1-го уровня с 1 вершиной.

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

Функция просеивания в пирамиде Параметры и переменные функции sift: i – начальный номер просеиваемого элемента, m – номер конечного элемента в текущей пирамиде, j – текущий номер просеиваемого элемента, k – номер левого или большего сына j. void sift(double *A, int i, int m) { int j = i, k = i*2+1; // левый сын while (k <= m) { if (k<m && A[k]<A[k+1]) k++; // больший сын if (A[j] < A[k]) { swap(A[j], A[k]); j = k; k = k*2+1; } else break; } }

Алгоритм пирамидальной сортировки void heap_sort(double *A, int n) { int i, m; // построение пирамиды for (i = n/2; i >= 0; i--) sift(A, i, n-1); // сортировка массива for (m = n-1; m >= 1; m--) { swap(A[0], A[m]); sift(A, 0, m-1); } }

Быстрая сортировка (Хоар) В быстрой сортировке проводится рекурсивная обработка массива и его отдельных частей. При каждом рекурсивном вызове задаются границы текущей части. Обозначим индексы ее начального и конечного элементов и (при первом вызове ). Основной шаг сортировки – разделение текущей части массива опорным элементом: выбирается некоторый элемент и текущая часть приводится к виду

Быстрая сортировка После разделения элемент окажется на своем месте в упорядоченном массиве, а части и можно сортировать рекурсивно и независимо. Разделение массива длины необходимо проводить за элементарных шагов, при этом: наилучшее разделение – 2 подмассива длины и наихудшее – 1 подмассив длины (второй будет пустым) и

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

Трудоемкость в среднем: доказательство Положим и . Покажем, что . Доказательство (мат. индукция): Базис Пусть выполняется , тогда

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

Трудоемкость в среднем: доказательство Таким образом:

Разделение массива: 1-й способ Текущая разделяемая часть массива: . – текущий индекс опорного элемента (начальные значения ). – самый правый непроверенный элемент (начальное значение ). k = b; j = e; x = A[b]; while (k < j) if (A[j] >= x) j--; else { A[k]=A[j]; A[j]=A[k+1]; A[k+1]=x; k++; }

Разделение массива: 2-й способ Опорный элемент можно выбрать на любой позиции разделяемой части, его индекс не важен. и – левая и правая границы непроверенной части (начальные значения ). Пока : Пропускаются все с увеличением на 1 Пропускаются все с уменьшением j на 1 Если , то и меняются местами, увеличивается, уменьшается на 1.

Быстрая сортировка с 2 рекурсивными вызовами void quick_sort_2(double *A, int b, int e) { double x; int i, j; x = A[(b+e)/2]; i = b; j = e; while (i < j) { while (A[i] < x) i++; while (A[j] > x) j--; if (i <= j) { { swap(A[i], A[j]); i++; j--; } } if (b < j) quick_sort_2(A, b, j); if (i < e) quick_sort_2(A, i, e); }

Быстрая сортировка с 1 рекурсивным вызовом В наихудшем случае опорный элемент после разделения текущей части всегда оказывается либо в позиции , либо в позиции , т.е. нужно рекурсивно сортировать либо , либо . В этом случае не только , но и глубина рекурсии составит . При каждом рекурсивном вызове в стеке выделяется память для параметров и внутренних переменных функции, и в наихудшем случае потребуется памяти в 5-6 раз больше, чем занимает исходный массив. Для уменьшения глубины рекурсии нужно избавиться от рекурсивной обработки большей из 2 частей, полученных в результате разделения.

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

Быстрая сортировка с 1 рекурсивным вызовом void quick_sort(double *A, int b, int e) { double x; int i, j, c = b, d = e; while (c < d) { x = A[(c+d)/2]; i = c; j = d; while (i < j) { while (A[i] < x) i++; while (A[j] > x) j--; if (i <= j) { swap(A[i], A[j]); i++; j--; } } if (j-c < d-i) { if (c < j) quick_sort(A,c,j); c = i; } else { if (i<d) quick_sort(A,i,d); d = j; } } }

Свойства алгоритмов сортировки Сравнение алгоритмов сортировки по : быстрая < слияние < пирамидальная Выбор при различных : десятки – простые алгоритмы, сотни или несколько тысяч – алгоритм Шелла Сортировка называется устойчивой, если она сохраняет порядок следования равных элементов: пусть в исходном массиве существуют , и после сортировки займет позицию , – . Если при этом , то сортировка устойчива.

Поиск k-го минимального элемента Задача: в массиве найти -й по значению элемент (т.е. элемент, который стоял бы на позиции , если бы массив был упорядочен по возрастанию). Варианты решения: Для используются элементарные алгоритмы. Если число запросов на поиск , то массив лучше отсортировать (прямо или косвенно). Если или , то можно построить бинарную кучу и провести шагов, как в пирамидальной сортировке.

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

Алгоритм поиска k-го минимального элемента double med(double *A, int n, int k) { int b = 0, e = n-1; double x; while (b < e) { j = b; i = e; x = A[b]; while (j < i) if (A[i] >= x) i--; else { A[j++] = A[i]; A[i] = A[j]; A[j] = x; } if (k < j) e = j-1; else if (k > j) b = j+1; else { b = j; break; } } return A[b]; }

Цифровая сортировка Пусть для целочисленного массива выполняется: , где и – целые и . Тогда для сортировки массива достаточно сформировать счетчик (целочисленный массив count[0…e-b]), подсчитать частоты всех значений и записать в все группы одинаковых значений по возрастанию. При этом , счетчик count[i] будет задавать общее число значений, равных (или наоборот, значение некоторого элемента A[j] соответствует счетчику count[A[j]-b]).

Простейший алгоритм цифровой сортировки void rad_sort(int *A, int n, int b, int e) { int i, j, k, *count; count = new int[e-b+1]; for (i = 0; i <= e-b; i++) count[i] = 0; for (i = 0; i < n; i++) count[A[i]-b]++; for (k = i = 0; i <= e-b; i++) for (j = 0; j < count[i]; j++) A[k++] = b + i; delete [] count; } Трудоемкость данного алгоритма .

Косвенная цифровая сортировка Пусть при тех же условиях массив A нужно упорядочить косвенно, т.е. сформировать массив индексов в порядке возрастания элементов A. В этом случае нам понадобятся 3 целочисленных массива: формируемый массив индексов Ind[0…n-1], массив счетчиков count[0…e-b], массив pos[0…e-b] текущих позиций в Ind индексов элементов массива A (индекс i очередного выбираемого элемента A[i] будет записан в Ind на позиции pos[A[i]-b]).

Алгоритм косвенной цифровой сортировки int* ind_rad_sort(int *A, int n, int b, int e) { int i, *count, *pos, *Ind; count = new int[e-b+1]; pos = new int[e-b+1]; Ind = new int[n]; for (i = 0; i <= e-b; i++) count[i] = 0; for (i = 0; i < n; i++) count[A[i]-b]++; for (pos[0] = 0, i = 1; i <= e-b; i++) pos[i] = pos[i-1] + count[i-1]; for (i = 0; i < n; i++) Ind[pos[A[i]-b]++] = i; delete [] count; delete [] pos; return Ind; } Трудоемкость данного алгоритма .

Косвенная цифровая сортировка со списками Если использовать списки целых (класс List из раздела «Линейные списки»), то можно записать более элегантный алгоритм косвенной сортировки массива A. В этом случае нам понадобятся: формируемый список индексов LRes – очередь индексов в порядке возрастания значений A, массив списков LMas[0…e-b] (индекс i очередного выбираемого элемента A[i] будет добавлен в конец списка LMas[A[i]-b]). Выходной список (очередь) LRes формируется с помощью последовательного объединения списков LMas.

Косвенная цифровая сортировка со списками List lrad_sort(int *A,int n, int b, int e) { int i; List LRes, *LMas; LMas = new List[e-b+1]; for (i = 0; i < n; i++) LMas[A[i]-b].push_back(i); for (i = 0; i <= e-b; i++) LRes.join(LMas[i]); delete [] LMas; return LRes; } Трудоемкость данного алгоритма .

Цифровая сортировка целых чисел Целые 4-байтовые числа можно делить на отдельные байты и сортировать по байтам (косвенно), начиная с младших (). При сортировке по байту необходимо: выбирать числа в порядке очереди, полученной в результате сортировки по предыдущему байту (начальная очередь при содержит последовательность индексов от 0 до ) разносить индексы по 256 спискам в соответствии со значением -го байта чисел сцепить полученные списки в единую очередь (она будет определять порядок выбора чисел при сортировке по байту или окончательный порядок при ).

Цифровая сортировка целых чисел Отметим, что положительные и отрицательные целые числа имеют разную внутреннюю кодировку, поэтому их нужно сортировать раздельно. Мы рассмотрим только неотрицательные числа. Цифровая сортировка является устойчивой, поэтому если по байту , то упорядоченность по байту не нарушится. Для получения значения -го байта числа необходимо сдвинуть битовое представление числа на бит вправо и поделить по модулю 256. Результат будет в младшем байте, остальные байты – нули.

Цифровая сортировка неотрицательных целых List radix_sort(unsigned *A, int n) { int i, k, j, m; List LRes, *LMas = new List[256]; for (i = 0; i < n; i++) LRes.push_back(i); for (k = 0; k < 4; k++) { for (i = 0; i < n; i++) { j = LRes.pop_front(); m=(A[j]>>(k*8))%256; LMas[m].push_back(j); } for (i = 0; i < 256; i++) LRes.join(LMas[i]); } delete [] LMas; return LRes; } Трудоемкость данного алгоритма .