playing cards

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

Как продолжение статьи об алгоритмах хочу предоставить Вам материал об разных сортировках массива. Хотя в библиотеке Array есть метод сортировки массива все же будет не лишним знать, как это делать самому и как это все работает. 

На первый взгляд, задача сортировки массива, может показаться простой и не требующей такого внимания на целую статью. Но в действительности — это серьезная проблема, которой занимаются ученые при изучении алгоритмов.

Сортировка массива используется в реальных проектах чаще, чем Вы это можете представить. Например, файловому менеджеру необходимо отсортировать отображаемые файлы по имени, чтобы пользователь мог легко перемещаться по ним. Или, еще один пример, в видеоигре может понадобиться сортировка 3D-объектов, отображаемых в мире, на основе их расстояния от глаза игрока в виртуальном мире, чтобы определить, что видимо, а что нет. Объекты, которые оказываются ближе всего к игроку видны, а те, которые находятся дальше, могут скрываться.

С полезностью сортировки разобрались. Теперь можно и рассмотреть алгоритмы. И первое, что мы рассмотрим это будет алгоритм сортировки выбором. Это один из самых простых алгоритмов сортировки массива. Его простота реализации сказывается на скорости работы такого алгоритма.

Шаги алгоритма:

  1. Находим номер минимального значения в текущем списке;
  2. Производим обмен этого значения со значением первой не отсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции);
  3. Теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы.

 

Код    
  1. int[] arr = {4, 4, 9, 2, 3};
  2.     /*
  3.      * По очереди будем просматривать все подмножества элементов массива (0 -
  4.      * последний, 1-последний, 2-последний,...)
  5.      */
  6.     for(int i = 0;i<arr.length;i++) {
  7.         /*
  8.          * Предполагаем, что первый элемент (в каждом подмножестве элементов)
  9.          * является минимальным
  10.          */
  11.         int min = arr[i];
  12.         int min_i = i;
  13.         /*
  14.          * В оставшейся части подмножества ищем элемент, который меньше
  15.          * предположенного минимума
  16.          */
  17.         for (int j = i + 1; j < arr.length; j++) {
  18.             // Если находим, запоминаем его индекс
  19.             if (arr[j] < min) {
  20.                 min = arr[j];
  21.                 min_i = j;
  22.             }
  23.         }
  24.         /*
  25.          * Если нашелся элемент, меньший, чем на текущей позиции, меняем их
  26.          * местами
  27.          */
  28.         if (i != min_i) {
  29.             int tmp = arr[i];
  30.             arr[i] = arr[min_i];
  31.             arr[min_i] = tmp;
  32.         }
  33.     }

 

Скорость работы данного алгоритма сильно зависит от исходного массива. Частично упорядочен массив будет отсортирован очень таки быстро, несмотря на простоту алгоритма.

Следующий алгоритм, который мы рассмотрим будет алгоритм сортировки пузырьком. Очень часто на собеседованиях просят написать именно этот алгоритм.

алгоритм сортировки пузырьком

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим
«наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).

Вот его код на Java:

 

Код    
  1. for (int i = 0; i < a.length - 1; i++)
  2.             for (int j = 0; j < a.length - i - 1; j++)
  3.                 if (a[j] > a[j + 1]) {
  4.                     int temp = a[j];
  5.                     a[j] = a[j + 1];
  6.                     a[j + 1] = temp;
  7.                 }

Достаточно скромно и просто. Можно использовать, когда есть массив небольшого размера. При увеличении массива, код будет работать медленнее, по сравнению с другими алгоритмами.

 

Далее посмотрим на алгоритм сортировки вставками, который удобен для сортировки коротких последовательностей. Чтобы представить, как работает алгоритм необходимо вспомнить, игру в карты. А именно: когда мы сортируем карты в руках от большей к меньшей или наоборот. Держа в левой руке уже упорядоченные карты и взяв правой рукой очередную карту, мы вставляем ее в нужное место, сравнивая с имеющимися и идя справа налево.

алгоритм сортировки вставками

На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.

Код    
  1. int key;
  2.         for (int i = 1; i < array.length; i++) {
  3.             key = array[i];
  4.             int j = i - 1;
  5.             while (j >= 0 && array[j] < key) {
  6.                 array[j + 1] = array[j];
  7.                 j = j - 1;
  8.             }
  9.             array[j + 1] = key;
  10.         }

Время сортировки вставками зависит от массива. Чем больше сортируемый массив, тем больше может понадобиться времени для его сортировки. Причем здесь, как Вы могли заметить, важен не только размер, но и входной массив. Если Вы читали предыдущий материал о сложности алгоритма, то можете посчитать, что его сложность составляет О(n)=n^2 что не очень хорошо для алгоритма. Этот алгоритм используется как часть алгоритма сортировки Шелла.

