Java sorting array algorithm

Алгоритмы сортировки в теории и на практике

Сортировка — один из базовых видов активности или действий, выполняемых над предметами. Ещё в детсве детей учат сортировать, развивая мышление. Компьютеры и программы — тоже не исключение. Существует огромное множество алгоритмов. Предлагаю посмотреть, какие есть и как они работают. Кроме того, вдруг однажды вас спросят об одном из них на собеседовании?

Вступление

Сортировка элементов — одна из категорий алгоритмов, к которым разработчик должен привыкнуть. Если когда-то, когда я учился, информатика не воспринималась так серьёзно, сейчас уже в школе должны уметь реализовывать алгоритмы сортировки и понимать их. Базовые алгоритмы, самые простые, реализованы при помощи цикла for . Естественно, чтобы отсортировать коллекцию элементов,например, массив, нужно по этой коллекции как-то пройти. Например:

 int[] array = ; for (int i = 0; i

Что можно сказать об этом участке кода? Мы имеем цикл, в котором меняем значение индекса ( int i ) с 0 до последнего элемента в массиве. Фактически, мы просто берём каждый элемент в массиве и печатаем его содержимое. Чем больше элементов в массиве, тем дольше будет выполняться код. То есть, если n — количество элементов, при n=10 программа будет выполняться дольше, чем при n=5, в 2 раза. Когда в нашей программе есть один цикл, время выполнения растёт линейно: чем больше элементов, тем дольше выполнение. Получается, что алгоритм кода выше работает за линейное время (n). В таких случаях говорят, что «сложность алгоритма» равна O(n). Это обозначение ещё называют «большое О» или «асимптотическое поведение». Но можно запомнить просто «сложность алгоритма».

Простейшая сортировка (Bubble Sort)

Итак, мы имеем массив и можем по нему итерироваться. Отлично. Давайте попробуем теперь его отсортировать по возрастанию. Что это значит для нас? Это значит, что имея два элемента (например, a=6, b=5), мы должны переставить местами a и b, если a больше чем b (если a > b). Что для нас это значит при работе с коллекцией по индексу (как в случае с массивом)? Это значит, что если элемент с индексом а больше, чем элемент с индексом b, (array[a] > array[b]), такие элементы надо поменять местами. Перемену мест часто называют swap. Существуют различные способы перемены мест. Но мы используем простой, понятный и легко запоминаемый код:

 private void swap(int[] array, int ind1, int ind2)

 int[] array = ; System.out.println(Arrays.toString(array)); for (int i = 1; i < array.length; i++) < if (array[i] < array[i - 1]) < swap(array, i, i-1); >> System.out.println(Arrays.toString(array)); 

Как мы видим, элементы действительно поменялись местами. Мы начали с одного элемента, т.к. если массив будет всего из одного элемента, выражение 1 < 1 не вернёт true и тем самым мы обезопасим себя от случаев из массива в один элемент или вовсе без них, а код будет выглядеть лучше. Но наш итоговый массив не отсортирован всё равно, т.к. за один проход не удаётся всех отсортировать. Придётся добавить ещё цикл, в котором мы будем выполнять проходы один за одним до тех пор, пока не получим отсортированный массив:

 int[] array = ; System.out.println(Arrays.toString(array)); boolean needIteration = true; while (needIteration) < needIteration = false; for (int i = 1; i < array.length; i++) < if (array[i] < array[i - 1]) < swap(array, i, i-1); needIteration = true; >> > System.out.println(Arrays.toString(array)); 

Сортировка выбором (Selection Sort)

Другая сортировка — сортировка выбором. Она также имеет квадратичную сложность, но об этом чуть позже. Итак, идея простая. Каждый проход выбирать самый минимальный элемент и смещать его в начало. При этом каждый новый проход начинать сдвигаясь вправо, то есть первый проход — с первого элемента, второй проход — со второго. Выглядеть это будет следующим образом:

 int[] array = ; System.out.println(Arrays.toString(array)); for (int left = 0; left < array.length; left++) < int minInd = left; for (int i = left; i < array.length; i++) < if (array[i] < array[minInd]) < minInd = i; >> swap(array, left, minInd); > System.out.println(Arrays.toString(array)); 

Сортировка вставками (Insertion Sort)

Сортировка вставками тоже имеет квадратичную сложность, так как у нас опять цикл в цикле. В чём отличие от сортировки выбором? Данная сортировка является «устойчивой». Это значит, что одинаковые элементы не изменят свой порядок. Одинаковые с точки зрения характеристики, по которой мы сортируем.

 int[] array = ; System.out.println(Arrays.toString(array)); for (int left = 0; left < array.length; left++) < // Вытаскиваем значение элемента int value = array[left]; // Перемещаемся по элементам, которые перед вытащенным элементом int i = left - 1; for (; i >= 0; i--) < // Если вытащили значение меньшее — передвигаем больший элемент дальше if (value < array[i]) < array[i + 1] = array[i]; >else < // Если вытащенный элемент больше — останавливаемся break; >> // В освободившееся место вставляем вытащенное значение array[i + 1] = value; > System.out.println(Arrays.toString(array)); 

Челночная сортировка (Shuttle Sort)

Среди простых сортировок есть ещё одна — челночная сортировка. Но мне больше нравится шаттл сорт. Мне кажется, мы редко говорим про космические челноки, а челночный у нас скорее бег. Поэтому проще представить, как в космос запускаются шаттлы. Вот вам ассоциация с этим алгоритмом. В чём суть алгоритма? Суть алгоритма в том, что мы итерируемся слева направо, при этом при выполнении swap элементов мы выполняем проверку всех остальных элементов, которые остались позади, не нужно ли повторить swap.

 int[] array = ; System.out.println(Arrays.toString(array)); for (int i = 1; i < array.length; i++) < if (array[i] < array[i - 1]) < swap(array, i, i - 1); for (int z = i - 1; (z - 1) >= 0; z--) < if (array[z] < array[z - 1]) < swap(array, z, z - 1); >else < break; >> > > System.out.println(Arrays.toString(array)); 

Сортировка Шелла

Ещё одной простой сортировкой является сортировка Шелла. Суть её похожа на сортировку пузырьком, но каждую итерацию мы имеем разный промежуток между сравниваемыми элементами. Каждую итерацию он уменьшается вдвое. Вот пример реализации:

 int[] array = ; System.out.println(Arrays.toString(array)); // Высчитываем промежуток между проверяемыми элементами int gap = array.length / 2; // Пока разница между элементами есть while (gap >= 1) < for (int right = 0; right < array.length; right++) < // Смещаем правый указатель, пока не сможем найти такой, что // между ним и элементом до него не будет нужного промежутка for (int c = right - gap; c >= 0; c -= gap) < if (array[c] >array[c + gap]) < swap(array, c, c + gap); >> > // Пересчитываем разрыв gap = gap / 2; > System.out.println(Arrays.toString(array)); 

Cортировка слиянием (merge sort)

Помимо указанных простых сортировок, есть сортировки и посложнее. Например, сортировка слиянием. Во-первых, нам на помощь придёт рекурсия. Во-вторых, сложность у нас будет уже не квадратичная, как мы с вами привыкли. Сложность данного алгоритма — логарифмическая. Записывается как O(n log n). Итак, давайте сделаем это. Сначала, напишем рекурсивный вызов метода сортировки:

 public static void mergeSort(int[] source, int left, int right) < // Выберем разделитель, т.е. разделим пополам входной массив int delimiter = left + ((right - left) / 2) + 1; // Выполним рекурсивно данную функцию для двух половинок (если сможем разбить( if (delimiter >0 && right > (left + 1)) < mergeSort(source, left, delimiter - 1); mergeSort(source, delimiter, right); >> 

 public static void mergeSort(int[] source, int left, int right) < // Выберем разделитель, т.е. разделим пополам входной массив int delimiter = left + ((right - left) / 2) + 1; // Выполним рекурсивно данную функцию для двух половинок (если сможем разбить( if (delimiter >0 && right > (left + 1)) < mergeSort(source, left, delimiter - 1); mergeSort(source, delimiter, right); >// Создаём временный массив с нужным размером int[] buffer = new int[right - left + 1]; // Начиная от указанной левой границы идём по каждому элементу int cursor = left; for (int i = 0; i < buffer.length; i++) < // Мы используем delimeter чтобы указывать на элемент из правой части // Если delimeter >right, значит в правой части не осталось недобавленных элементов if (delimiter > right || source[cursor] > source[delimiter]) < buffer[i] = source[cursor]; cursor++; >else < buffer[i] = source[delimiter]; delimiter++; >> System.arraycopy(buffer, 0, source, left, buffer.length); > 

Сортировка подсчётом (Counting Sort) и Поразрядная сортировка (Radix Sort)

Другим интересным алгоритмом сортировки является сортировка подсчётом (Counting Sort). Алгоритмическая сложность в этом случае будет O(n+k), где n — количество элементов, а k — максимальное значение элемента. Есть с алгоритмом одна незадача: нам нужно знать минимальное и максимальное значение в массиве. Вот пример реализации сортировки подсчётом:

 public static int[] countingSort(int[] theArray, int maxValue) < // Массив со "счётчиками" размером от 0 до максимального значения int numCounts[] = new int[maxValue + 1]; // В соответствующей ячейке (индекс = значение) увеличиваем счётчик for (int num : theArray) < numCounts[num]++; >// Подготавливаем массив для отсортированного результата int[] sortedArray = new int[theArray.length]; int currentSortedIndex = 0; // идём по массиву со "счётчиками" for (int n = 0; n < numCounts.length; n++) < int count = numCounts[n]; // идём по количеству значений for (int k = 0; k < count; k++) < sortedArray[currentSortedIndex] = n; currentSortedIndex++; >> return sortedArray; > 

Как мы понимаем, очень неудобно, когда мы должны знать заранее минимальное и максимальное значение. И тут есть другой алгоритм — Radix Sort. Я здесь приведу алгоритм только визуально. Реализацию см. в материалах:

Быстрая сортировка Java (Quick Sort)

Ну и на сладкое — один из самых известных алгоритмов: быстрая сортировка. Она имеет алгоритмическую сложность, то есть мы имеем O(n log n). Данную сортировку ещё называют сортировкой Хоара. Интересно, что алгоритм был придуман Хоаром во время его пребывания в Советском Союзе, где он обучался в Московском университете компьютерному переводу и занимался разработкой русско-английского разговорника. А ещё данный алгоритм в более сложной реализации используется в Arrays.sort в Java. А что с Collections.sort? Предлагаю посмотреть самостоятельно, как сортируются они «под капотом». Итак, код:

 public static void quickSort(int[] source, int leftBorder, int rightBorder) < int leftMarker = leftBorder; int rightMarker = rightBorder; int pivot = source[(leftMarker + rightMarker) / 2]; do < // Двигаем левый маркер слева направо пока элемент меньше, чем pivot while (source[leftMarker] < pivot) < leftMarker++; >// Двигаем правый маркер, пока элемент больше, чем pivot while (source[rightMarker] > pivot) < rightMarker--; >// Проверим, не нужно обменять местами элементы, на которые указывают маркеры if (leftMarker // Сдвигаем маркеры, чтобы получить новые границы leftMarker++; rightMarker--; > > while (leftMarker if (leftBorder < rightMarker) < quickSort(source, leftBorder, rightMarker); >> 

Итог

Выше мы рассмотрели «джентельменский» набор алгоритмов сортировки, реализованных на Java. Алгоритмы вообще штука полезная, как с прикладной точки зрения, так и с точки зрения развития мышления. Некоторые из них попроще, некоторые посложнее. По каким-то умные люди защищали различные работы на степени, а по другим писали толстые-толстые книги. Надеюсь, приложенный к статье материал позволит вам узнать ещё больше, так как это обзорная статья, которая и так получилась увесистой. И цель её — дать небольшое вступление. Про введение в алгоритмы можно так же прочитать ознакомиться с книгой «Грокаем Алгоримы». Также мне нравится плэйлист от Jack Brown — AQA Decision 1 1.01 Tracing an Algorithm. Ради интереса можно посмотреть на визуализацию алгоритмов на sorting.at и visualgo.net. Ну и весь Youtube к вашим услугам.

Источник