Сортировка в Эксель – это встроенная функция, с помощью которой пользователь сможет расположить данные в столбцах на листе в удобном порядке для их последующего анализа.
Вы сможете отсортировать информацию в алфавитном порядке, по возрастанию или убыванию значений, по дате или по значкам, по цвету текста или ячейки. Именно об этом и пойдет речь в данной статье.
Здесь все достаточно просто. Для примера возьмем следующую таблицу. Сделаем в ней сортировку данных по столбцу С . Для этого выделяем его и на вкладке «Главная» кликаем на кнопочку «Сортировка и фильтр» . В следующем меню выберите или «… от минимального к максимальному» , или «… от максимального к минимальному» . Выберем второй вариант.
Теперь у нас данные в С размещены в порядке убывания.
У меня столбец С расположен между двумя другими, которые заполнены данными. В этом случае, Excel считает, что выделенный столбец – это часть таблицы (и считает правильно). В результате появилось следующее сообщение. Поскольку мне нужно сделать сортировку конкретно для Класса, выделяю маркером пункт «… в пределах указанного выделения» и нажимаю «Сортировка» .
Она делается по тому же принципу, как было описано выше. Выделяем нужный диапазон, и нажимаем кнопочку «Сортировка и фильтр» . В выпадающем меню пункты изменились. Выберите или от «А до Я» , или от «Я до А» .
Список имен в примере отсортирован по алфавиту.
Чтобы отсортировать даты в Эксель, сначала обратите внимание, какой формат установлен для тех ячеек, в которых они записаны. Выделите их и на вкладке «Главная» посмотрите на группу «Число» . Лучше всего подойдет или формат «Дата» , краткий или длинный, или «(все форматы)» – дата может быть записана различными способами: ДД.ММ.ГГГГ, ДД.МММ, МММ.ГГ.
Этот момент очень важен, так как в противном случае, даты могут быть отсортированы просто по возрастанию первых двух чисел, или по месяцам в алфавитном порядке.
После этого выделяем нужный диапазон ячеек и жмем на кнопочку «Сортировка и фильтр» . В меню можно выбрать или «от старых к новым» , или «от новых к старым» .
Этот способ можно использовать, когда в таблице Excel текст в ячейках или сами ячейки закрашены в различный цвет. Для примера возьмем столбец из чисел, закрашенных разными цветами. Отсортируем его, чтобы сначала шли числа, закрашенные в красный, затем зеленый и черный цвет.
Выделяем весь диапазон, кликаем на кнопочку «Сортировка и фильтр» и выбираем из меню «Настраиваемая…» .
В следующем окне, уберите галочку с поля , если Вы выделили их без верхней строки, которая является шапкой таблицы. Затем выбираем столбец, по которому будем сортировать, в примере это «I» . В разделе «Сортировка» из выпадающего списка выбираем «Цвет шрифта» . В разделе порядок выбираем «красный цвет» – «Сверху» . Это мы отсортировали числа красного цвета.
Теперь нужно, чтобы в столбце шли числа зеленого цвета. Нажмите на кнопочку «Добавить уровень» . Все настройки те же, только выберите «зеленый цвет» . Нажмите «ОК» .
Наш столбец отсортирован следующим образом.
Как видите, числа идут не по порядку. Давайте отсортируем числа в порядке возрастания. Выделяем столбец, нажимаем «Сортировка и фильтр» – «Настраиваемая …» . В открывшемся окне нажмите на кнопку «Добавить уровень» . Столбец остается «I» , в следующем поле выбираем по «Значению» , порядок «По возрастанию» . Нажмите «ОК» .
Теперь наш столбец отсортирован и по цвету текста и в порядке возрастания данных.
Аналогичным образом сортируются данные и по цвету ячейки, только в разделе «Сортировка» выбирайте из списка «Цвет ячейки» .
Если у Вас есть таблица, в которой нужно выполнить сортировку сразу по нескольким столбцам, делаем следующее. Выделяем весь диапазон ячеек таблицы вместе с шапкой. Кликаем по кнопочке «Сортировка и фильтр» и выбираем «Настраиваемая …» .
Давайте отсортируем класс в порядке возрастания, и таким же образом средний бал.
В окне сортировки ставим галочку в поле «Мои данные содержат заголовки» . В разделе «Столбец» выбираем из списка «Класс» , сортировка по «Значению» , а порядок «По возрастанию» .
Чтобы сделать все тоже самое по среднему балу, нажмите на кнопочку «Добавить уровень» . В разделе «Столбец» выбираем «Средн.бал» . Нажмите «ОК» .
Данные в таблице отсортированы.
Теперь в столбце «Имя» закрасим ячейки с мальчиками в синий цвет, ячейки с девочками в розовый. Чтобы не делать это для каждой ячейки в отдельности, прочтите статью, как выделить ячейки в Excel – в ней написано, как выделить несмежные ячейки.
Выполним сортировку этого столбца по цвету ячейки: сначала будут девочки, потом мальчики. Снова выделяем всю таблицу, жмем «Сортировка» – «Настраиваемая …» .
В открывшемся окне уже есть два уровня, которые мы сделали раньше. Эти уровни имеют приоритет – у первого самый большой, у второго меньше и так далее. То есть, если мы хотим, чтобы сначала выполнилась сортировка данных в таблице девочки/мальчики, затем по классу, а затем по среднему балу – нужно в таком порядке и расставить уровни.
Нажимаем на кнопку «Добавить уровень» . В разделе «Столбец» выбираем «Имя» , сортировка – «Цвет ячейки» , порядок – «розовый» , «Сверху» .
Теперь с помощью стрелочек перемещаем данную строку наверх списка. Нажмите «ОК» .
Таблица с отсортированными данными выглядит следующим образом.
В этой статье я покажу Вам, как в Excel выполнить сортировку данных по нескольким столбцам, по заголовкам столбцов в алфавитном порядке и по значениям в любой строке. Вы также научитесь осуществлять сортировку данных нестандартными способами, когда сортировка в алфавитном порядке или по значению чисел не применима.
Думаю, всем известно, как выполнить сортировку по столбцу в алфавитном порядке или по возрастанию / убыванию. Это делается одним нажатием кнопки А-Я (A-Z) и Я-А (Z-A) в разделе Редактирование (Editing) на вкладке Главная (Home) либо в разделе Сортировка и фильтр (Sort & Filter) на вкладке Данные (Data):
Однако, сортировка в Excel имеет гораздо больше настраиваемых параметров и режимов работы, которые не так очевидны, но могут оказаться очень удобны:
Я покажу Вам, как в Excel сортировать данные по двум или более столбцам. Работа инструмента показана на примере Excel 2010 – именно эта версия установлена на моём компьютере. Если Вы работаете в другой версии приложения, никаких затруднений возникнуть не должно, поскольку сортировка в Excel 2007 и Excel 2013 работает практически так же. Разницу можно заметить только в расцветке диалоговых окон и форме кнопок. Итак, приступим…
Сортировать данные по нескольким столбцам в Excel оказалось совсем не сложно, правда? Однако, в диалоговом окне Сортировка (Sort) кроется значительно больше возможностей. Далее в этой статье я покажу, как сортировать по строке, а не по столбцу, и как упорядочить данные на листе в алфавитном порядке по заголовкам столбцов. Вы также научитесь выполнять сортировку данных нестандартными способами, когда сортировка в алфавитном порядке или по значению чисел не применима.
Я полагаю, что в 90% случаев сортировка данных в Excel выполняется по значению в одном или нескольких столбцах. Однако, иногда встречаются не такие простые наборы данных, которые нужно упорядочить по строке (горизонтально), то есть изменить порядок столбцов слева направо, основываясь на заголовках столбцов или на значениях в определённой строке.
Вот список фотокамер, предоставленный региональным представителем или скачанный из интернета. Список содержит разнообразные данные о функциях, характеристиках и ценах и выглядит примерно так:
Нам нужно отсортировать этот список фотокамер по наиболее важным для нас параметрам. Для примера первым делом выполним сортировку по названию модели:
В результате сортировки у Вас должно получиться что-то вроде этого:
В рассмотренном нами примере сортировка по заголовкам столбцов не имеет серьёзной практической ценности и сделана только для того, чтобы продемонстрировать Вам, как это работает. Таким же образом мы можем сделать сортировку нашего списка фотокамер по строке, в которой указаны размеры, разрешение, тип сенсора или по любому другому параметру, который сочтём более важным. Сделаем ещё одну сортировку, на этот раз по цене.
Наша задача – повторить описанные выше шаги 1 – 3. Затем на шаге 4 вместо строки 1 выбираем строку 4 , в которой указаны розничные цены (Retail Price). В результате сортировки таблица будет выглядеть вот так:
Обратите внимание, что отсортированы оказались данные не только в выбранной строке. Целые столбцы меняются местами, но данные не перемешиваются. Другими словами, на снимке экрана выше представлен список фотокамер, расставленный в порядке от самых дешёвых до самых дорогих.
Надеюсь, теперь стало ясно, как работает сортировка по строке в Excel. Но что если наши данные должны быть упорядочены не по алфавиту и не по возрастанию / убыванию?
Если нужно упорядочить данные в каком-то особом порядке (не по алфавиту), то можно воспользоваться встроенными в Excel настраиваемыми списками или создать свой собственный. При помощи встроенных настраиваемых списков Вы можете сортировать, к примеру, дни недели или месяцы в году. Microsoft Excel предлагает два типа таких готовых списков – с сокращёнными и с полными названиями.
Предположим, у нас есть список еженедельных дел по дому, и мы хотим упорядочить их по дню недели или по важности.
Готово! Теперь домашние дела упорядочены по дням недели:
Замечание: Если Вы планируете вносить изменения в эти данные, помните о том, что добавленные новые или изменённые существующие данные не будут отсортированы автоматически. Чтобы повторить сортировку, нажмите кнопку Повторить (Reapply) в разделе Сортировка и фильтр (Sort & Filter) на вкладке Данные (Data).
Как видите, сортировка данных в Excel по настраиваемому списку – задача вовсе не сложная. Ещё один приём, которому мы должны научиться – сортировка данных по собственному настраиваемому списку.
В нашей таблице есть столбец Priority – в нём указаны приоритеты задач. Чтобы упорядочить с его помощью еженедельные задачи от более важных к менее важным, выполним следующие действия.
Повторите шаги 1 и 2 из предыдущего примера. Когда откроется диалоговое окно Списки (Custom Lists), в одноимённом столбце слева нажмите НОВЫЙ СПИСОК (NEW LIST) и заполните нужными значениями поле Элементы списка (List entries). Внимательно введите элементы Вашего списка именно в том порядке, в котором они должны быть расположены в результате сортировки.
Нажмите Добавить (Add), и созданный Вами список будет добавлен к уже существующим. Далее нажмите ОК .
Вот так выглядит наш список домашних дел, упорядоченных по важности:
При выборке данных бывает важно получить их в определенном упорядоченном виде. Сортировка может быть выполнена по любым полям с любым типом данных. Это может быть сортировка по возрастанию или убыванию для числовых полей. Для символьных (текстовых) полей это может быть сортировка в алфавитном порядке, хотя по сути, она так же является сортировкой по возрастанию или убыванию. Она так же может быть выполнена в любых направлениях – от А, до Я, и наоборот от Я, до А.
Суть процесса сортировки заключается к приведению последовательности к определенному порядку. Подробней о сортировки можно узнать в статье "Алгоритмы сортировки" Например, сортировка произвольной числовой последовательности по возрастанию:
2, 4, 1, 5, 9
должна привести к упорядоченной последовательности:
1, 2, 4, 5, 6
Аналогично, при сортировке по возрастанию строковых значений:
Иванов Иван, Петров Петр, Иванов Андрей
результат должен быть:
Иванов Андрей, Иванов Иван, Петров Петр
Здесь строка "Иванов Андрей" перешла в начало, так как сравнение строк производится посимвольно. Обе строки начинаются одинаковых символов "Иванов ". Так как символ "А" в слове "Андрей" идет раньше в алфавите, чем символ "И" в слове "Иван", то эта строка будет поставлена раньше.
Для выполнения сортировки в строку запроса нужно добавить команду ORDER BY. После этой команды указывается поле, по которому производится сортировка.
Для примеров используем таблицу товаров goods:
| num
(номер товара) | title
(название) | price
(цена) |
| 1 | Мандарин | 50 |
| 2 | Арбуз | 120 |
| 3 | Ананас | 80 |
| 4 | Банан | 40 |
Данные здесь уже упорядочены по столбцу "num". Теперь, построим запрос, который выведет таблицу с товарами, упорядоченными в алфавитном порядке:
SELECT * FROM goods ORDER BY title
SELECT * FROM goods – указывает выбрать все поля из таблицы goods;
ORDER BY – команда сортировки;
title – столбец, по которому будет выполняться сортировка.
Результат выполнения такого запроса следующий:
| num | title | price |
| 3 | Ананас | 80 |
| 2 | Арбуз | 120 |
| 4 | Банан | 40 |
| 1 | Мандарин | 50 |
Так же можно выполнить сортировку для любого из полей таблицы.
По умолчанию, команда ORDER BY выполняет сортировку по возрастанию. Чтобы управлять направлением сортировки вручную, после имени столбца указывается ключевое слово ASC (по возрастанию) или DESC (по убыванию). Таким образом, чтобы вывести нашу таблицу в порядке убывания цен, нужно задать запрос так:
SELECT * FROM goods ORDER BY price DESC
Сортировка по возрастанию цены будет:
SELECT * FROM goods ORDER BY price ASC
SQL допускает сортировку сразу по нескольким полям. Для этого после команды ORDER BY необходимые поля указываются через запятую. Порядок в результате запроса будет настраиваться в той же очередности, в которой указаны поля сортировки.
| column1 | column2 | column3 |
| 3 | 1 | c |
| 1 | 3 | c |
| 2 | 2 | b |
| 2 | 1 | b |
| 1 | 2 | a |
| 1 | 3 | a |
| 3 | 4 | a |
Отсортируем таблицу по следующим правилам:
SELECT * FROM mytable ORDER BY column1 ASC, column2 DESC, column3 ASC
Т.е. первый столбец по возрастанию, второй по убыванию, третий опять по возрастанию. Запрос упорядочит строки по первому столбцу, затем, не разрушая первого правила, по второму столбцу. Затем, так же, не нарушая имеющихся правил, по третьему. В результате получится такой набор данных:
| column1 | column2 | column3 |
| 1 | 3 | a |
| 1 | 3 | c |
| 1 | 2 | a |
| 2 | 2 | b |
| 2 | 1 | b |
| 3 | 1 | a |
| 3 | 1 | c |
Сортировка строк чаще всего проводится вместе с условием на выборку данных. Команда ORDER BY ставится после условия выборки WHERE. Например, выбираем товары с ценой меньше 100 рублей, упорядочив по названию в алфавитном порядке:
SELECT * FROM goods WHERE price 100 ORDER BY price ASC
Привет, уважаемые читатели. Каким образом выполняется сортировка списка в ? Конечно, можно это сделать в ручную, перетаскивая один за другим. Удобно? Не думаю. Давайте я вам расскажу способ по лучше.
Пример своей работы я буду показывать на примере Word 2013, но этот способ подойдет и к версии Word 2010 и 2007.
Для демонстрации сортировки по возрастанию в Word я возьму небольшой список с именами.
Прежде, чем приступить к делу, необходимо выделить его левой кнопкой мыши. Затем, на вкладке «Главная » в разделе «Абзац » есть специальная кнопка. Какая? Посмотрите на гифке ниже.
В окне «Сортировка текста » можно выбрать Тип данных: текст, число или дата; а также выбрать способ: по возрастанию или убыванию. Я выбрал по возрастанию и тип текст.
Кстати, если нажать на кнопку «Параметры », то можно настроить дополнительные параметры сортировки в Ворде.
Теперь, чтобы завершить наше дело, нужно нажать на кнопку «ОК ». После этого у нас получился список, в котором имена расположены от А до Я.
Если нужно выполнить сортировку в таблице Word, то принцип такой же. Выделяете столбец и делаете те же самые действия. А если у вас цифры, то укажите в типе Числа .
В общем, это все. Даже если нужно отсортировать в Word 2010 по алфавиту, в этом нет ничего сложного, ведь интерфейсы похожи.
Создадим массив, в котором после завершения алгоритма будет лежать ответ. Будем поочередно вставлять элементы из исходного массива так, чтобы элементы в массиве-ответе всегда были отсортированы. Асимптотика в среднем и худшем случае – O(n 2), в лучшем – O(n). Реализовывать алгоритм удобнее по-другому (создавать новый массив и реально что-то вставлять в него относительно сложно): просто сделаем так, чтобы отсортирован был некоторый префикс исходного массива, вместо вставки будем менять текущий элемент с предыдущим, пока они стоят в неправильном порядке.Реализация:
void insertionsort(int* l, int* r) { for (int *i = l + 1; i < r; i++) { int* j = i; while (j > l && *(j - 1) > *j) { swap(*(j - 1), *j); j--; } } }
Несколько полезных ссылок:
Реализации:
void shellsort(int* l, int* r) { int sz = r - l; int step = sz / 2; while (step > < r; i++) { int *j = i; int *diff = j - step; while (diff >= l && *diff > *j) { swap(*diff, *j); j = diff; diff = j - step; } } step /= 2; } } void shellsorthib(int* l, int* r) { int sz = r - l; if (sz <= 1) return; int step = 1; while (step < sz) step <<= 1; step >>= 1; step--; while (step >= 1) { for (int *i = l + step; i < r; i++) { int *j = i; int *diff = j - step; while (diff >= l && *diff > *j) { swap(*diff, *j); j = diff; diff = j - step; } } step /= 2; } } int steps; void shellsortsedgwick(int* l, int* r) { int sz = r - l; steps = 1; int q = 1; while (steps * 3 < sz) { if (q % 2 == 0) steps[q] = 9 * (1 << q) - 9 * (1 << (q / 2)) + 1; else steps[q] = 8 * (1 << q) - 6 * (1 << ((q + 1) / 2)) + 1; q++; } q--; for (; q > < r; i++) { int *j = i; int *diff = j - step; while (diff >= l && *diff > *j) { swap(*diff, *j); j = diff; diff = j - step; } } } } void shellsortpratt(int* l, int* r) { int sz = r - l; steps = 1; int cur = 1, q = 1; for (int i = 1; i < sz; i++) { int cur = 1 << i; if (cur > sz / 2) break; for (int j = 1; j < sz; j++) { cur *= 3; if (cur > sz / 2) break; steps = cur; } } insertionsort(steps, steps + q); q--; for (; q >= 0; q--) { int step = steps[q]; for (int *i = l + step; i < r; i++) { int *j = i; int *diff = j - step; while (diff >= l && *diff > *j) { swap(*diff, *j); j = diff; diff = j - step; } } } } void myshell1(int* l, int* r) { int sz = r - l, q = 1; steps = 1; while (steps < sz) { int s = steps; steps = s * 4 + s / 4; } q--; for (; q >= 0; q--) { int step = steps[q]; for (int *i = l + step; i < r; i++) { int *j = i; int *diff = j - step; while (diff >= l && *diff > *j) { swap(*diff, *j); j = diff; diff = j - step; } } } } void myshell2(int* l, int* r) { int sz = r - l, q = 1; steps = 1; while (steps < sz) { int s = steps; steps = s * 3 + s / 3; } q--; for (; q >= 0; q--) { int step = steps[q]; for (int *i = l + step; i < r; i++) { int *j = i; int *diff = j - step; while (diff >= l && *diff > *j) { swap(*diff, *j); j = diff; diff = j - step; } } } } void myshell3(int* l, int* r) { int sz = r - l, q = 1; steps = 1; while (steps < sz) { int s = steps; steps = s * 4 - s / 5; } q--; for (; q >= 0; q--) { int step = steps[q]; for (int *i = l + step; i < r; i++) { int *j = i; int *diff = j - step; while (diff >= l && *diff > *j) { swap(*diff, *j); j = diff; diff = j - step; } } } }
Реализация:
void treesort(int* l, int* r) {
multiset
Реализация:
void gnomesort(int* l, int* r) { int *i = l; while (i < r) { if (i == l || *(i - 1) <= *i) i++; else swap(*(i - 1), *i), i--; } }
Реализация:
void selectionsort(int* l, int* r) { for (int *i = l; i < r; i++) { int minz = *i, *ind = i; for (int *j = i + 1; j < r; j++) { if (*j < minz) minz = *j, ind = j; } swap(*i, *ind); } }
Реализация:
template
Реализация:
void quicksort(int* l, int* r) { if (r - l <= 1) return; int z = *(l + (r - l) / 2); int* ll = l, *rr = r - 1; while (ll <= rr) { while (*ll < z) ll++; while (*rr > z) rr--; if (ll <= rr) { swap(*ll, *rr); ll++; rr--; } } if (l < rr) quicksort(l, rr + 1); if (ll < r) quicksort(ll, r); } void quickinssort(int* l, int* r) { if (r - l <= 32) { insertionsort(l, r); return; } int z = *(l + (r - l) / 2); int* ll = l, *rr = r - 1; while (ll <= rr) { while (*ll < z) ll++; while (*rr > z) rr--; if (ll <= rr) { swap(*ll, *rr); ll++; rr--; } } if (l < rr) quickinssort(l, rr + 1); if (ll < r) quickinssort(ll, r); }
Реализация:
void merge(int* l, int* m, int* r, int* temp) { int *cl = l, *cr = m, cur = 0; while (cl < m && cr < r) { if (*cl < *cr) temp = *cl, cl++; else temp = *cr, cr++; } while (cl < m) temp = *cl, cl++; while (cr < r) temp = *cr, cr++; cur = 0; for (int* i = l; i < r; i++) *i = temp; } void _mergesort(int* l, int* r, int* temp) { if (r - l <= 1) return; int *m = l + (r - l) / 2; _mergesort(l, m, temp); _mergesort(m, r, temp); merge(l, m, r, temp); } void mergesort(int* l, int* r) { int* temp = new int; _mergesort(l, r, temp); delete temp; } void _mergeinssort(int* l, int* r, int* temp) { if (r - l <= 32) { insertionsort(l, r); return; } int *m = l + (r - l) / 2; _mergeinssort(l, m, temp); _mergeinssort(m, r, temp); merge(l, m, r, temp); } void mergeinssort(int* l, int* r) { int* temp = new int; _mergeinssort(l, r, temp); delete temp; }
1) Не будем создавать новых массивов. Для этого воспользуемся техникой сортировки подсчетом – подсчитаем количество элементов в каждом блоке, префиксные суммы и, таким образом, позицию каждого элемента в массиве.
2) Не будем запускаться из пустых блоков. Занесем индексы непустых блоков в отдельный массив и запустимся только от них.
3) Проверим, отсортирован ли массив. Это не ухудшит время работы, так как все равно нужно сделать проход с целью нахождения минимума и максимума, однако позволит алгоритму ускориться на частично отсортированных данных, ведь элементы вставляются в новые блоки в том же порядке, что и в исходном массиве.
4) Поскольку алгоритм получился довольно громоздким, при небольшом количестве элементов он крайне неэффективен. До такой степени, что переход на сортировку вставками ускоряет работу примерно в 10 раз.
Осталось только понять, какое количество блоков нужно выбрать. На рандомизированных тестах мне удалось получить следующую оценку: 1500 блоков для 10 7 элементов и 3000 для 10 8 . Подобрать формулу не удалось – время работы ухудшалось в несколько раз.
Реализация:
void _newbucketsort(int* l, int* r, int* temp) { if (r - l <= 64) { insertionsort(l, r); return; } int minz = *l, maxz = *l; bool is_sorted = true; for (int *i = l + 1; i < r; i++) { minz = min(minz, *i); maxz = max(maxz, *i); if (*i < *(i - 1)) is_sorted = false; } if (is_sorted) return; int diff = maxz - minz + 1; int numbuckets; if (r - l <= 1e7) numbuckets = 1500; else numbuckets = 3000; int range = (diff + numbuckets - 1) / numbuckets; int* cnt = new int; for (int i = 0; i <= numbuckets; i++) cnt[i] = 0; int cur = 0; for (int* i = l; i < r; i++) { temp = *i; int ind = (*i - minz) / range; cnt++; } int sz = 0; for (int i = 1; i <= numbuckets; i++) if (cnt[i]) sz++; int* run = new int; cur = 0; for (int i = 1; i <= numbuckets; i++) if (cnt[i]) run = i - 1; for (int i = 1; i <= numbuckets; i++) cnt[i] += cnt; cur = 0; for (int *i = l; i < r; i++) { int ind = (temp - minz) / range; *(l + cnt) = temp; cur++; cnt++; } for (int i = 0; i < sz; i++) { int r = run[i]; if (r != 0) _newbucketsort(l + cnt, l + cnt[r], temp); else _newbucketsort(l, l + cnt[r], temp); } delete run; delete cnt; } void newbucketsort(int* l, int* r) { int *temp = new int; _newbucketsort(l, r, temp); delete temp; }
Реализация:
int digit(int n, int k, int N, int M) { return (n >> (N * k) & (M - 1)); } void _radixsort(int* l, int* r, int N) { int k = (32 + N - 1) / N; int M = 1 << N; int sz = r - l; int* b = new int; int* c = new int[M]; for (int i = 0; i < k; i++) { for (int j = 0; j < M; j++) c[j] = 0; for (int* j = l; j < r; j++) c++; for (int j = 1; j < M; j++) c[j] += c; for (int* j = r - 1; j >= l; j--) b[--c] = *j; int cur = 0; for (int* j = l; j < r; j++) *j = b; } delete b; delete c; } void radixsort(int* l, int* r) { _radixsort(l, r, 8); }
Реализация:
void _radixsortmsd(int* l, int* r, int N, int d, int* temp) { if (d == -1) return; if (r - l <= 32) { insertionsort(l, r); return; } int M = 1 << N; int* cnt = new int; for (int i = 0; i <= M; i++) cnt[i] = 0; int cur = 0; for (int* i = l; i < r; i++) { temp = *i; cnt++; } int sz = 0; for (int i = 1; i <= M; i++) if (cnt[i]) sz++; int* run = new int; cur = 0; for (int i = 1; i <= M; i++) if (cnt[i]) run = i - 1; for (int i = 1; i <= M; i++) cnt[i] += cnt; cur = 0; for (int *i = l; i < r; i++) { int ind = digit(temp, d, N, M); *(l + cnt) = temp; cur++; cnt++; } for (int i = 0; i < sz; i++) { int r = run[i]; if (r != 0) _radixsortmsd(l + cnt, l + cnt[r], N, d - 1, temp); else _radixsortmsd(l, l + cnt[r], N, d - 1, temp); } delete run; delete cnt; } void radixsortmsd(int* l, int* r) { int* temp = new int; _radixsortmsd(l, r, 8, 3, temp); delete temp; }
Реализация:
void bitseqsort(int* l, int* r, bool inv) { if (r - l <= 1) return; int *m = l + (r - l) / 2; for (int *i = l, *j = m; i < m && j < r; i++, j++) { if (inv ^ (*i > *j)) swap(*i, *j); } bitseqsort(l, m, inv); bitseqsort(m, r, inv); } void makebitonic(int* l, int* r) { if (r - l <= 1) return; int *m = l + (r - l) / 2; makebitonic(l, m); bitseqsort(l, m, 0); makebitonic(m, r); bitseqsort(m, r, 1); } void bitonicsort(int* l, int* r) { int n = 1; int inf = *max_element(l, r) + 1; while (n < r - l) n *= 2; int* a = new int[n]; int cur = 0; for (int *i = l; i < r; i++) a = *i; while (cur < n) a = inf; makebitonic(a, a + n); bitseqsort(a, a + n, 0); cur = 0; for (int *i = l; i < r; i++) *i = a; delete a; }
Подробнее timsort описан здесь:
Реализация:
void _timsort(int* l, int* r, int* temp) {
int sz = r - l;
if (sz <= 64) {
insertionsort(l, r);
return;
}
int minrun = sz, f = 0;
while (minrun >= 64) {
f |= minrun & 1;
minrun >>= 1;
}
minrun += f;
int* cur = l;
stack
Поскольку картинок очень много, они скрыты спойлерами. Немного комментариев по поводу обозначений. Сортировки названы так, как выше, если это сортировка Шелла, то в скобочках указан автор последовательности, к названиям сортировок, переходящих на сортировку вставками, приписано Ins (для компактности). В диаграммах у второй группы тестов обозначена возможная длина отсортированных подмассивов, у третьей группы - количество свопов, у четвертой - количество замен. Общий результат рассчитывался как среднее по четырем группам.
Таблицы
Таблицы
Таблицы
Таблицы
Таблицы
За счет своего абсолютного безразличия к массиву, сортировка выбором, работавшая быстрее всех на случайных данных, все же проиграла сортировке вставками. Гномья сортировка оказалась заметно хуже последней, из-за чего ее практическое применение сомнительно. Шейкерная и пузырьковая сортировки оказались медленнее всех.
Таблицы, 1е6 элементов
Таблицы, 1е7 элементов
Таблицы, 1е6 элементов
Таблицы, 1е7 элементов
Таблицы, 1е6 элементов
Таблицы, 1е7 элементов
Таблицы, 1е6 элементов
Таблицы, 1е7 элементов
Таблицы, 1е6 элементов
Таблицы, 1е7 элементов
Убедительное первое место заняла сортировка Шелла по Хиббарду, не уступив ни в одной промежуточной группе. Возможно, стоило ее отправить в первую группу сортировок, но… она слишком слаба для этого, да и тогда почти никого не было бы в группе. Битонная сортировка довольно уверенно заняла второе место. Третье место при миллионе элементах заняла другая сортировка Шелла, а при десяти миллионах сортировка деревом (асимптотика сказалась). Стоит обратить внимание, что при десятикратном увеличении размера входных данных все алгоритмы, кроме древесной сортировки, замедлились почти в 20 раз, а последняя всего лишь в 13.
Таблицы, 1е7 элементов
Таблицы, 1е8 элементов
Таблицы, 1е7 элементов
Таблицы, 1е8 элементов
