Сортування – один із базових видів діяльності або дій, що виконуються над об'єктами. Ще в дитинстві дітей вчать сортувати, розвиваючи мислення. Комп'ютери та програми теж не є винятком. Існує безліч алгоритмів. Пропоную подивитися, які вони бувають і як працюють. Крім того, раптом вас запитають про один із них на співбесіді?
Вступ
Сортування елементів – одна з категорій алгоритмів, до яких розробник має звикнути. Якщо колись, коли я навчався, інформатика не сприймалася так серйозно, то зараз уже в школі повинні вміти реалізовувати алгоритми сортування та розуміти їх.
Базові, найпростіші алгоритми реалізуються за допомогою циклу for. Звичайно, щоб відсортувати колекцію елементів, наприклад масив, потрібно якось пройтися по цій колекції. Наприклад:
int[] array ={10,2,10,3,1,2,5};for(int i =0; i < array.length; i++){System.out.println(array[i]);}
Що можна сказати про цю ділянку коду? Ми маємо цикл, у якому змінюємо значення індексу (int i) від 0 до останнього елемента масиву. Фактично ми просто беремо кожен елемент масиву і виводимо його вміст.
Чим більше елементів у масиві, тим довше виконуватиметься код. Тобто, якщо n – кількість елементів, то при n = 10 програма виконуватиметься у 2 рази довше, ніж при n = 5.
Коли в нашій програмі є один цикл, час виконання зростає лінійно: що більше елементів, то довше триває виконання. Виходить, що алгоритм працює за лінійний час (n). У такому разі говорять, що складність алгоритму дорівнює O(n). Це позначення ще називають «велика O» або «асимптотична поведінка». Але можна запам'ятати просто: «складність алгоритму».
Найпростіше сортування (Bubble Sort)
Отже, ми маємо масив і можемо ним ітеруватися. Чудово. Давайте спробуємо відсортувати його за зростанням.
Що це означає для нас? Це означає, що, маючи два елементи (наприклад, a = 6, b = 5), ми повинні поміняти місцями a та b, якщо a більше за b (тобто якщо a > b).
Що це означає для нас при роботі з колекцією за індексом (як у випадку з масивом)? Це означає, що якщо елемент з індексом a більший за елемент з індексом b (array[a] > array[b]), то такі елементи потрібно поміняти місцями. Зміну місць часто називають swap. Існують різні способи зміни місць, але ми використаємо простий, зрозумілий код, який легко запам'ятовується:
int[] array ={10,2,10,3,1,2,5};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 ={10,2,10,3,1,2,5};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));
Ось наше перше сортування і відпрацювало. Ми ітеруємося у зовнішньому циклі (while) доти, доки не вирішимо, що ітерацій більше не потрібно.
За замовчуванням перед кожною новою ітерацією ми припускаємо, що наш масив відсортований і більше не хочемо ітеруватися. Тому ми послідовно проходимо елементи й перевіряємо це припущення.
Але якщо елементи не по порядку, ми виконуємо swap елементів та розуміємо, що немає впевненості, що тепер елементи у правильному порядку. Отже, хочемо виконати ще одну ітерацію.
Наприклад, [3, 5, 2]. 5 більше за 3, усе гаразд. Але 2 менше за 5. Проте [3, 2, 5] потребує ще одного проходу, оскільки 3 > 2 і їх треба поміняти місцями.
Оскільки ми використовуємо цикл у циклі, виходить, що складність нашого алгоритму збільшується. Для n елементів вона стає n * n, тобто O(n^2). Така складність називається квадратичною.
Як ми розуміємо, ми не можемо точно знати, скільки знадобиться ітерацій. Показник складності алгоритму має на меті показати тенденцію зростання складності, найгірший випадок. Наскільки сильно збільшуватиметься час роботи при зміні кількості елементів n.
Сортування бульбашкою – одне з найпростіших і неефективних сортувань. Його ще іноді називають «дурним сортуванням».
Матеріал на тему:
Інше сортування – сортування вибором. Воно також має квадратичну складність, але про це трохи згодом.
Отже, ідея проста. Під час кожного проходу вибирається найменший елемент і переміщується на початок. При цьому кожен новий прохід починається зі зміщенням праворуч, тобто перший прохід – з першого елемента, другий прохід – з другого.
Виглядатиме це так:
int[] array ={10,2,10,3,1,2,5};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));
Це сортування є нестійким, оскільки однакові елементи (з погляду характеристики, за якою ми їх сортуємо) можуть змінити свій взаємний порядок.
Хороший приклад наведено у статті Вікіпедії: Сортування вибором.
Матеріал на тему:
Сортування вставками також має квадратичну складність, оскільки у нас знову цикл у циклі.
У чому ж відмінність від сортування вибором? Це сортування є стійким. Це означає, що однакові елементи не змінюють свого взаємного порядку з погляду характеристики, за якою ми їх сортуємо.
int[] array ={10,2,10,3,1,2,5};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));
Серед простих алгоритмів сортування є ще один – човникове сортування. Але мені більше подобається назва «шатл-сортування». Мені здається, ми рідко говоримо про космічні човники, а слово «шатл» одразу викликає асоціацію з космічними кораблями. Тому простіше уявити, як у космос запускають шатли. Ось вам асоціація з цим алгоритмом.
У чому полягає суть алгоритму? Суть алгоритму полягає в тому, що ми ітеруємося ліворуч, при цьому під час виконання swap елементів перевіряємо всі інші елементи, що залишилися позаду, щоб з'ясувати, чи не потрібно повторити swap.
int[] array ={10,2,10,3,1,2,5};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 ={10,2,10,3,1,2,5};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));
Окрім зазначених простих алгоритмів сортування, існують і складніші. Наприклад, сортування злиттям. По-перше, нам знадобиться рекурсія. По-друге, складність алгоритму вже не буде квадратичною, як у попередніх прикладах. Складність цього алгоритму – O(n log n). Отже, давайте реалізуємо його.
Спочатку напишемо рекурсивний виклик методу сортування:
publicstaticvoidmergeSort(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);}}
Тепер додамо до нього основну логіку. Ось приклад нашого методу з реалізацією:
publicstaticvoidmergeSort(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 =newint[right - left +1];// Починаючи із зазначеної лівої межі, проходимо по кожному елементуint cursor = left;for(int i =0; i < buffer.length; i++){// Використовуємо delimiter, щоб указувати на елемент із правої частини// Якщо delimiter > 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);}
Запустимо приклад, викликавши метод mergeSort(array, 0, array.length - 1). Як бачимо, суть алгоритму зводиться до того, що ми передаємо на вхід масив із зазначенням початку та кінця ділянки, яку потрібно відсортувати. На початку сортування це початок і кінець усього масиву. Далі ми обчислюємо delimiter – позицію роздільника. Якщо роздільник може поділити масив на дві частини, рекурсивно викликаємо сортування для ділянок, на які він розбив масив. Потім готуємо додатковий буферний масив, у якому зберігатиметься відсортована ділянка. Після цього встановлюємо курсор на початок ділянки, що сортується, і починаємо проходити по кожному елементу підготовленого порожнього масиву, заповнюючи його найменшими елементами. Якщо елемент, на який вказує курсор, менший за елемент, на який вказує роздільник, поміщаємо цей елемент до буферного масиву та зміщуємо курсор. Інакше поміщаємо до буферного масиву елемент, на який вказує роздільник, і зміщуємо сам роздільник. Щойно роздільник вийде за межі ділянки, що сортується, або буде заповнено весь буферний масив, відповідний діапазон вважається відсортованим.
Матеріали на тему:
Сортування підрахунком (Counting Sort) і поразрядне сортування (Radix Sort)
Ще одним цікавим алгоритмом є сортування підрахунком (Counting Sort). Алгоритмічна складність у цьому випадку становить O(n + k), де n – кількість елементів, а k – максимальне значення елемента. Проте цей алгоритм має один недолік: нам потрібно знати мінімальне та максимальне значення в масиві.
Ось приклад реалізації сортування підрахунком:
publicstaticint[]countingSort(int[] theArray,int maxValue){// Масив «лічильників» розміром від 0 до максимального значенняint numCounts[]=newint[maxValue +1];// У відповідній комірці (індекс = значення) збільшуємо лічильникfor(int num : theArray){
numCounts[num]++;}// Готуємо масив для відсортованого результатуint[] sortedArray =newint[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. Тут я наведу алгоритм лише схематично. Реалізацію дивіться в матеріалах:
Матеріали:
І насамкінець – один із найвідоміших алгоритмів: швидке сортування. Його алгоритмічна складність становить O(n log n).
Цей алгоритм також називають сортуванням Хоара. Цікаво, що його автор, Хоар, придумав цей алгоритм під час перебування в Радянському Союзі, де навчався в Московському університеті за напрямом комп'ютерного перекладу та займався розробкою російсько-англійського розмовника. Крім того, цей алгоритм у складнішій реалізації використовується в Arrays.sort у Java. А як щодо Collections.sort? Пропоную самостійно подивитися, як вони працюють «під капотом».
Отже, код:
publicstaticvoidquickSort(int[] source,int leftBorder,int rightBorder){int leftMarker = leftBorder;int rightMarker = rightBorder;int pivot = source[(leftMarker + rightMarker)/2];do{// Переміщуємо лівий маркер зліва направо, доки елемент менший за pivotwhile(source[leftMarker]< pivot){
leftMarker++;}// Переміщуємо правий маркер, доки елемент більший за pivotwhile(source[rightMarker]> pivot){
rightMarker--;}// Перевіряємо, чи потрібно поміняти місцями елементи, на які вказують маркериif(leftMarker <= rightMarker){// Лівий маркер буде меншим за правий лише тоді, коли потрібно виконати swapif(leftMarker < rightMarker){int tmp = source[leftMarker];
source[leftMarker]= source[rightMarker];
source[rightMarker]= tmp;}// Зміщуємо маркери, щоб отримати нові межі
leftMarker++;
rightMarker--;}}while(leftMarker <= rightMarker);// Рекурсивно виконуємо сортування для обох частинif(leftMarker < rightBorder){quickSort(source, leftMarker, rightBorder);}if(leftBorder < rightMarker){quickSort(source, leftBorder, rightMarker);}}
Тут усе дуже страшно, тож будемо розбиратися. Для вхідного масиву int[] source виставляємо два маркери: лівий (L) і правий (R). При першому виклику вони відповідають початку та кінцю масиву. Далі визначається опорний елемент, він же pivot. Після цього наше завдання – перемістити значення, менші за pivot, у ліву від pivot частину, а більші – у праву.
Для цього спочатку рухаємо покажчик L, доки не знайдемо значення, більше за pivot. Якщо більшого значення не знайшли, то L збіжиться з pivot.
Потім рухаємо покажчик R, доки не знайдемо значення, менше за pivot. Якщо меншого значення не знайшли, то R збіжиться з pivot.
Далі, якщо покажчик L знаходиться перед покажчиком R або збігається з ним, то намагаємося виконати обмін елементів, якщо елемент L менший за R. Далі L зміщуємо праворуч на 1 позицію, R зміщуємо ліворуч на 1 позицію.
Коли лівий маркер L опиниться за правим маркером R, це означатиме, що обмін завершено: ліворуч від pivot – менші значення, праворуч від pivot – більші значення.
Після цього рекурсивно викликаємо таке саме сортування для ділянок масиву: від початку ділянки, що сортується, до правого маркера і від лівого маркера до кінця ділянки, що сортується.
Чому від початку до правого? Тому що в кінці ітерації так і вийде, що правий маркер зміститься настільки, що стане межею частини зліва.
Цей алгоритм складніший, ніж просте сортування, тому його краще замалювати. Візьмемо білий аркуш паперу, запишемо: 4 2 6 7 3, а pivot буде по центру, тобто число 6. Обведемо його в коло.
Під 4 напишемо L, під 3 напишемо R. 4 менше за 6, 2 менше за 6. Отже, L перемістився на позицію pivot, оскільки за умовою L не може піти далі, ніж pivot.
Напишемо знову 4 2 6 7 3, обведемо 6 у коло (pivot) і поставимо під ним L. Тепер рухаємо покажчик R. 3 менше за 6, тому ставимо маркер R на цифру 3. Оскільки 3 менше за pivot 6, виконуємо swap, тобто обмін. Запишемо результат: 4 2 3 7 6, обводимо 6 у коло, оскільки він, як і раніше, pivot.
Покажчик L на цифрі 3, покажчик R на цифрі 6. Ми пам'ятаємо, що рухаємо покажчики доти, доки L не зайде за R. L рухаємо на наступну цифру.
Тут хочеться розібрати два варіанти: якби передостання цифра була 7 і якби вона була не 7, а 1.
Передостання цифра 1: Змістили покажчик L на цифру 1, оскільки ми можемо рухати L доти, доки покажчик L вказує на цифру, меншу за pivot. А ось R ми не можемо змістити з 6, оскільки R можемо рухати тільки тоді, коли покажчик R вказує на цифру, більшу за pivot. swap не робимо, оскільки 1 менше за 6. Записуємо положення: 4 2 3 1 6, обводимо pivot 6. L зміщується на pivot і більше не рухається. R теж не рухається. Обмін не виконуємо. Зміщуємо L і R на одну позицію і підписуємо цифру 1 маркером R, а L опиняється поза числом. Оскільки L поза числом – нічого не робимо, а ось частину 4 2 3 1 виписуємо знову, оскільки це наша ліва частина, менша за pivot 6. Вибираємо новий pivot і починаємо все спочатку.
Передостання цифра 7: Змістили покажчик L на цифру 7, правий покажчик не можемо рухати, оскільки він уже вказує на pivot. Оскільки 7 більше за pivot, то робимо swap. Запишемо результат: 4 2 3 6 7, обводимо 6 кружком, оскільки він pivot. Покажчик L тепер зміщується на цифру 7, а покажчик R зміщується на цифру 3. Частину від L до кінця немає сенсу сортувати, оскільки там лише 1 елемент, а ось частину від 4 до покажчика R відправляємо на сортування. Вибираємо pivot і починаємо все спочатку.
Може на перший погляд здатися, що якщо розставити багато однакових із pivot значень, це зламає алгоритм, але це не так. Можна придумати каверзні варіанти і на папері переконатися, що все правильно, та здивуватися, як такі прості дії забезпечують такий надійний механізм. Єдиний мінус – таке сортування не є стабільним. Оскільки під час виконання обміну однакові елементи можуть поміняти свій порядок, якщо один із них зустрівся до pivot до того, як інший елемент потрапив у частину до pivot за допомогою обміну.
Підсумок
Вище ми розглянули «джентльменський» набір алгоритмів сортування, реалізованих на Java. Алгоритми – корисна річ як із прикладної точки зору, так і з точки зору розвитку мислення. Деякі з них простіші, деякі – складніші. За одними розумні люди захищали наукові роботи, а за іншими писали товсті-претовсті книги.
Сподіваюся, матеріали, наведені в цій статті, допоможуть вам дізнатися ще більше, адже це лише оглядова стаття, яка й без того вийшла досить об'ємною. Її головна мета – дати невеликий вступ.
Про вступ до алгоритмів також можна прочитати в книзі Грокаємо алгоритми або безболісне введення в алгоритми.
Також мені подобається плейлист від Jack Brown – AQA Decision 1 1.01 Tracing an Algorithm.
Заради цікавості можна подивитися на візуалізацію алгоритмів visualgo.net. Ну і, звісно, весь YouTube до ваших послуг.
Матеріали:
