Анализ
Пример пузырьковой сортировки. Начиная с начала списка, сравните каждую соседнюю пару, поменяйте их местами, если они не в правильном порядке (последняя меньше первой). После каждой итерации необходимо сравнивать на один элемент меньше (последний), пока не останется больше элементов для сравнения.
Представление
Пузырьковая сортировка имеет наихудший случай и среднюю сложность О ( n 2 ), где n — количество сортируемых элементов. Большинство практических алгоритмов сортировки имеют существенно лучшую сложность в худшем случае или в среднем, часто O ( n log n ). Даже другое О ( п 2 ) алгоритмы сортировки, такие как вставки рода , как правило , не работать быстрее , чем пузырьковой сортировки, а не более сложным. Следовательно, пузырьковая сортировка не является практическим алгоритмом сортировки.
Единственное существенное преимущество пузырьковой сортировки перед большинством других алгоритмов, даже быстрой сортировкой , но не сортировкой вставкой , заключается в том, что в алгоритм встроена способность определять, что список сортируется эффективно. Когда список уже отсортирован (в лучшем случае), сложность пузырьковой сортировки составляет всего O ( n ). Напротив, большинство других алгоритмов, даже с лучшей средней сложностью , выполняют весь процесс сортировки на множестве и, следовательно, являются более сложными. Однако сортировка вставкой не только разделяет это преимущество, но также лучше работает со списком, который существенно отсортирован (имеет небольшое количество инверсий ). Кроме того, если такое поведение желательно, его можно тривиально добавить к любому другому алгоритму, проверив список перед запуском алгоритма.
Кролики и черепахи
Расстояние и направление, в котором элементы должны перемещаться во время сортировки, определяют производительность пузырьковой сортировки, поскольку элементы перемещаются в разных направлениях с разной скоростью. Элемент, который должен двигаться к концу списка, может перемещаться быстро, потому что он может принимать участие в последовательных заменах. Например, самый большой элемент в списке будет выигрывать при каждом обмене, поэтому он перемещается в свою отсортированную позицию на первом проходе, даже если он начинается рядом с началом. С другой стороны, элемент, который должен двигаться к началу списка, не может двигаться быстрее, чем один шаг за проход, поэтому элементы перемещаются к началу очень медленно. Если наименьший элемент находится в конце списка, потребуется n −1 проход, чтобы переместить его в начало. Это привело к тому, что эти типы элементов были названы кроликами и черепахами соответственно в честь персонажей басни Эзопа о Черепахе и Зайце .
Были предприняты различные попытки уничтожить черепах, чтобы повысить скорость сортировки пузырей. Сортировка коктейлей — это двунаправленная сортировка пузырьков, которая идет от начала до конца, а затем меняет свое направление, идя от конца к началу. Он может довольно хорошо перемещать черепах, но сохраняет сложность наихудшего случая O (n 2 ) . Сортировка гребенкой сравнивает элементы, разделенные большими промежутками, и может очень быстро перемещать черепах, прежде чем переходить к все меньшим и меньшим промежуткам, чтобы сгладить список. Его средняя скорость сопоставима с более быстрыми алгоритмами вроде быстрой сортировки .
Пошаговый пример
Возьмите массив чисел «5 1 4 2 8» и отсортируйте его от наименьшего числа к наибольшему числу, используя пузырьковую сортировку. На каждом этапе сравниваются элементы, выделенные жирным шрифтом . Потребуется три прохода;
- Первый проход
- ( 5 1 4 2
→ ( 1 5 4 2 8). Здесь алгоритм сравнивает первые два элемента и меняет местами, поскольку 5> 1. - (1 5 4 2 → (1 4 5 2 8), поменять местами, поскольку 5> 4
- (1 4 5 2 → (1 4 2 5 8), поменять местами, поскольку 5> 2
- (1 4 2 5 8 ) → (1 4 2 5 8 ). Теперь, поскольку эти элементы уже упорядочены (8> 5), алгоритм не меняет их местами.
- Второй проход
- ( 1 4 2 5 → ( 1 4 2 5
- (1 4 2 5 → (1 2 4 5 8), поменять местами, поскольку 4> 2
- (1 2 4 5 → (1 2 4 5
- (1 2 4 5 8 ) → (1 2 4 5 8 )
→ ( 1 5 4 2 8). Здесь алгоритм сравнивает первые два элемента и меняет местами, поскольку 5> 1.Теперь массив уже отсортирован, но алгоритм не знает, завершился ли он. Алгоритму требуется один дополнительный полный проход без какой-либо подкачки, чтобы знать, что он отсортирован.
- Третий проход
- ( 1 2 4 5 → ( 1 2 4 5
- (1 2 4 5 → (1 2 4 5
- (1 2 4 5 → (1 2 4 5
- (1 2 4 5 8 ) → (1 2 4 5 8 )
Сортировка слиянием (Merge sort)
При рекурсивной сортировке слиянием массив сначала разбивается на мелкие кусочки — на
первом этапе — на состоящие из одного элемента. Затем эти кусочки объединяются в более
крупные кусочки — по два элемента и элементы при этом сравниваются, а в результате в
новом кусочке меньший элемент занимает место слева, а больший — справа. Далее происходит
слияние в ещё более крупные кусочки и так до конца алгоритма, когда все кусочки будут
объединены в один, уже отсортированный массив. Если есть интерес, есть статья о рекурсивных функциях.
Код C++
void SortAlgo::mergeSort(int data[], int lenD)
{
if(lenD>1){
int middle = lenD/2;
int rem = lenD-middle;
int* L = new int;
int* R = new int;
for(int i=0;i<lenD;i++){
if(i<middle){
L = data;
}
else{
R = data;
}
}
mergeSort(L,middle);
mergeSort(R,rem);
merge(data, lenD, L, middle, R, rem);
}
}
void SortAlgo::merge(int merged[], int lenD, int L[], int lenL, int R[], int lenR){
int i = 0;
int j = 0;
while(i<lenL||j<lenR){
if (i<lenL & j<lenR){
if(L<=R){
merged = L;
i++;
}
else{
merged = R;
j++;
}
}
else if(i<lenL){
merged = L;
i++;
}
else if(j<lenR){
merged = R;
j++;
}
}
}
Пузырьковая Cортировка
3.1. Первое объяснение.
Объяснение на примере пузырьковой сортировки от меньшего к большему:
Берём последний элемент и стравнивываем его с предпоследним, если последний меньше больше предыдущего, то меняем их местами.
Применяем данное правило к новому предпослениму элементу и элементу, расположенному перед предпосленим. Повторяем это правило до первого элемента.
Снова повторяем это правило, считая, что первый элемент трогать не надо, т.к. на его место правило протолкнуло наименьший элемент. Теперь в результате этого правила протолкулся на второе место наименьший элемент в оставшейся части.
Повторяем это правило проталкивания обменом к оставшейся части массива, исключив первый и второй. И так далее, пока не осортируется массив.
Посмотрим на это правило (пузырьковую сортировку) на Анимации 1. Пузырьковая сортировка на обратно отсортированном массиве:
Анимация 1. Пузырьковая сортировка на обратно отсортированном массиве (применённая к обратному случаю (обратным входным данным)).
3.2. Второе объяснение.
- 1. Введите временную переменную temp для запоминания текущего значения элемента массива.
- 2. Введём цикл для перемещения пузырьков, равный по повторениям (Размер массива arr).:
- 2.1. Просмотрим в цикле все элементы массива, просматриваются два элемента, поэтому повторений будет (Размер массива — 1). Элементы просматриваются с конца.
- 2.1.1. Вычислим индекс предыдущего элемента за анализируемым.
- 2.1.2. Если текущий элемент больше предыдущего за ним, то меняем их местами.
- 2.1. Просмотрим в цикле все элементы массива, просматриваются два элемента, поэтому повторений будет (Размер массива — 1). Элементы просматриваются с конца.
- Конец.
Далее рассмотрим блок-схему алгоритма, т.к. в алгоритме не учтено присвоение счётчиков цикла:
Входные данные: arr — входной сортируемый массив.
Рис. 3. Блок-схема алгоритма сортировки пузырьком от меньшего к большему.
3.3. Третье объяснение.
private static void sortArrBuble(ArrayList<Integer> arr) {
// 1. Введите временную переменную temp для запоминания текущего значения элемента массива.
Integer temp;
// 2. Введём цикл для перемещения пузырьков, равный по повторениям (Размер массива arr).
for(int i = 0; i < arr.size() — 1; i++)
{
// 2.1. Просмотрим в цикле все элементы массива, просматриваются два элемента, поэтому повторений будет (Размер массива — 1). Элементы просматриваются с конца.
for(int j = arr.size() — 1; j > i; j—)
{
// 2.1.1. Вычислим индекс предыдущего элемента за анализируемым.
int decJ = j — 1;
// 2.1.2. Если текущий элемент больше предыдущего за ним, то меняем их местами.
if(arr.get(j).intValue() < arr.get(decJ).intValue()) {
// Меняем их местами.
temp = arr.get(j);
arr.set(j, arr.get(decJ));
arr.set(decJ, temp);
}
}
}
}
Как работает серверный вызов в 1С Промо
Клиент-серверная архитектура заложена в платформе изначально — со времен «1С:Предприятие 8.0». Однако при разработке на 8.0 и 8.1 о разделении кода на клиентскую и серверную часть можно было не заботиться, поскольку на клиенте (на толстом клиенте) был доступен тот же функционал, что и на сервере. Всё изменилось с выходом платформы «1С:Предприятие 8.2», когда появился тонкий клиент. Теперь на клиенте доступен один функционал, на сервере — другой. Клиент и сервер «общаются» между собой с помощью серверного вызова. Конечно, это усложнило процесс разработки, но с другой стороны – можно создавать более оптимальные (быстрые) решения, поскольку все сложные задачи выполняются на сервере.
Сложность сортировки пузырьком
В алгоритме сортировки пузырьком фигурируют две различных
нетривиальных операции: условное ветвление по результатам сравнения и
обмен двух элементов массива местами.
Будем считать, что каждая из этих операций занимает единицу времени,
а всё остальное (например, обслуживание счётчиков циклов) бесплатно.
Тогда для массива длины \(N\) алгоритм занимает
\
единиц времени. Заметим, что, начиная с \(N=4\), выполнено
неравенство
\
Также всегда выполнено неравенство
\
То есть, начиная с некоторого \(N\), время работы алгоритма
заключено между значениями выражений, пропорциональных \(N^2\).
В такой ситуации говорят, что \(N^2\) является
асимптотической сложностью рассматриваемого алгоритма.
В общем случае, если \( T(N) \) — (максимально возможное)
время работы алгоритма на наборе данных размера \( N \),
а \(f\) — некоторая функция натурального аргумента, то говорят, что:
- алгоритм обладает верхней асимптотической сложностью \( f(N) \), если
существует такое положительное число \( \alpha \), что, начиная с некоторого
\(N\), выполнено неравенство \( T(N) \leqslant \alpha f(N) \) - алгоритм обладает нижней асимптотической сложностью \( f(N) \), если
существует такое положительное число \( \alpha \), что, начиная с некоторого
\(N\), выполнено неравенство \( T(N) \geqslant \alpha f(N) \) - алгоритм обладает асимптотической сложностью \( f(N) \), если
он обладает нижней и верхней асимптотическими сложностями \( f(N) \)
Например, про сортировку пузырьком можно сказать, что:
- она обладает верхней асимптотической сложностью \( N^2 \)
- она обладает верхней асимптотической сложностью \( 1000N^2 \)
- она обладает верхней асимптотической сложностью \( N^{1000} \)
- она обладает нижней асимптотической сложностью \( N^2 \)
- она обладает нижней асимптотической сложностью \( 1000N^2 \)
- она обладает нижней асимптотической сложностью \( N \)
- она обладает асимптотической сложностью \( N^2 \)
Часто можно встретить обозначение \(O( f(N) )\) для множества
алгоритмов, обладающих асимптотической сложностью \( f(N) \).
Иногда буква \(O\) относится только к верхней асимптотической сложности:
в таких ситуациях для нижней асимптотической сложности используется
буква \( \Omega \) (омега большая), а для (просто) асимптотической
сложности — буква \( \Theta \) (тета большая).
Реализация алгоритма «Сортировка пузырьком» на T-SQL
На а теперь давайте перейдём к реализации алгоритма «Сортировка пузырьком» на языке T-SQL в Microsoft SQL Server.
В качестве исходных данных у меня будет выступать массив чисел, который представлен на картинке чуть выше, т.е. алгоритм ниже выполняет те же самые действия, что и на GIF изображении.
Для удобства данный алгоритм я оформил в виде хранимой процедуры bubble_sort.
Весь код я подробно прокомментировал.
CREATE PROCEDURE bubble_sort AS BEGIN --Табличная переменная для хранения массива данных с числами --Индекс массива начинается с 0 DECLARE @data_array TABLE (array_index INT NOT NULL IDENTITY(0, 1) PRIMARY KEY, value INT NOT NULL); --Добавление данных в табличную переменную INSERT INTO @data_array VALUES (5),(2),(1),(3),(9),(0),(4),(6),(8),(7); --Вывод данных до сортировки SELECT array_index, value FROM @data_array; DECLARE @current_element INT, --Текущий элемент в массиве @amount_elements INT, --Количество элементов в массиве @continue_sort BIT; --Признак для продолжения сортировки --Переменные для хранения значений массива DECLARE @value1 INT, @value2 INT; --Определяем количество элементов в массиве, учитывая, что он начинается с 0 SELECT @amount_elements = COUNT(*) - 1 FROM @data_array; SET @continue_sort = 1; /* @continue_sort = 1 - продолжать сортировку, массив не отсортирован @continue_sort = 0 - сортировка завершена, массив отсортирован */ --Запуск цикла для прохода по массиву WHILE @continue_sort = 1 BEGIN --Сразу отмечаем, что сортировку нужно завершить, в случае если не будет обмена значениями SET @continue_sort = 0; --Проход по массиву начинаем с первого элемента SET @current_element = 0; --Запуск цикла для сравнения значений массива в текущем проходе WHILE @current_element < @amount_elements BEGIN SELECT @value1 = 0, @value2 = 0; --Получаем первые значения в массиве SELECT @value1 = value FROM @data_array WHERE array_index = @current_element; SELECT @value2 = value FROM @data_array WHERE array_index = @current_element + 1; --Сравнение значений --Если первое значение больше второго, то необходимо поменять их местами IF @value1 > @value2 BEGIN UPDATE @data_array SET value = @value2 WHERE array_index = @current_element; UPDATE @data_array SET value = @value1 WHERE array_index = @current_element + 1; --Произошел обмен значениями, значит сортировку следует продолжать SET @continue_sort = 1; END --Двигаемся дальше по массиву SET @current_element = @current_element + 1; END /* После прохода по массиву в его конце оказываются отсортированные элементы Исключаем их, для уменьшения количества интераций (сравнений) */ SET @amount_elements = @amount_elements - 1; END --Вывод данных после сортировки SELECT array_index, value FROM @data_array; END GO
Чтобы проверить работу алгоритма, вызываем процедуру bubble_sort.
EXEC bubble_sort;
Как видим, данные отсортированы.
На сегодня это все, надеюсь, материал был Вам интересен, пока!
Нравится4Не нравится
Примеры блок-схем
В качестве примеров, построены блок-схемы очень простых алгоритмов сортировки, при этом акцент сделан на различные реализации циклов, т.к. у студенты делают наибольшее число ошибок именно в этой части.
Сортировка вставками
Массив в алгоритме сортировки вставками разделяется на отсортированную и еще не обработанную части. Изначально отсортированная часть состоит из одного элемента, и постепенно увеличивается.
На каждом шаге алгоритма выбирается первый элемент необработанной части массива и вставляется в отсортированную так, чтобы в ней сохранялся требуемый порядок следования элементов. Вставка может выполняться как в конец массива, так и в середину. При вставке в середину необходимо сдвинуть все элементы, расположенные «правее» позиции вставки на один элемент вправо. В алгоритме используется два цикла — в первом выбираются элементы необработанной части, а во втором осуществляется вставка.
Блок-схема алгоритма сортировки вставками
В приведенной блок-схеме для организации цикла используется символ ветвления. В главном цикле (i < n) перебираются элементы необработанной части массива. Если все элементы обработаны — алгоритм завершает работу, в противном случае выполняется поиск позиции для вставки i-того элемента. Искомая позиция будет сохранена в переменной j в результате выполнения внутреннего цикла, осуществляющем сдвиг элементов до тех пор, пока не будет найден элемент, значение которого меньше i-того.
На блок-схеме показано каким образом может использоваться символ перехода — его можно использовать не только для соединения частей схем, размещенных на разных листах, но и для сокращения количества линий. В ряде случаев это позволяет избежать пересечения линий и упрощает восприятие алгоритма.
Сортировка пузырьком
Сортировка пузырьком, как и сортировка вставками, использует два цикла. Во вложенном цикле выполняется попарное сравнение элементов и, в случае нарушения порядка их следования, перестановка. В результате выполнения одной итерации внутреннего цикла, максимальный элемент гарантированно будет смещен в конец массива. Внешний цикл выполняется до тех пор, пока весь массив не будет отсортирован.
Блок-схема алгоритма сортировки пузырьком
На блок-схеме показано использование символов начала и конца цикла. Условие внешнего цикла (А) проверяется в конце (с постусловием), он работает до тех пор, пока переменная hasSwapped имеет значение true. Внутренний цикл использует предусловие для перебора пар сравниваемых элементов. В случае, если элементы расположены в неправильном порядке, выполняется их перестановка посредством вызова внешней процедуры (swap). Для того, чтобы было понятно назначение внешней процедуры и порядок следования ее аргументов, необходимо писать комментарии. В случае, если функция возвращает значение, комментарий может быть написан к символу терминатору конца.
Сортировка выбором
В сортировке выбором массив разделяется на отсортированную и необработанную части. Изначально отсортированная часть пустая, но постепенно она увеличивается. Алгоритм производит поиск минимального элемента необработанной части и меняет его местами с первым элементом той же части, после чего считается, что первый элемент обработан (отсортированная часть увеличивается).
Блок-схема сортировки выбором
На блок-схеме приведен пример использования блока «подготовка», а также показано, что в ряде случаев можно описывать алгоритм более «укрупнённо» (не вдаваясь в детали). К сортировке выбором не имеют отношения детали реализации поиска индекса минимального элемента массива, поэтому они могут быть описаны символом вызова внешней процедуры. Если блок-схема алгоритма внешней процедуры отсутствует, не помешает написать к символу вызова комментарий, исключением могут быть функции с говорящими названиями типа swap, sort, … .
На блоге можно найти другие примеры блок-схем:
- блок-схема проверки правильности расстановки скобок арифметического выражения ;
- блок-схемы алгоритмов быстрой сортировки и сортировки слиянием .
Часть студентов традиционно пытается рисовать блок-схемы в Microsoft Word, но это оказывается сложно и не удобно. Например, в MS Word нет стандартного блока для терминатора начала и конца алгоритма (прямоугольник со скругленными краями, а не овал). Наиболее удобными, на мой взгляд, являются утилиты MS Visio и yEd , обе они позволяют гораздо больше, чем строить блок-схемы (например рисовать диаграммы UML), но первая является платной и работает только под Windows, вторая бесплатная и кроссплатфомренная. Все блок-схемы в этой статье выполнены с использованием yEd.
Выполнение
Реализация псевдокода
В псевдокод алгоритм может быть выражен как (массив на основе 0):
процедура bubbleSort(А список из сортируемый Предметы) п := длина(А) повторение поменяны местами := ложный за я := 1 к п-1 включающий делать /* если это пара является из из порядок */ если Ая-1 > Ая тогда /* замена их и Помните что нибудь измененный */ замена(Ая-1, Ая]) поменяны местами := истинный конец если конец за до того как нет поменяны местамиконец процедура
Оптимизация пузырьковой сортировки
Алгоритм пузырьковой сортировки можно оптимизировать, заметив, что п-й проход находит п-й по величине элемент и ставит его на последнее место. Таким образом, внутренний цикл может не смотреть на последний п — 1 шт. При беге за п-й раз:
процедура bubbleSort(А список из сортируемый Предметы) п := длина(А) повторение поменяны местами := ложный за я := 1 к п - 1 включающий делать если Ая - 1 > Ая тогда замена(Ая - 1, Ая]) поменяны местами = истинный конец если конец за п := п - 1 до того как нет поменяны местамиконец процедура
В более общем смысле может случиться так, что более чем один элемент помещается в свое окончательное положение за один проход. В частности, после каждого прохода все элементы после последнего свопа сортируются и не нуждаются в повторной проверке. Это позволяет пропускать многие элементы, что в худшем случае приводит к увеличению количества сравнений примерно на 50% (хотя и без улучшения подсчета подкачки), и добавляет очень небольшую сложность, поскольку новый код включает переменную «подкачки»:
Для этого в псевдокоде можно записать следующее:
процедура bubbleSort(А список из сортируемый Предметы) п := длина(А) повторение новинка := за я := 1 к п - 1 включающий делать если Ая - 1 > Ая тогда замена(Ая - 1, Ая]) newn := я конец если конец за п := newn до того как п ≥ 1конец процедура
Альтернативные модификации, такие как коктейльный шейкер сортировка попытаться улучшить производительность пузырьковой сортировки, сохраняя при этом идею многократного сравнения и замены соседних элементов.
Сортировка вставками (Insertion sort)
При сортировке вставками массив разбивается на две области: упорядоченную и
и неупорядоченную. Изначально весь массив является неупорядоченной областью.
При первом проходе первый элемент из неупорядоченной области изымается и помещается
в правильном положении в упорядоченной области.
На каждом проходе размер упорядоченной области возрастает на 1, а размер неупорядоченной
области сокращается на 1.
Основной цикл работает в интервале от 1 до N-1. На j-й итерации элемент вставлен в
правильное положение в упорядоченной области. Это сделано путем сдвига всех
элементов упорядоченной области, которые больше, чем , на одну позицию вправо.
вставляется в интервал между теми элементами, которые меньше , и теми, которые больше .
Код C++
void SortAlgo::insertionSort(int data[], int lenD)
{
int key = 0;
int i = 0;
for(int j = 1;j<lenD;j++){
key = data;
i = j-1;
while(i>=0 && data>key){
data = data;
i = i-1;
data=key;
}
}
}
Пузырьковая сортировка Python 3
# Оптимизированная реализация Python3
# сортировки пузырьком
# Оптимизированная версия пузырьковой сортировки
def bubbleSort(arr):
n = len(arr)
# Проход через все элементы массива
for i in range(n):
swapped = False
# Последние i элементы уже
# на месте
for j in range(0, n-i-1):
# проход через массив от 0
# n-i-1. Поменять местами элементы, если
# найденный элемент больше
# следующего
if arr > arr :
arr, arr = arr, arr
swapped = True
# Если в процессе прохода не было ни одной замены,
# то выход из функции
if swapped == False:
break
# тестирующий код
arr =
bubbleSort(arr)
print ("Сортированный массив :")
for i in range(len(arr)):
print ("%d" %arr,end=" ")
Метод пузырька C — результат сортировки:
Сортированный массив: 11 12 22 25 34 64 90
Худшая и средняя сложность времени: O (n * n). Наихудший случай возникает, когда массив отсортирован по обратному адресу.
Сложность наилучшего случая: O (n). Наилучший случай возникает, когда массив уже отсортирован.
Пограничные случаи: сортировка занимает минимальное время (порядок n), когда элементы уже отсортированы.
Сортировка на месте: Да.
Стабильность: Да.
В компьютерной графике пузырьковая сортировка популярна благодаря возможности обнаруживать мелкие ошибки (например, обмен всего двух элементов) в почти отсортированных массивах и исправлять ее только с линейной сложностью (2n). Например, она используется в алгоритме заполнения полигонов, где ограничивающие линии сортируются по их координате x на определенной линии сканирования (линия, параллельная оси X), и с увеличением Y их порядок меняется (два элемента меняются местами) только на пересечениях двух линий.
Пожалуйста, оставьте свои комментарии, если захотите поделиться дополнительной информацией про алгоритм сортировки пузырьком.
Пожалуйста, оставьте свои комментарии по текущей теме статьи. За комментарии, лайки, дизлайки, отклики, подписки огромное вам спасибо!
Пожалуйста, опубликуйте ваши мнения по текущей теме статьи. За комментарии, лайки, подписки, дизлайки, отклики низкий вам поклон!
Пожалуйста, оставьте свои мнения по текущей теме статьи. Мы крайне благодарны вам за ваши комментарии, дизлайки, лайки, отклики, подписки!
ВЛВиктория Лебедеваавтор-переводчик статьи «Bubble Sort»
Модификации[править]
Сортировка чет-нечетправить
Сортировка чет-нечет (англ. odd-even sort) — модификация пузырьковой сортировки, основанная на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность — .
Псевдокод указан ниже:
function oddEvenSort(a):
for i = 0 to n - 1
if i mod 2 == 0
for j = 2 to n - 1 step 2
if a < a
swap(a, a)
else
for j = 1 to n - 1 step 2
if a < a
swap(a, a)
Преимущество этой сортировки — на нескольких процессорах она выполняется быстрее, так как четные и нечетные индексы сортируются параллельно.
Сортировка расческойправить
Сортировка расческой (англ. comb sort) — модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность — , но стремится к . Является самой быстрой квадратичной сортировкой. Недостаток — она неустойчива. Псевдокод указан ниже:
function combSort(a):
k = 1.3
jump = n
bool swapped = true
while jump > 1 and swapped
if jump > 1
jump /= k
swapped = false
for i = 0 to size - jump - 1
if a < a
swap(a, a)
swapped = true
Пояснения: Изначально расстояние между сравниваемыми элементами равно , где — оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком.
Сортировка перемешиваниемправить
Сортировка перемешиванием (англ. cocktail sort), также известная как Шейкерная сортировка — разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность — , но стремится она к , где — максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:
function shakerSort(a):
begin = -1
end = n - 2
while swapped
swapped = false
begin++
for i = begin to end
if a > a
swap(a, a)
swapped = true
if !swapped
break
swapped = false
end--
for i = end downto begin
if a > a
swap(a, a)
swapped = true
Нахождение Максимума
2.1. Первое объяснение.
Алгоритм нахождения максимального элемента эквивалентен алгоритму сортировки нахождения минимального элемента, только имеет обратный смысл сортировка от большего к меньшему и от меньшего к большему.
Найдите первое максимальное число, поменяйте его местами с первым и далее повторите процедуру до последнего, не брав во внимание первое число и так далее (потом не брав во внимание первое и второе, поменяв местами второе и максимальное в оставшемся массиве, если оно больше, потом первое, и второе, и третье и т.д.). Это алгоритм сортировки от большему к меньшему
Переставляйте на последнее место, если хотите получить алгоритм от меньшего к большему.
2.2. Второе объяснение.
Первого объяснения (2.1. Первое объяснение.) достаточно для тех, кто уже знает этот алгоритм, теперь рассмотрим алгоритм сортировки нахождением максимума от меньшего к большему подробнее:
- 1. Введите временную переменную index для запоминания текущего значения номера элемента массива.
- 2. Выполните цикл N раз, где N равно размеру массива минус единица. Введите переменную i для количества уже проанализированных элементов — это счётчик цикла. Объявите её для начала алгоритма на конец массива:
- 2.1. Присвойте переменной index значение i.
- 2.2. Выполните цикл от до размер массива — i, где j счётчик этого цикла. Далее массив будем называть arr, а доступ к i-тому элементу будем называть arr
2.2.1. Если arr меньше j-того элемента (arr < arr), то присвойте переменной index начение счётчика j, index:=j.
:
- 2.3. Обменяйте местами значения элементов массива с индексами. index и размер массива — i.
- Конец.
Далее рассмотрим блок-схему алгоритма, т.к. в алгоритме не учтено присвоение счётчиков цикла:
Входные данные: arr — входной сортируемый массив.
Рис. 2. Блок-схема алгоритма сортировки нахождением максимума от меньшего к большему.
Также возможен алгоритм сортировки от большего к меньшему, но с другими параметрами.
2.3. Третье объяснение.
private static void sortArrMax(ArrayList<Integer> arr) {
// 1. Введите временную переменную index для запоминания текущего значения номера элемента массива.
int index;
// Введём переменную для обмена, запомните сортировать можно не только числа.
Integer temp;
// 2. Выполните цикл N раз, где N равно размеру массива минус единица. Введите переменную i для количества уже проанализированных элементов — это счётчик цикла. Объявите её для начала алгоритма на конец массива:
for(int i = arr.size() — 1; i >= 0; i—) {
// 2.1. Присвойте переменной index значение i.
index = i;
// 2.2. Выполните цикл от 0 до i-1, где j счётчик этого цикла. Далее массив будем называть arr, а доступ к i-тому элементу будем называть arr:
for(int j = i — 1; j >= 0; j— ) {
// 2.2.1. Если arr больше j-того элемента (arr > arr), то присвойте переменной index начение счётчика j, index:=j
if(arr.get(index) < arr.get(j)) index = j;
}
// Обменяйте местами значения элементов массива с индексами. index и i.
temp = arr.get(index);
arr.set(index, arr.get(i));
arr.set(i, temp);
}
}
Сортировка пузырьком
Идея алгоритма очень простая. Идём по массиву чисел и проверяем порядок (следующее число должно быть больше и равно предыдущему), как только наткнулись на нарушение порядка, тут же обмениваем местами элементы, доходим до конца массива, после чего начинаем сначала.
Отсортируем массив {1, 5, 2, 7, 6, 3}
Идём по массиву, проверяем первое число и второе, они идут в порядке возрастания. Далее идёт нарушение порядка, меняем местами эти элементы
Продолжаем идти по массиву, 7 больше 5, а вот 6 меньше, так что обмениваем из местами
3 нарушает порядок, меняем местами с 7
Возвращаемся к началу массива и проделываем то же самое
void bubbleSort(int *a, size_t size) {
size_t i, j;
int tmp;
for (i = 1; i < size; i++) {
for (j = 1; j < size; j++) {
if (a > a) {
tmp = a;
a = a;
a = tmp;
}
}
}
}
Этот алгоритм всегда будет делать (n-1)2 шагов, независимо от входных данных. Даже если массив отсортирован, всё равно он будет пройден (n-1)2 раз. Более того, будут в очередной раз проверены уже отсортированные данные.
Пусть нужно отсортировать массив 1, 2, 4, 3
После того, как были поменяны местами элемента a и a нет больше необходимости проходить этот участок массива
Примем это во внимание и переделаем алгоритм
void bubbleSort2(int *a, size_t size) {
size_t i, j;
int tmp;
for (i = 1; i < size; i++) {
for (j = i; j > 0; j--) {
if (a < a) {
tmp = a;
a = a;
a = tmp;
}
}
}
}
Ещё одна реализация
void bubbleSort2b(int *a, size_t size) {
size_t i, j;
int tmp;
for (i = 1; i < size; i++) {
for (j = 1; j <= size-i; j++) {
if (a < a) {
tmp = a;
a = a;
a = tmp;
}
}
}
}
В данном случае будет уже вполовину меньше шагов, но всё равно остаётся проблема сортировки уже отсортированного массива: нужно сделать так, чтобы отсортированный массив функция просматривала один раз. Для этого введём переменную-флаг: он будет опущен (flag = 0), если массив отсортирован. Как только мы наткнёмся на нарушение порядка, то флаг будет поднят (flag = 1) и мы начнём сортировать массив как обычно.
void bubbleSort3(int *a, size_t size) {
size_t i;
int tmp;
char flag;
do {
flag = 0;
for (i = 1; i < size; i++) {
if (a < a) {
tmp = a;
a = a;
a = tmp;
flag = 1;
}
}
} while (flag);
}
В этом случае сложность также порядка n2, но в случае отсортированного массива будет всего один проход.
Теперь усовершенствуем алгоритм. Напишем функцию общего вида, чтобы она сортировала массив типа void. Так как тип переменной не известен, то нужно будет дополнительно передавать размер одного элемента массива и функцию сравнения.
int intSort(const void *a, const void *b) {
return *((int*)a) > *((int*)b);
}
void bubbleSort3g(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) {
size_t i;
void *tmp = NULL;
char flag;
tmp = malloc(item);
do {
flag = 0;
for (i = 1; i < size; i++) {
if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) {
memcpy(tmp, ((char*)a + i*item), item);
memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item);
memcpy(((char*)a + (i-1)*item), tmp, item);
flag = 1;
}
}
} while (flag);
free(tmp);
}
Функция выглядит некрасиво – часто вычисляется адрес текущего и предыдущего элемента. Выделим отдельные переменные для этого.
void bubbleSort3gi(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) {
size_t i;
void *tmp = NULL;
void *prev, *cur;
char flag;
tmp = malloc(item);
do {
flag = 0;
i = 1;
prev = (char*)a;
cur = (char*)prev + item;
while (i < size) {
if (cmp(cur, prev)) {
memcpy(tmp, prev, item);
memcpy(prev, cur, item);
memcpy(cur, tmp, item);
flag = 1;
}
i++;
prev = (char*)prev + item;
cur = (char*)cur + item;
}
} while (flag);
free(tmp);
}
Теперь с помощью этих функций можно сортировать массивы любого типа, например
void main() {
int a = {1, 0, 9, 8, 7, 6, 2, 3, 4, 5};
int i;
bubbleSort3gi(a, sizeof(int), 10, intSort);
for (i = 0; i < 10; i++) {
printf("%d ", a);
}
_getch();
}
Заключение
Метод пузырька гораздо менее эффективен других алгоритмов, однако он имеет простую и понятную реализацию, поэтому часто используется в учебных целях. Кроме того, пузырьковая сортировка может использоваться для работы с небольшими массивами данных.
На самом деле, вместо самостоятельного написания алгоритмов сортировки программисты на Python используют стандартные функции и методы языка, такие как и . Эти функции отлажены и работают быстро и эффективно.
Знания особенностей алгоритмов сортировки, их сложности и принципов реализации в общем виде пригодятся каждому программисту, желающему пройти собеседование и стать Python-разработчиком.
