Пузырьковая сортировка в excel
Если вы хотите начать писать макросы на VBA (да и на любом другом языке), то помимо знания самого языка программирования хорошем подспорьем в работе будет знание и умение писать алгоритмы. Как и в любом другом деле для этого потребуется практика, много практики. В этой статье мы разберем алгоритмы сортировки, знание их спрашивают практически на любом собеседование на должность программиста, да и студентов часто мучают ими. Изучите их, это хороший опыт и практика для начинающих!
О чем пойдет речь
В статье разберем 9 видов сортировок, рассмотрим суть этих алгоритмов. Скорости, сложность алгоритмов и практическое их применение оставим за скобками. Задача статьи показать, что одну и туже задачу можно решать различными способами, показать практическое применение языка VBA и помочь начинающим в его освоении.
Подготовительный этап
Перед тем как начинать писать алгоритмы немного подготовимся. Создадим общую константу n для хранения размера массивов. Вставим на лист диаграмму, чтобы отслеживать как все работает. В коде объявим объект нашей диаграммы, на которой будем просматривать ход процесса сортировки. Чтобы не дублировать код в каждом алгоритме сортировки мы будем использовать процедуру инициализации Init().
Чтобы наша диаграмма с результатом не подвисала и обновлялась напишем такую функцию.
В качестве массивов будем использовать диапазон ячеек A1:Y1. Напишем еще одну коротенькую процедуру для перемешивания этого массива, точнее заполнения его числами от 1 до 25 в случайном порядке.
Теперь все готово, давайте писать алгоритмы сортировки.
Сортировка пузырьком
Пузырьковая сортировка (или сортировка простыми обменами) пожалуй самый неэффективный алгоритм сортировки и в тоже время пожалуй самый известный.
Суть алгоритма в прохождении в цикле по всем элементами массива и в попарном сравнении текущего элемента со следующим. Если текущий элемент массива больше (для сортировки по возрастанию и меньше для сортировки по убыванию) чем следующий, то эти два элемента меняются друг с другом местами. Ход алгоритма смотрите на следующей диаграмме.
Вот код сортировки данным алгоритмом на VBA. Еще стоит обратить внимание на переменную Flag она служит индикатором того, что массив досрочно отсортирован и можно заранее выйти из цикла и сократить вычислительные ресурсы.
Далее описана процедура Swap для перестановки ячеек местами. После перестановки ячеек вызывается процедура ChartRefresh обновления диаграммы.
Сортировка перемешиванием
Этот алгоритм является разновидностью пузырьковой сортировки. Также этот алгоритм называют Шейкерной сортировкой или двунаправленной. Основное отличие от обычной сортировки пузырьком в том, что массив сначала просматривается слева направо и максимальный элемент перемещается вправа, а после мы проходим по массиву справа налево (от последнего отсортированного элемента) и наименьший элемент перемещается влево. Вот на графике отчетливо это видно.
Алгоритм немного больше, но по сложности аналогичный, вот его код на VBA.
Сортировка выбором
Тоже достаточно простой алгоритм сортировки. Суть его заключается в поиске минимального значения (максимального для сортировки по убыванию) и обмене найденного значения с первым неотсортированным значением. Т.е. нашли первое минимальное значение, поменяли его с первым элементом, нашли второе минимальное - поменяли со вторым элементом. График получается следующий:
Объединение сортировки пузырьком и сортировки выбором
Можно ускорить алгоритм сортировки пузырьком объединив его с алгоритмом сортировки выбором. Для этого нужно определять минимальный элемент во внутреннем цикле и после каждого прохода по списку обменивать найденный минимальный элемент с первым неотсортированным слева. Таким образом, мы сокращаем в 2 раза число перестановок, но при этом увеличиваем в 2 раза число сравнений.
Код отличается только 2 строчками:
Сортировка вставками
Вот определение сортировки с википедии
Это алгоритм, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.
Другими словами мы во внешнем цикле проходим по всем элементам массива, а во внутреннем цикле сравниваем правый элемент с уже отсортированными элементами слева и перемещаем его при необходимости. Вот как это выглядит визуально:
Код тоже думаю окажется для вас достаточно простым.
Гномья сортировка
Визуально отличия от сортировки вставками нет, однако в код совершенно другой так как нет никаких вложенных циклов. Алгоритм в цикле проходит по всем элементам, сравнивая текущий элемент с предыдущим. Если элементы стоят верно переходит к следующему, если нет, меняет их местами и переходит к предыдущему элементу.
Сортировка слиянием
Простые алгоритмы сортировки мы разобрали, теперь давайте рассмотрим более сложные виды сортировок. Хотя главное понять суть алгоритма и его реализация уже не будет казаться сложной.
Суть алгоритма сортировки слиянием состоит в том, чтобы разбить исходный массив на более мелкие массивы, отсортировать каждый по отдельности, а после объединить результаты.
Для этого первоначальный массив разбивается на 2 части пополам (ну или почти пополам если количество нечетное), каждая половинка разбивается еще пополам и так до тех пор, пока мы не получим массивы состоящие из 1 элемента. После прохождения процедуры разбивки на части, слияние каждой части и ее сортировка. Например, массив содержит числа 5 2 1 3 4. Разбиваем его на две части: 5,2,1 и 3,4 . Первую часть 5,2,1 разбиваем еще на две части 5,2 и 1. Далее 5,2 еще на две части 5 и 2. А теперь идем обратно, сортируем и сливаем массивы. Получается 2,5 и 1, объединим дальше - 1,2,5 , последняя итерация отсортирует исходный массив 1 2 3 4 5. При слиянии учитывается тот факт, что массивы уже отсортированы по отдельности, поэтому объединение проходит быстрее.
Вот визуализация работы алгоритма:
Код состоит из двух частей. Первая MergeSort - рекурсивная функция разделения массивов, т.е. эта функция запускает саму себя. Это происходит до тех пор, пока размер массива больше 1, иначе запускается функция MergeSort для каждой из частей.
После того как массивы разобьются запускается функция Merge(left, right), которая сортирует и объединяет массив обратно.
В качестве сортировки и объединения можно использовать различные алгоритмы, например такой. Если кто-то предложит более изящное решение - пишите в комментариях.
Так как функция у нас рекурсивная, то первый ее запуск необходимо сделать из отдельной процедуры, вот так:
Быстрая сортировка
Алгоритм быстрой сортировки - один из самых быстрых и эффективных и часто используется в практике. При этом он достаточно простой.
Суть алгоритма в следующем:
- Выбрать из массива опорный элемент. Например, взять элемент в середине массива (в целом это может быть любой из элементов).
- Сравнить остальные элементы массива с выбранным опорным элементов и разбить массив на 2 части:
- элементы, которые меньше или равны опорному элементу;
- элементы, которые больше опорного.
- Далее пункты 1 и 2 повторяются рекурсивно для каждой части массива, до тех пор пока размер части состоит из более чем 1 элемента.
На визуализации к сожалению что-то разглядеть сложно. Алгоритм достаточно быстро отрабатывает:
Вот код данного алгоритма на VBA.
Запуск рекурсивной функции быстрой сортировки запустим из отдельного метода.
Пирамидальная сортировка
Пирамидальная сортировка или как еще ее называют "Сортировка кучей" использует в своем алгоритме двоичное дерево.
Это такое дерево, для которого выполнены следующие условия:
- Значение в любой вершине не меньше, чем значения её потомков.
- Длина веток дерева не отличается друг от друга более чем на 1 слой.
- Последний слой заполняется слева направо без «дырок».
Вот пример дерева, которое можно найти на википедии:
Это дерево можно представить в виде следующего массива, где для любого элемента A[i] потомками являются элементы A[2i] и A[2i+1].
Т.е. для каждого элемента кучи справедливы следующие условия: A[i] >= A[2i] и A[i] >= A[2i+1].
Алгоритм пирамидальной сортировки состоит из следующих шагов:
- Построение массива в виде двоичного дерева.
- Исключение корня дерева (максимального значения массива) из массива и перенос его в конец последовательности.
- После исключения корня дерево перестраивается и его корень опять отсекается и переносится в конец.
- Так происходит до тех пор, пока вся последовательность не отсортируется.
Вот визуальное отображение выполнения этого алгоритма:
Ниже код пирамидальной сортировки на VBA. Который формирует двоичную кучу и корень этой кучи переносит в конец последовательности. Так происходит n раз.
При работе с данными в Excel может понадобиться их упорядочить. Например, в большой организации нужен список сотрудников в алфавитном порядке фамилий, а также списки их в порядке убывания или возрастания стажа работы, возраста или размера зарплаты. Для решения этой задачи не требуется вводить данные несколько раз. С помощью механизма сортировки в Excel легко отсортировать имеющиеся данные в нужном порядке.
Если данные текстовые, их можно отсортировать по алфавиту («от А до Я» или «от Я до А»). Если данные числовые, их можно отсортировать в порядке возрастания или убывания. Если в диапазоне данных есть строка или столбец, в которых содержатся данные типа время или дата, их можно отсортировать в прямом или обратном хронологическом порядке. Имеется также возможность сортировки предварительно отформатированных данных по элементам этого форматирования.
Сортировать данные можно по одному условию (например, сортировка списка сотрудников по фамилии) или нескольким (например, сортировка списка сотрудников по занимаемой должности, а внутри каждой должности фамилии отсортировать в алфавитном порядке). Данные можно сортировать по столбцу (или нескольким столбцам) или по строке.
Сортировка по одному критерию
- В столбце, по которому должна быть выполнена сортировка, нужно выделить любую ячейку (весь столбец выделять не надо).
- На вкладке Данные [Data] найти группу команд Сортировка и фильтр [Sort&Filter].
Отметим, что буквы на этой кнопке указывают только на направление сортировки, а вид кнопки остается один и тот же и при текстовых, и при числовых данных.
Существует и другой удобный способ сортировки данных: щелкнув правой кнопкой мыши по ячейке столбца, по которому будет выполняться сортировка, в контекстном меню выбрать пункт Сортировка [Sort], а далее – требуемый вариант сортировки.
Многоуровневая сортировка
- Выделить одну ячейку из сортируемого массива данных.
Если диапазоне данных имеются пустые столбцы или строкой, то Excel автоматически воспринимает их как границы сортируемого массива данных. В таком случае следует выделить все данные, подлежащие сортировке.
- На вкладке Данные [Data] найти группу команд Сортировка и фильтр [Sort&Filter] и на ней выбрать команду Сортировка [Sort].
- Последовательно задать уровни сортировки (определяемые именем столбца).
Нажимая на стрелку возле трех полей (Столбец, Сортировка, Порядок) необходимо выбрать:
- Имя столбца для сортировки.
- Тип критерия (в зависимости от того, будет ли вестись сортировка по значениям данных в столбце, или по оформлению ячейки, или по значку ячейки).
- Порядок сортировки (по убыванию или по возрастанию).
Если выбранный для сортировки столбец содержит названия месяцев или дней недели, то в списке поля Порядок можно выбрать опцию Настраиваемый список и в новом окне отметить один из предлагаемых вариантов сортировки.
Сортировка по форматированию
Часто для анализа данных делается заливка ячеек (или шрифта) цветом. С помощью сортировки можно также упорядочивать данные на основе их форматирования.
Пошаговый порядок действий:
- Щелкнуть по любой ячейки из столбца, по которому будет выполняться сортировка.
- На вкладке Данные [Data] выбрать группу Сортировка и фильтр [Sort&Filter], а затем выбрать команду Сортировка [Sort].
- В поле Столбец [Column] укажите столбец по которому будет проводиться сортировка.
- В поле Сортировка [Sort On] из всплывающего меню выбрать критерий сортировки: цвет ячейки, цвет шрифта или значок ячейки.
- Поле Порядок [Order] содержит два выпадающих списка. В первом нужно выбрать тип критерия, а во втором – размещение ячеек, отсортированных по данному критерию (строку Сверху [On Top] или Снизу [On Bottom]).
- При необходимости добавить еще один критерий сортировки, в окне Сортировка нужно выбрать кнопку Добавить уровень.
Можно также воспользоваться командой «Копировать уровень» [Copy Level], заменив в поле «Порядок» прежнее значение на новое.
Рис.1 Алгоритмы сортировки массивов.VBA.Макросы.
В моем массиве хранятся (генерируются случайным образом) только целые числа.
Массив глобальный, т.е. все подпрограммы имеют к нему доступ.
Public a( ) As Integer
Поскольку сортировка массива подразумевает замену элементов местами, то без процедуры (подпрограммы) swap здесь не обойтись.
Нет, обойтись, конечно, можно, но придется часто повторять однотипный код из трех операторов.
Итак, замена значений переменных с использованием третьей (временной):
Private Sub swap(p As Integer, q As Integer, bool As Boolean)
'меняет местами два элемента массива
Dim t As Integer
t = a(p): a(p) = a(q): a(q) = t
bool = False
End Sub
В процедуру передаются два индекса элементов массива и логическая переменная (по ссылке), которую я буду называть «показатель сортировки» или «флаг сортировки».
При любом вызове этой процедуры, как видите, флаг сбрасывается.
Метод Пузырька или пузырьковая сортировка
наиболее простой и не очень быстрый метод. Есть смысл использовать его для небольших массивов и в учебных целях.
Его суть: сравнить два соседних элемента массива и если они расположены не в «нужном» порядке, то поменять их местами.
Вот условие сортировки по возрастанию:
If a(i) > a(i + 1) Then swap i, i + 1, bool
Показал и все. В дальнейшем сортирую только по возрастанию. Для удобства восприятия
Как видите, если соседние элементы равны или не удовлетворяют условию замены, то просто ничего не происходит, а элементы остаются на своих местах.
Следующий момент: соседние элементы, конечно, рассматриваются и сравниваются парами в цикле. Но можно цикл начать от начала массива (прямой прогон), а можно с конца (обратный прогон).
Вот, прямой прогон:
For i = 1 To sizeArr -1 'прямой ход.
If a(i) > a(i + 1) Then swap i, i + 1, bool
Next i
А вот, обратный прогон:
For i = sizeArr To 2 Step -1 'обратный ход.
If a(i) < a(i - 1) Then swap i, i - 1, bool
Next i
Конечно, за один прогон, массив будет отсортирован только в очень редких случаях, и данный метод подразумевает неопределенное (необходимое и достаточное) количество прогонов для достижения желаемого результата Но поговорим о прямом и обратном прогонах. В чем их отличие? И почему метод называется «методом пузырька»?
При прямом прогоне слева направо устремляются более крупные числа, как пузырьки воздуха всегда устремляются вверх. Если на первом месте было максимальное число данного массива а(1)=max, то при прямом прогоне оно беспрепятственно на каждом очередном шаге займет второе, третье и наконец последнее, самое правое место в массиве a(sizeArr)=max.
Если же это было не самое большое число (но и не самое маленькое), то оно тоже устремится направо, пока не встретит на своем пути более крупное число. Дальше путь к вершине продолжит уже это новое более крупное число.
Вспомните, как большие пузырьки всегда всплывают быстрее
Таким образом, за один прямой прогон массив отсортирован не будет, но его последним элементом станет обязательно максимальное по величине число. При этом первым элементом массива станет наименьшее из чисел, располагавшихся на первом и втором местах.
А при единственном обратном прогоне (не забывайте, что массив сортируется по возрастанию) первым элементом массива станет минимальное число. Про остальные ничего определенного сказать нельзя, кроме того, что каждое более мелкое число по сравнению со своим левым соседом, обменялось с ним местами.
За второй обратный прогон, вторым элементом станет второе по «мелкости» число. Оно никак не сможет занять первое место, так как там уже находится минимальное в массиве число. Поэтому сделаем однозначный вывод, что каждый последующий прогон целесообразно заканчивать на шаг раньше предыдущего. Этим сэкономим немного машинного времени.
Так сколько же раз нужно выполнить прогоны, чтобы массив полностью был отсортирован?
Конечно, для полной уверенности и 100% гарантии можно любой из прогонов (это без разницы) выполнить sizeArr-1 раз.
К гадалке не ходи, все элементы будут расположены по возрастанию. Но при этом вполне вероятно, что последние прогоны проходили бы уже без замен элементов, так как последние элементы были расположены по порядку и условие на замену не выполнялось. Вот, чтобы исключить, подобное и сэкономить еще немного машинного времени, используют «флаг сортировки», т.е. обычную логическую переменную, которая до начала прогона имела бы значение true. Даже при единственной замене двух «соседей» за весь прогон, в процедуре swap данный флаг сбросится. Но зато уж, если после прогона флаг остался равным true, то можно с уверенностью прекращать сортировку, т.к. из всех пар соседних элементов, ни одна не выразила желание поменяться местами. Это та же самая 100% гарантия, что и при избыточности прогонов.
Private Sub prForward(p As Integer, q As Integer, bool As Boolean)
Dim i As Integer
bool = True
For i = p To q 'прямой ход. максимальный элемент займет самое правое место
If a(i) > a(i + 1) Then swap i, i + 1, bool
Next i
End Sub
Private Sub prBack(p As Integer, q As Integer, bool As Boolean)
Dim i As Integer
bool = True
For i = p To q Step -1 'обратный ход. min-элемент займет самое левое место
If a(i) < a(i - 1) Then swap i, i - 1, bool
Next i
End Sub
Вот так я написал две процедуры для прямого и обратного прогонов. Они мне еще не раз пригодятся. А Вы можете, при желании, обойтись и любой одной. Дело вкуса и конкретной решаемой задачи
И как результат привожу два варианта главной процедуры метода пузырьковой сортировки:
Public Sub sortPusir() 'двухпроходный
Dim i As Integer, j As Integer, bSorted As Boolean
For j = LBound(a) To UBound(a) - 1
prForward LBound(a) + j, UBound(a) - j, bSorted
If bSorted Then Exit For 'значит сортировка окончена
prBack UBound(a) - 1 - j, LBound(a) + j, bSorted
If bSorted Then Exit For 'значит сортировка окончена
Next j
End Sub
bSorted флаг сортировки. Его даже инициализировать не надо, т.к. он однозначно устанавливается в true перед каждым прогоном в процедурах прямого и обратного прогона.
Хочу отметить, что хотя цикл по j определен до UBound(a) 1, но реально он даже до середины не дойдет, т.к. при двухпроходном цикле выход по флагу сортировки может осуществиться после любого из прогонов.
Public Sub sortPusir1() 'однопроходный
Dim i As Integer, j As Integer, bSorted As Boolean
For j = LBound(a) To UBound(a) - 1
prBack UBound(a), j + 1, bSorted
If bSorted Then Exit For 'значит сортировка окончена
Next j
End Sub
В однопроходном алгоритме все еще проще. Обратите внимание, что цикл по j идет на увеличение, а прогоны обратные, поэтому все прогоны будут начинаться от самого верхнего индекса массива, а заканчиваться на шаг раньше, чем предыдущий прогон.
Алгоритм Хоара или быстрая, рекурсивная сортировка
Понятное дело, раз алгоритм основан на рекурсии (т.е. при определенных условиях должен вызывать сам себя с измененными входными параметрами), то входные параметры этой процедуры заслуживают особого внимания.
Public Sub sortHoara(p As Integer, q As Integer)
Каким же образом алгоритм проводит грубую сортировку? И как происходит деление на левую и правую части для последующей сортировки?
процедура проверяет входные параметры на соответствие и принимает решение о продолжении или завершении своей работы, а вот (если решила продолжать выполняться) она определяет ОПОРНОЕ ЗНАЧЕНИЕ. Для хранения опорного значения в процедуре выделена отдельная переменная того же типа, что и хранящиеся элементы массива. В моем случае это r As Integer, но если в массиве будут храниться действительные числа или строки, то и опорное значение должно быть того же типа. Кроме того, опорное значение должно быть обязательно «больше или равно» минимальному элементу массива и «меньше или равно» максимальному.
ГРУБАЯ СОРТИРОВКА подразумевает перемещение любого элемента, который больше «опорного значения» в правую часть массива, и любого, который меньше «опорного значения», в левую часть (если сортировка по возрастанию, а иначе - наоборот). В идеальном варианте, «опорное значение» хотелось бы определить таким, чтобы ровно половина элементов массива его превышала, а половина массива была меньше него. Именно при таком варианте количество рекурсивных вызовов было бы минимальным, а, следовательно, и время выполнения сортировки.
А в самом тривиальном случае, r можно присвоить первое попавшееся значение массива, например: r=a(p) или r=a(q). Это будет вполне удовлетворять условиям выбора опорного значения, правда, про оптимальность времени выполнения алгоритма здесь вспоминать не будем. А если честно, то при таком выборе r и большом размере массива при определенных условиях алгоритм не сможет завершиться из-за переполнения стека (ведь каждый рекурсивный вызов это дополнительное наполнение стека).
Но не будем отвлекаться, и продолжаем рассматривать самый тривиальный случай с выбором r=a(p). В несортированном массиве, по теории вероятности, это будет какое-то промежуточное число между максимальным и минимальным элементами массива.
, процедура ищет элемент (т.е. определяет индекс i элемента), который больше r, начиная с начала диапазона.
, процедура ищет элемент (т.е. определяет индекс j элемента), который меньше r, начиная с конца диапазона.
При выполнении условия If i < j And a(i) >a(j) Then swap i, j, False , как видим, происходит обмен (). Учитывая, что шаги 3-5 производятся в цикле Do While , то после окончания цикла, в левой части массива элементы будут располагаться беспорядочно, но среди них не будет ни одного большего r. Точно так же, в правой части, среди беспорядочно расположенных элементов, не будет ни одного меньше r. Это и есть грубая сортировка (по крайней мере, я для себя ее так называю). А значение j разделит массив на левую и правую части.
Следующими шагами процедуры (т.е. алгоритма) будут поочередная обработка левой и правой частей массива, путем рекурсивного вызова себя самой.
Вот пример такой, самой незамысловатой, процедуры сортировки по алгоритму Хоара:
Public Sub sortHoara_s(p As Integer, q As Integer)'самый простой вариант
Dim i As Integer, j As Integer, r As Integer
If p < q Then 'если на входе одинаковые или обратные индексы, то на выход
r = a(p) ' опорное значение
i = p - 1: j = q + 1 ' отступление за границы, чтобы не нарушать while
Do While i < j ' поиск элементов для обмена
Do
i = i + 1
Loop While a(i) < r
'i останавливается на элементе больше опорного (который надо направо)
Do
j = j - 1
Loop While a(j) > r
'j останавливается на элементе меньше опорного (который надо налево)
If i < j And a(i) >a(j) Then swap i, j, False ' обмен
Loop
sortHoara_s p, j ' сортируем левую часть
sortHoara_s j + 1, q ' сортируем правую часть
End If
End Sub
Это понятно. Принимая за опорное значение самый левый элемент отсортированного массива, программа делит массив на две части: в левой части 1 элемент, а в правой весь массив без первого элемента. Вызывается рекурсивно левая часть и заканчивается мгновенно, а вот правая часть опять делится на 1 элемент и все остальное. Итого для завершения задачи должно произойти sizeArr-1 рекурсивных вызовов. При достаточно большом sizeArr и большом количестве элементов массива расположенных в порядке возрастания, такой момент должен наступить неминуемо. Область памяти, отводимая под стек имеет свой предел.
Но если внести незначительные изменения
Public Sub sortHoara(p As Integer, q As Integer)
Dim i As Integer, j As Integer, r As Integer, bSorted As Boolean
If p < q Then 'если на входе одинаковые или обратные индексы, то на выход
If GetSortedMaxMin(p, q, mx, mn) Then Exit Sub
'если участок уже отсортирован - на выход
r = Round((mx + mn) / 2) ' опорное значение. Оптимально по середине
i = p - 1: j = q + 1 ' отступление за границы, чтобы не нарушать while
Do While i < j ' поиск элементов для обмена
Do
i = i + 1
Loop While a(i) < r
'i останавливается на элементе больше опорного (который надо направо)
Do
j = j - 1
Loop While a(j) > r
'j останавливается на элементе меньше опорного (который надо налево)
If i < j And a(i) >a(j) Then swap i, j, False ' обмен
Loop
sortHoara p, j ' сортируем левую часть
sortHoara j + 1, q ' сортируем правую часть
End If
End Sub
Где функция GetSortedMaxMin(p, q, mx, mn) возвращает «true» если заданный диапазон массива уже отсортирован, что ведет к выходу из данного рекурсивного вызова. А если диапазон не отсортирован, то в параметрах по ссылке mx, mn будут находиться максимальный и минимальный элементы массива соответственно, что позволит, более оптимально, определить «опорное значение». Хотя и этот вариант, конечно, не на все случаи жизни Он просто немного лучше предыдущего…
Сортировка Слиянием и Хоара - совмещение
Совмещение алгоритмов Хоара и сортировки слиянием является наиболее оптимальным
Алгоритм сортировки слиянием отлично описан в Википедии.
Не сложно понять, что наибольший эффект от сортировки слиянием получается при объединении двух отсортированных массивов. А в начальный период, когда идет дробление исходного массива на части (как правило, до какой-то определенной величины, а то и до элемента), машинное время и память используются крайне не эффективно.
Как же тут не вспомнить про быструю, рекурсивную сортировку (Хоара). В том алгоритме все наоборот. Очень быстро сортируются сравнительно малые массивы (равномерно перемешанные), а в случае очень больших массивов (особенно если определенная часть уже отсортирована) может происходить рекурсивное переполнение стека.
Вывод: сортировку слиянием следует совмещать с быстрой сортировкой.
Не дробить начальный массив до элемента, а лишь до величины заданной константой MIN_CHUNK_SIZE и эти куски сортировать быстрой сортировкой, ну, а объединять потом, конечно, слиянием.
Таким образом, процедуру, объединяющую два предварительно отсортированных участка массива, можно представить так:
Public Sub merge(p As Integer, m As Integer, q As Integer)
Dim tmp() As Integer 'временный результирующий массив
Dim i As Integer, j As Integer, r As Integer счетчики
ReDim tmp(p To q)
i = p: j = m: r = p
For i = p To q перезапись объединенного массива в исходный
a(i) = tmp(i)
Next i
End Sub
- р - начальный индекс первого массива, он же будет и начальным индексам объединенного массива;
- m (средний) индекс являющийся начальным во втором массиве, поэтому первый отсортированный массив (или участок исходного массива) конечным индексом будет иметь m-1;
- q конечный индекс второго отсортированного и объединенного массивов.
А основная процедура сортировки, которая рекурсивно разбивает исходный массив на части длиною меньше константы MIN_CHUNK_SIZE и сортирует их, вызывая метод Хоара, а затем отсортированные части объединяет слиянием, может быть представлена так:
Public Sub mergesort(p As Integer, q As Integer)
Dim leng As Integer, midl As Integer, i As Integer
If leng > MIN_CHUNK_SIZE Then
midl = leng / 2 'индекс элемента, разделяющего массив пополам
mergesort p, p + midl 1 'сортируем левую часть
mergesort p + midl, q ' сортируем правую часть
merge p, p + midl, q ' объединяем слиянием
Else
sortHoara_s p, q ' сортируем Хоаром
End If
End If
End Sub
В этом варианте никогда не происходит переполнения стека (ведь всегда можно уменьшить константу MIN_CHUNK_SIZE) и скорость сортировки достаточно хорошая
ЕЩЁ ПРИМЕРЫ:
Если у Вас остались вопросы, то задать их Вы можете, нажав на эту кнопочку .
460040, г.Оренбург ©2010 Учебные программы и сайты для студентов
Большинство из тех, кто хоть раз строил графики в Microsoft Excel или PowerPoint, замечали необычный и забавный тип диаграмм - пузырьковые (bubble chart). Многие видели их в чужих файлах или презентациях. Однако, в 99 случаев из 100, при попытке самостоятельно построить такую диаграмму впервые, пользователи сталкиваются с рядом неочевидных сложностей. Обычно Excel или отказывается ее создавать вообще, или создает, но совершенно непонятного вида, без подписей и наглядности.
Давайте разберемся в этой теме.
Что такое пузырьковая диаграмма
По горизонтальной оси Х откладывается средний годовой доход на душу населения в USD. По вертикальной оси Y откладывается средняя продолжительность жизни в годах. Размер же (диаметр или площадь) каждого пузырька пропорционален населению каждой страны. Таким образом, на одной плоской диаграмме удается отобразить трехмерную информацию.
Дополнительную информационную нагрузку несет еще и цвет, отображающий региональную принадлежность каждой страны к определенному континенту.
Как построить пузырьковую диаграмму в Excel
Самый важный момент при построении пузырьковой диаграммы - правильно подготовленная таблица с исходными данными. А именно - таблица должна состоять строго из трех столбцов в следующем порядке (слева-направо):
- Параметр для откладывания по оси Х
- Параметр для откладывания по оси Y
- Параметр, определяющий размер пузырька
Возьмем для примера вот такую таблицу с данными по игровым приставкам:
Чтобы построить по ней пузырьковую диаграмму, нужно выделить диапазон C3:E8 (строго - только оранжевые и серые ячейки без столбца с названиями) и затем:
- В Excel 2007/2010 - перейти на вкладку Вставка- группа Диаграммы-Другие-Пузырьковая (Insert - Chart - Bubble)
- В Excel 2003 и старше - выбрать в меню Вставка - Диаграмма - Пузырьковая (Insert - Chart - Bubble)
Получившаяся в итоге диаграмма будет отображать быстродействие приставок по оси X, число программ для них по оси Y и долю рынка, занимаемого каждой приставкой - как размер пузырька:
После создания пузырьковой диаграммы имеет смысл настроить подписи к осям - без названий осей трудно понять, что по какой из них откладывается. В Excel 2007/2010 это можно сделать на вкладке Макет (Layout) , а в старых версиях Excel - щелкнув по диаграмме правой кнопкой мыши и выбрав команду Параметры диаграммы (Chart options) - вкладка Заголовки (Titles) .
К сожалению, Excel не позволяет автоматически привязывать цвет пузырьков к исходным данным (как в примере выше со странами), но для наглядности можно быстро отформатировать все пузырьки в разные цвета. Для этого щелкните правой кнопкой мыши на любом пузырьке, выберите команду Формат ряда данных (Format series) из контекстного меню и включите опцию Разноцветные точки (Vary colors) .
Проблема с подписями
Общей трудностью, с которой сталкиваются абсолютно все пользователи при построении пузырьковых (и точечных, кстати, тоже) диаграмм, являются подписи к пузырькам. Стандартными средствами Excel можно вывести в качестве подписей только значения X, Y, размер пузырька или называние ряда (общее для всех). Если вспомнить что при построении пузырьковой диаграммы вы не выделяли столбец с подписями, а только три столбца с данными X, Y и размер пузырьков, то все оказывается в общем-то логично: то, что не выделено - в диаграмму само никак попасть не может.
Решить проблему подписей можно тремя путями:
Способ 1. Вручную
Вручную переименовывать (менять) подписи для каждого пузырька. Можно просто щелкнуть мышью по контейнеру с подписью и ввести с клавиатуры новое название вместо старого. Очевидно, что при большом количестве пузырьков этот способ начинает напоминать мазохизм.
Способ 2. Надстройка XYChartLabeler
Нетрудно предположить, что с подобной проблемой до нас с вами сталкивались и другие пользователи Excel. И один из них, а именно легендарный Rob Bovey (дай бог ему здоровья) написал и выложил в открытый доступ бесплатную надстройку XYChartLabeler, добавляющую в Excel эту недостающую функцию.
После установки у вас появится новая вкладка (в старых версиях Excel - панель инструментов) XY Chart Labels:
Выделив пузырьки и воспользовавшись кнопкой Add Labels можно быстро и удобно добавить подписи сразу ко всем пузырькам в диаграмме, просто задав диапазон ячеек с текстом для подписей:
Способ 3. Excel 2013
В новой версии Microsoft Excel 2013 появилась наконец-таки возможность добавлять подписи к элементам данных диаграммы из любых произвольно выделенных ячеек. Дождались :)
Про обычные статические пузырьковые диаграммы я уже писал большую подробную статью, поэтому на основах я сейчас подробно останавливаться не буду. Если кратко, то пузырьковая диаграмма (Bubble Chart) - это, по-своему, уникальный тип диаграммы для отображения и обнаружения взаимосвязей (корреляции) между несколькими (3-4) параметрами. Классический пример: диаграмма, отображающая благосостояние граждан (по оси X), среднюю продолжительность жизни (по оси Y) и население (размер шарика) для нескольких стран.
Теперь наша задача - показать с помощью пузырьковой диаграммы развитие ситуации во времени, например, с 2000 по 2014 годы, т.е создать, по-сути, интерактивную анимацию:
Выглядит такая диаграмма весьма пафосно, но создается (если у вас Excel 2013-2016), буквально, за пару минут. Давайте по шагам.
Шаг 1. Готовим данные
Для построения нам потребуется таблица с данными по каждой стране, причем определенного вида:
Обратите внимание, что каждый год представляет собой отдельную строку с названием страны и значениями трех параметров (доход, продолжительность жизни, население). Последовательность столбцов и строк (сортировка) роли не играет.
Часто встречающийся вариант таблицы, где годы идут по столбцам для построения пузырьковых диаграмм, к сожалению, принципиально не подойдет:
Для преобразования такой таблицы в подходящий вид можно использовать макрос редизайна кросс-таблиц или готовый инструмент из надстройки PLEX.
Шаг 2. Подключаем надстройку Power View
Всю работу по построению такой интерактивной диаграммы возьмет на себя новая надстройка Power View из набора инструментов для бизнес-анализа (Business Intelligence = BI), который появился в Excel начиная с 2013 версии. Чтобы проверить, есть ли у вас такая надстройка и подключена ли она, зайдите в Файл - Параметры - Надстройки, выберите внизу окна в выпадающем списке Надстройки COM и нажмите кнопку Перейти (File - Options - Add-Ins - COM Add-Ins - Go) :
В открывшемся окне проверьте, чтобы стояла галочка напротив Power View.
В Excel 2013 после этого на вкладке Вставка (Insert) должна появиться соответствующая кнопка:
В Excel 2016 эту кнопку зачем-то убрали с ленты (даже при включенной галочке в списке COM-надстроек), поэтому ее придется добавить один раз вручную:
- Щелкните по ленте правой кнопкой мыши, выберите команду Настройка ленты (Customize Ribbon) .
- В левой части появившегося окна сверху выберите из выпадающего списка Все команды (All Commands) и найдите значок Power View.
- В правой половине выберите вкладку Вставка (Insert) и создайте в ней новую группу с помощью кнопки Создать группу (New Group) . Введите любое имя, например Power View.
- Выделите созданную группу и добавьте в нее из левой половины окна найденную кнопку с помощью кнопки Добавить (Add) в середине окна.
Шаг 3. Строим диаграмму
Если надстройка подключена, то построение самой диаграммы займет всего несколько секунд:
- Ставим активную ячейку в таблицу с данными и жмем на кнопку Power View на вкладке Вставка (Insert) - в нашу книгу добавится новый лист отчета Power View. В отличие от обычного листа Excel, на нем нет ячеек и он больше похож на слайд из Power Point. По-умолчанию, Excel построит на этом слайде что-то типа сводной по нашим данным. Справа должна появиться панель Поля Power View, где будут перечислены все столбцы (поля) из нашей таблицы.
- Снимите флажки со всех столбцов, кроме Страны и Среднего годового дохода - таблица, автоматически построенная на листе Power View, должна обновиться, отобразив только выбранные данные.
- На вкладке Конструктор (Design) нажмите кнопку Другая диаграмма - Точечная (Other Chart - Scatter) .
Вот и все - диаграмма готова!
Осталось ввести заголовок, запустить анимацию нажатием на кнопку Play в левом нижнем углу слайда и наслаждаться прогрессом (во всех смыслах).
Читайте также: