Приведите примеры информации ,отсортированной: а) по алфавиту; б) в порядке убывания; в) в хронологической послед.
По алфавиту: телефонная книга.
В порядке убывания: таблица рекордов.
В хронологической посл. : учебник истории.
Остальные ответы
а) телефонная книга?
вы уверены
Похожие вопросы
Ваш браузер устарел
Мы постоянно добавляем новый функционал в основной интерфейс проекта. К сожалению, старые браузеры не в состоянии качественно работать с современными программными продуктами. Для корректной работы используйте последние версии браузеров Chrome, Mozilla Firefox, Opera, Microsoft Edge или установите браузер Atom.
Как выглядит информация отсортированная по алфавиту
Вопросы по покупке sales@onlyoffice.com
Запросы на партнерство partners@onlyoffice.com
Запросы от прессы press@onlyoffice.com
Следите за нашими новостями:
© Ascensio System SIA 2024. Все права защищены
© Ascensio System SIA 2024. Все права защищены
Не пропустите обновление!
Получайте последние новости ONLYOFFICE на ваш email
Имя не указано.
Email не указан.
На ваш адрес электронной почты отправлено сообщение с подтверждением.
В Справочном центре ONLYOFFICE используются файлы cookie для обеспечения максимального удобства работы пользователей. Продолжая использовать этот сайт, вы соглашаетесь с тем, что мы можем сохранять файлы cookie в вашем браузере.
Сортировка буквенной части составной (алфавитно-числовой) строки
Есть решение с разбором на подстроки. Заменой цифр на «» (replaceAll) и сортировкой полученных строк как элементов list. Как выстроить в том же порядке начальные данные? UPD: В данный момент функциональный кусок обработки токена (newString) выглядит примерно так:
newString = newString.replaceAll("\\d",""); list.add(newString); Collections.sort(list);
UPD-2: В конечном итоге реализовано с помощью конструкции: splitted — это начальный массив подстрок.
for (int i = 0; i < (splitted.length - 1); i++) < if (splitted[i].replaceAll("\\d", "").compareTo(splitted[i + 1].replaceAll("\\d", "")) >0) < temp = splitted[i]; splitted[i] = splitted[i + 1]; splitted[i + 1] = temp; >> Как правильно реализовать?
Великая тройка: алгоритмы сортировки, которые точно пригодятся на собеседовании
Да кто такой этот ваш Bubble Sort?! Валерий Жила доступно рассказал о базовых алгоритмах сортировки и сравнил их характеристики.
Фото: Getty Images / Brandon Bell
Редакция «Код» Skillbox Media
Онлайн-журнал для тех, кто влюблён в код и информационные технологии. Пишем для айтишников и об айтишниках.
Валерий Жила
Software engineer, разрабатывает системы управления городской инфраструктурой для мегаполисов по всему миру. Основная деятельность: backend, database engineering. Ведёт твиттер @ValeriiZhyla.
Ссылки
Сегодня я расскажу простым языком о Bubble Sort, Insertion Sort и Selection Sort. Я покажу, какие идеи лежат в основе этих сортировок и продемонстрирую их сильные и слабые стороны. Мы разберём алгоритмы по шагам, рассмотрим их простые версии и даже немного улучшим.
Дальнейший рассказ подразумевает, что вас не смущают такие фразы, как «сложность worst-case-алгоритма по времени равна O(n^2)». Иногда Time Complexity я буду называть «сложностью по времени», а Space Complexity — «сложностью по памяти».
Если вы новичок в теории алгоритмов, сначала прочитайте статью Валерия о Big O Notation. В ней он человеческим языком рассказал, что такое алгоритмическая сложность и как её считать.
На какие вопросы нужно ответить перед сортировкой массива
Давайте подумаем, на какие вопросы нужно ответить программисту, который собирается отсортировать элементы массива.
Вопрос первый. Отсортировать оригинальный массив или его копию?
Сортировка оригинала. Недостаток этого решения в том, что мы потеряем изначальный массив. Представляет ли он ценность — зависит от ситуации. Тем не менее это лишний побочный эффект (side effect) работы алгоритма.
Зато нам не придётся выделять память под копию массива. Иначе Space Complexity выросла бы до O(n). А так имеем O(1) памяти. Красота! Кроме того, массив не придётся копировать, а значит, мы сэкономим O(n) у Time Complexity.
Сортировка копии (out-of-place). Здесь всё наоборот: никаких сторонних эффектов, зато сложность алгоритма по памяти и времени вырастает до O(n). Забегая вперёд, скажу, что лишнее O(n) времени на копирование не так уж и страшно по сравнению со временем на саму сортировку, которая сожрёт намного больше. А вот дополнительные O(n) памяти — это серьёзный аргумент против out-of-place-алгоритмов.
Вопрос второй. Как поменять элементы массива местами?
Напишем функцию, которая эффективно переставляет два элемента местами по их индексам:
Обратите внимание: почти все элементы массива сместились в нужную сторону, а самый большой (9) оказался в крайней правой ячейке! На каждой итерации он менялся местами с соседом справа и «всплыл на поверхность».
Исполним наш код ещё несколько раз:
Всего за три прохода данные заметно упорядочились. Каждый виток гарантирует всплывание одного из элементов: на первом шаге число 9 встало на своё место, на втором — 8, а затем, по счастливой случайности, — сразу четыре элемента.
Сколько нужно сделать таких перестановок, чтобы гарантированно отсортировать массив? Если каждый проход выталкивает минимум один элемент, то через n проходов мы точно получим отсортированный массив! Даже через n — 1, потому что у крайнего правого элемента останется только один вариант размещения.
Пройдёмся по массиву несколько раз циклом из selection_sort() и посмотрим на состояние arr. Вот что мы получим:
Чтобы сохранять упорядоченные элементы в левой части массива arr, алгоритм использует барьер между отсортированной и неотсортированной частью. Этот барьер находится между элементами с индексами i и (i + 1).
В каждой итерации алгоритм ищет наименьшее значение в правой части (от i + 1 и до конца массива) и меняет его местами с элементом по индексу i. При i = 1 в отсортированной части массива будет только один элемент. При i = 2 — два.
Сделаем процесс чуть более наглядным. Добавим разделитель между элементами, по которым проходит граница между отсортированной и неотсортированной частями массива:
Обратите внимание: состояние arr показывается в конце каждой итерации. Первая строчка при i = 0, вторая при i = 1 и так далее.
Надеюсь, теперь идея Selection Sort кажется простой и естественной. Давайте взглянем на характеристики алгоритма.
С одной стороны, у такой реализации хорошая сложность по памяти O(1) за счёт использования левой части массива. С другой — поиск минимального элемента съедает O(n) времени и повторяется в каждом цикле (n раз). Поэтому мы получаем и Worst Case, и Best Case равные O(n^2), а это нехорошо.
Выходит, Bubble Sort быстрее, чем Selection Sort из-за Best Case O(n)? Тут как в известном анекдоте: есть один нюанс. В конце статьи мы ещё обсудим аспекты, которые не учитывает О-нотация.
Дополним нашу таблицу с характеристиками:
| Name | Bubble | Selection |
|---|---|---|
| Name | Bubble | Selection |
| Worst | O(n^2) | O(n^2) |
| Average | O(n^2) | O(n^2) |
| Best | O(n) | O(n^2) |
| Space | O(1) | O(1) |
Как работает Insertion Sort
Insertion Sort, она же сортировка вставками, очень похожа на Selection Sort. Я даже называю её «Selection Sort наоборот», потому что она действует по обратному принципу.
Напомню, что в Selection Sort мы искали наименьший элемент в правой части, переставляли его в конец левой и шли дальше. Самая дорогая операция в этом алгоритме — поиск наименьшего элемента.
В Insertion Sort мы тоже сохраняем упорядоченные элементы в исходном массиве. Только на этот раз из правой части берём первый попавшийся элемент и выбираем, куда его вставить в левой.
При этом левая часть массива всегда будет отсортирована. А это значит, что нам нужно лишь найти подходящее место, сдвинуть всех соседей справа на одну позицию правее и вставить новый элемент на освободившееся место.
Работа Insertion Sort немного напоминает толкучку в общественном транспорте. Боксёр-тяжеловес, который зайдёт в набитый трамвай, вероятно, спровоцирует движение всех пассажиров на полшага от выхода.
Рассмотрим пример такой вставки. У нас есть отсортированный массив из восьми чисел со свободной ячейкой в конце. Нужно добавить в этот массив число 5 на правильную позицию. Вот как будет выглядеть алгоритм:
Обратите внимание: справа от передвигаемого числа возникает его копия, а оригинал перезаписывается соседом слева на следующей итерации.
А вот как выглядит массив после всех сдвиганий:
Когда цикл дойдёт до 4, он остановится и запишет число 5 вместо «мусорной» шестёрки.
Теперь взглянем на заветный код Insertion Sort:
Нижняя граница производительности довольно привлекательна. Если массив изначально отсортирован, то ничего сдвигать не нужно! Сложность Best Case у такой сортировки составляет O(n).
Мы разобрали «Великую Тройку Сортировок», с которой неизбежно сталкивается любой, кто изучает алгоритмы. С чем я всех и поздравляю!
Что такое стабильность сортировки
Стабильным (устойчивым, stable) называется алгоритм сортировки, который не меняет порядок элементов с одинаковыми ключами относительно друг друга. Если мы сортируем числа, то стабильность особой роли не играет, а вот если сортируем объекты, то очень даже.
Допустим, нужно отсортировать по возрасту массив с записями о клиентах. Для наглядности возьмём максимально простой вид записей в формате [возраст : имя].
После стабильной сортировки Кузя гарантированно будет расположен выше Олега, потому что именно так расположены элементы с одинаковыми ключами в оригинальных данных.
В нестабильном варианте допускается второй сценарий:
Стабильность крайне важна, если мы планируем сортировать массив объектов по нескольким ключам. Например, сначала по возрасту, потом по размеру банковского счёта и затем по площади жилья. В таком случае нестабильный алгоритм испортит нам всю малину.
В нашей тройке стабильными являются Bubble Sort и Insertion Sort, а вот Selection Sort так и норовит перемешать элементы.
Дополним нашу таблицу характеристиками Selection Sort и строкой с показателями стабильности:
| Name | Bubble | Selection | Insertion |
|---|---|---|---|
| Name | Bubble | Selection | Insertion |
| Worst | O(n^2) | O(n^2) | O(n^2) |
| Average | O(n^2) | O(n^2) | O(n^2) |
| Best | O(n) | O(n^2) | O(n) |
| Space | O(1) | O(1) | O(1) |
| Stable | yes | no | yes |
Что не учитывает O(n)
Я обещал обсудить нюансы, которые не учитывает O-нотация. Пришло время перемывать косточки уже полюбившимся алгоритмам!
Посмотрим на почти идеально отсортированный массив. Почти — потому что самый большой элемент в нём стоит на первом месте:
Как поведут себя алгоритмы:
- Bubble Sort сработает великолепно. За n перестановок наибольший элемент «всплывёт» наверх.
- Insertion Sort тоже хорош в этом вопросе.
- Selection Sort со страшной расточительностью перелопатит весь массив и выдаст O(n^2) по времени.
Вывод: если данные почти отсортированы, то Bubble Sort и Insertion Sort — наши лучшие друзья.
Теперь подумаем о стоимости операций. В О-нотации об этом ничего не говорится, но на самом деле разные операции требуют разного количества ресурсов компьютера.
Например, прочитать значение в ячейке массива — элементарно. Перезаписать ячейку — вроде бы тоже просто, да вот только многопоточность, обновление значений в кэше процессора и другие факторы реального мира с этим не согласны. Поэтому операция swap() не так уж и проста, как кажется на первый взгляд.
А вот что у нас по количеству свопов:
- Bubble Sort просто монстр, который свопает без остановки. Количество операций записи здесь зашкаливает.
- Insertion Sort тоже не подарок — постоянное сдвигание элементов вправо до добра не доведёт.
- Selection Sort — конфетка! Всего n свопов в худшем случае. Очень экономичный алгоритм.
Вывод: если стоит задача сэкономить на операциях записи, то Selection Sort — лучший выбор.
Что касается памяти, то все три алгоритма в этом одинаково хороши. Они работают in-place и поэтому съедают O(1) памяти.
Отмечу, что алгоритмы сортировки можно улучшать. В основном с помощью особых структур данных. Например, Insertion Sort можно ускорить примерно в два раза, а также свести количество свопов к показателям Bubble Sort, если использовать не массив, а связный список. А Selection Sort можно сделать стабильным.
Что почитать и посмотреть
Код сортировок на разных языках программирования и видео с визуалиазцией можно найти на сайте geeksforgeeks.org:
На YouTube полно визуализаций алгоритмов сортировки, но я выделю это видео:
Отдельный мем в этой теме — венгерские танцы. Выглядит не только познавательно, но и очень забавно:)
Кажется, на этом тема простых сортировок исчерпана. Надеюсь, удалось всё разложить по полочкам и никого не запутать. В следующих статьях об алгоритмах разберу Merge Sort и Quick Sort и постараюсь залезть в материал поглубже.
Читайте также:
- Big O Notation: что это такое и как её посчитать
- GNU Emacs: как текстовый редактор из 1980-х учит программистов ценить свободное ПО
- Экспекто Питонум: 15 заклинаний на змеином языке