JAVA-сортировка массива — это процесс упорядочивания компонентов массива по убыванию или возрастанию, реализованный программой на языке программирования JAVA.
Общие сведения о массивах
Массив — это набор однотипных компонентов, объединенных одним именем. Массивы способны предоставить возможность удобно группировать информацию и организовать доступ к ней. Массивы делятся на следующие типы:
- Одномерные массивы.
- Двумерные массивы.
- Многомерные массивы.
Местоположение компонента в массиве задается индексом. В языке программирования Java задание позиции начального компонента массива должно начинаться с нуля.
Массив считается одномерным, если, для того чтобы задать расположения компонента в массиве, необходимо определить значение лишь одного индекса. Массив считается двумерным, если, для того чтобы задать расположение компонента в массиве необходимо указывать значения двух индексов.
Объемы информации, из которых могут состоять существующие сегодня базы данных и различные массивы, способны достигать огромных размеров, вплоть до десятков миллионов единиц. При работе с такими массивами данных основным параметром считается скорость отклика, то есть, временной интервал от момента формирования задачи информационного поиска, до момента разрешения этой проблемы. Обработка информационных данных может быть выполнена значительно быстрее, когда массив данных является отсортированным.
Сортировка является операцией размещения последовательной совокупности однотипных данных в заданном порядке в соответствии с определенными правилами. Наиболее важным параметром алгоритмов сортировки выступает скорость работы и оптимальный режим применения ресурсов памяти. Скорость работы или быстродействие сортировки определяется количеством операций сравнения и количеством операций перемещения элементов (обменов), которые исполняются при осуществлении алгоритма сортировки.
Как правило, эффективность алгоритмов сортировки должна определяться по уровню роста количества процедур сравнения. Относительно небольшие массивы данных можно целиком поместить в оперативной памяти компьютера. Это также позволяет обеспечить произвольный доступ к элементам сортировки. В этом варианте сортировка является внутренней. Но когда размеры массива данных становятся очень большими и оперативной памяти уже не хватает, то нужно использовать внешние носители, для того чтобы запомнить данные. В этом случае доступ к информационным элементам реализуется в последовательном режиме, и сортировка уже превращается во внешнюю.
JAVA-сортировка массива
Как говорилось выше, использование алгоритмов сортировки помогает упорядочить массивы Java. Сортировка чисел от наименьшего к большему или наоборот, а также задание лексикографического порядка являются примерами алгоритмов сортировки, которые способны упорядочить Java строки и числа.
Сортировка пузырьком является широко используемым алгоритмом, популярность которого объясняется его простотой, наглядностью и даже названием. Согласно этому алгоритму, следует выполнять просмотр массива и сравнивать каждую пару соседних компонентов. Если попадается пара компонентов, которые расположены не по порядку, то осуществляется обмен двух компонентов местами. Все компоненты будут считаться упорядоченными, когда очередная итерация будет пройдена без операции замены соседних компонентов.
Рассмотрим пример сортировки массива чисел от наименьшего к большему числу:
- 4 2 1 5 3. В этом массиве два первых компонента располагаются в неправильной очередности. Их следует поменять местами.
- 2 4 1 5 3. Теперь вторая пара компонентов массива также стоит неверно. Их нужно поменять местами.
- 2 1 4 5 3. Очередная пара компонентов расположена верно, поскольку четыре меньше пяти. Обмен местами не выполняется.
- 2 1 4 5 3. Следующая пара компонентов массива также требует обмена местами, что и следует выполнить.
- 2 1 4 3 5. Это итоговый результат после реализации одной итерации.
Для завершения данной сортировки потребуется еще одна итерация, а третья итерация будет пройдена уже без замен, что будет означать, что массив уже отсортирован.
Если посмотреть внимательно на данный пример, то можно увидеть, что алгоритм как бы смещает цифры вправо. В соответствии с поведением компонентов в массиве и была проведена аналогия с «пузырьками», которые как бы всплывают на «поверхность».
Рассмотрим реализацию данного алгоритма на языке Java. Функция должна войти в цикл while, в котором выполняется прохождение всего массива и осуществляется замена компонентов местами, если это необходимо. Изначально массив в алгоритме предполагается отсортированным, но когда реализуется первая замена, то это является доказательством обратного и, как следствие, выполняется запуск еще одной итерации. Выполнение цикла прекращается, если все пары компонентов в массиве будут пройдены без осуществления замен. Программа, реализующая этот алгоритм, представлена ниже.
Рисунок 1. Программа. Автор24 — интернет-биржа студенческих работ
Особо следует подчеркнуть, что необходимо очень четко формулировать условия обмена местами компонентов. К примеру, при условии a[i] >= a[i+1], то есть «больше или равно», алгоритм может войти в бесконечный цикл, поскольку для равной пары компонентов это условие остается true (верным), что повлечет за собой бесконечные замены.
Существует также определенная сложность со временем выполнения алгоритма. Рассмотрим самый худший вариант, согласно которому для массива, состоящего из n компонентов, необходимо осуществить n итераций. В программном варианте это означает, что цикл while необходимо будет исполнить максимально n раз. Каждая n-ая итерация по всему массиву (цикл for в коде) будет означать, что временная сложность в самом худшем варианте будет равняться $O(n ^ 2)$.