При сортировке Шелла сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии d. Выбор d – как последовательность чисел Фибоначчи. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d=1 (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

Догодуюсь, что немного непонятно. Попробую привести пример. Пусть дан список A = (32, 95, 16, 82, 24, 66, 35, 19, 75, 54, 40, 43, 93, 68) и выполняется его сортировка методом Шелла, а в качестве значений d выбраны 5, 3, 1.
На первом шаге сортируются подмассивы A, составленные из всех элементов A, различающихся на 5 позиций, то есть подмассивы A_{5,1} = (32, 66, 40), A_{5, 2} = (95, 35, 43), A_{5, 3} = (16, 19, 93), A_{5, 4} = (82, 75, 68), A_{5, 5} = (24, 54).
В полученном массиве на втором шаге вновь сортируются подмассивы из отстоящих на 3 позиции элементов. Процесс завершается обычной сортировкой вставками получившегося списка.

Вот пример кода на Java:

Код    
  1. int h = 1;
  2.         int n = array.length;
  3.         while (h < n / 3)
  4.             h = 3 * h + 1;
  5.  
  6.         while (h >= 1) {
  7.             for (int i = h; i < array.length; i++) {
  8.                 for (int j = i; j >= h && array[j] > array[j - h]; j -= h) {
  9.                     int temp = array[j];
  10.                     array[j] = array[j - h];
  11.                     array[j - h] = temp;
  12.                 }
  13.             }
  14.             h = h / 3;
  15.         }

Все приведенные выше алгоритмы практически не применяются на практике, так как являются очень медленными и часто зависят от входного массива. Если Вам нужно отсортировать массив или список в реальных проектах — лучше использовать готовые решения, которые сэкономят Вам время и часто будут быстрее самописных. Тот же самый метод sort() из класса Arrays использует совершенствованный алгоритм Быстрой сортировки (Quicksort), который эффективен в большинстве случаев. Для того чтобы отсортировать массив, необходимо написать всего одну строку. Arrays.sort(arr); где arr это имя массива Примечание: в начале файла предварительно нужно подключить библиотеку java.util. import java.util.*;

Знание алгоритмов поможет Вам понять, как примерно работают готовые решения и кто знает, может помогут Вам написать совершенно новый, уникальный и самый быстрый алгоритм сортировки)).

Бонусом скидываю Вам тестовый файл, в котором я набирал несколько алгоритмов:

Код    
  1. package com.stream;
  2.  
  3.  
  4. public class Test {
  5.  
  6.     public String stripHtmlTags(String html) {
  7.         String newHtml = html.replaceAll("\\<[^>]*>", "");
  8.         return newHtml;
  9.  
  10.     }
  11.  
  12.     public int[] insertionSort(int[] array) {
  13.         int key;
  14.         for (int i = 1; i < array.length; i++) {
  15.             key = array[i];
  16.             int j = i - 1;
  17.             while (j >= 0 && array[j] < key) {
  18.                 array[j + 1] = array[j];
  19.                 j = j - 1;
  20.             }
  21.             array[j + 1] = key;
  22.         }
  23.         return array;
  24.     }
  25.  
  26.     public int[] selectionSort(int[] array) {
  27.         for (int i = 0; i < array.length; i++) {
  28.             int min = array[i];
  29.             int min_i = i;
  30.             for (int j = i + 1; j < array.length; j++) {
  31.                 if (array[j] < min) {
  32.                     min = array[j];
  33.                     min_i = j;
  34.                 }
  35.             }
  36.             if (i != min_i) {
  37.                 int tmp = array[i];
  38.                 array[i] = min;
  39.                 array[min_i] = tmp;
  40.             }
  41.         }
  42.         return array;
  43.     }
  44.  
  45.     public int[] shellSorting(int[] array) {
  46.         int h = 1;
  47.         int n = array.length;
  48.         while (h < n / 3)
  49.             h = 3 * h + 1;
  50.  
  51.         while (h >= 1) {
  52.             for (int i = h; i < array.length; i++) {
  53.                 for (int j = i; j >= h && array[j] > array[j - h]; j -= h) {
  54.                     int temp = array[j];
  55.                     array[j] = array[j - h];
  56.                     array[j - h] = temp;
  57.                 }
  58.             }
  59.             h = h / 3;
  60.         }
  61.         return array;
  62.     }
  63.  
  64.     public int[] bubbleSorting(int[] array) {
  65.         for (int i = 0; i < array.length - 1; i++) {
  66.             for (int j = 0; j < array.length - 1 - i; j++) {
  67.                 if (array[j] < array[j + 1]) {
  68.                     int temp = array[j];
  69.                     array[j] = array[j + 1];
  70.                     array[j + 1] = temp;
  71.                 }
  72.             }
  73.         }
  74.         return array;
  75.     }
  76.  
  77.  
  78.     public static void main(String[] args) {
  79.         int[] a = {3, 5, 6 ,3, 76, 4};
  80.         int[] b = new Test().shellSorting(a);
  81.         for (int i = 0; i < b.length; i++) {
  82.             System.out.println(b[i]);
  83.         }
  84.     }
  85. }

Добавить комментарий