Вибір Сортування в Java Програма з прикладом
Джеймс Гартман
⚡ Розумний підсумок
Сортування вибору Java багаторазово сканує несортовану частину масиву, знаходить найменше значення, що залишилося, та міняє його місцями, завершуючи роботу максимум з n-1 обмінами незалежно від порядку введення.
Як працює Selection Sort?
Selection Sort реалізує простий алгоритм сортування таким чином:
- Алгоритм повторно шукає найнижчий елемент.
- Поміняти місцями поточний елемент елементом із найменшим значенням
- З кожною ітерацією/проходом сортування вибору елементи міняються місцями.
Таким чином, кожен прохід обробляє масив як дві області: відсортований блок, що зростає зліва, та невідсортований блок, що зменшується справа. Алгоритм обходить невідсортований блок, запам'ятовує індекс найменшого значення, яке він зустрічає, та обмінює це значення з першою невідсортованою позицією.
Оскільки за прохід відбувається лише один обмін, масив із n елементів упорядковується після максимум n-1 обміну. Ця властивість відрізняє цю процедуру від інших підпрограм початкового рівня. Java алгоритми сортування, які переміщують дані набагато частіше.
Команда tracНижче наведено приклад масиву {860, 8, 200, 9} точно так, як програма в наступному розділі виводить його під час виконання.
| Проходити | Порівняння надруковані | Найменше знайдене значення | Масив після заміни |
|---|---|---|---|
| Старт | - | - | 860 8 200 9 |
| 1 | 860 та 8, 8 та 200, 8 та 9 | 8 | 8 860 200 9 |
| 2 | 860 та 200, 200 та 9 | 9 | 8 9 200 860 |
| 3 | 200 і 860 | 200 | 8 9 200 860 |
Дві деталі в цьому tracВарто зупинитися на них. По-перше, на третьому проході все ще повідомляється про заміну, хоча порядок не змінюється, оскільки найменше значення, що залишилося, вже знаходиться на поточному індексі, і програма обмінює елемент сама з собою. По-друге, кількість порівнянь зменшується на одиницю на кожному проході (три, потім два, потім одне), що є закономірністю, що лежить в основі показників складності далі на сторінці.
Java Програма для реалізації Selection Sort
Клас, наведений нижче, називається SelectionSortAlgo та знаходиться в пакеті com.guru99. Метод main() оголошує вибірковий масив, друкує його, передає його selection() для сортування та друкує знову. Допоміжний метод printArray() записує всі елементи в один рядок, що і створює читабельний журнал обробки.
Усередині selection() зовнішній цикл позначає межу між відсортованою та несортованою областями, змінна index містить позицію найменшого значення, яке було знайдено на даний момент, а три присвоєння в кінці кожного проходу виконують обмін.
package com.guru99; public class SelectionSortAlgo { public static void main(String a[]) { int[] myArray = {860,8,200,9}; System.out.println("------Before Selection Sort-----"); printArray(myArray); selection(myArray);//sorting array using selection sort System.out.println("-----After Selection Sort-----"); printArray(myArray); } public static void selection(int[] array) { for (int i = 0; i < array.length - 1; i++) { System.out.println("Sort Pass Number "+(i+1)); int index = i; for (int j = i + 1; j < array.length; j++) { System.out.println("Comparing "+ array[index] + " and " + array[j]); if (array[j] < array[index]){ System.out.println(array[index] + " is greater than " + array[j] ); index = j; } } int smallerNumber = array[index]; array[index] = array[i]; array[i] = smallerNumber; System.out.println("Swapping Elements: New Array After Swap"); printArray(array); } } static void printArray(int[] array){ for(int i=0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
вихід:
Компіляція та запуск класу створює журнал консолі, наведений нижче, з одним блоком виводу на прохід.
------Before Selection Sort----- 860 8 200 9 Sort Pass Number 1 Comparing 860 and 8 860 is greater than 8 Comparing 8 and 200 Comparing 8 and 9 Swapping Elements: New Array After Swap 8 860 200 9 Sort Pass Number 2 Comparing 860 and 200 860 is greater than 200 Comparing 200 and 9 200 is greater than 9 Swapping Elements: New Array After Swap 8 9 200 860 Sort Pass Number 3 Comparing 200 and 860 Swapping Elements: New Array After Swap 8 9 200 860 -----After Selection Sort----- 8 9 200 860
Дві проблеми застають новачків у свідомості, коли вони вперше запускають цей приклад. Оскільки у файлі оголошується package com.guru99;, джерело повинно знаходитися у відповідному com/guru99 каталог, інакше компілятор повідомляє про невідповідність імені пакета або класу. Клас тоді має бути запущений за його повним ім'ям, java com.guru99.SelectionSortAlgo, тому що звичайний java SelectionSortAlgo викликає помилку NoClassDefFoundError.
Межі циклу – це ще одна поширена пастка. Зовнішній цикл зупиняється на array.length - 1 а внутрішній цикл починається з i + 1; зміна будь-якої з меж призводить до зайвого порожнього проходу або винятку ArrayIndexOutOfBoundsException.
Часова та просторова складність сортування вибіркою
Внутрішній цикл у програмі завжди виконується до кінця масиву, тому алгоритм виконує однакову кількість порівнянь незалежно від вигляду даних. Для масиву з n елементів ця сума дорівнює n(n-1)/2, що для вибірки з чотирьох елементів дорівнює шести, і наведений вище вивід дійсно друкує рівно шість рядків порівняння.
| випадок | Порівняння | Свопи | Часова складність | Допоміжний простір |
|---|---|---|---|---|
| Найкращий (масив вже відсортовано) | n(n-1)/2 | н-1 | O (n²) | O (1) |
| Середнє (випадковий порядок) | n(n-1)/2 | н-1 | O (n²) | O (1) |
| Найгірше (у зворотному порядку) | n(n-1)/2 | н-1 | O (n²) | O (1) |
З цього рівномірного ряду фігур випливають три наслідки:
- Сортування вибором не є адаптивним. Вартість відсортованих вхідних даних рівно стільки ж, скільки й зворотних вхідних даних, тому немає такого скороченого шляху для раннього виходу. сортування бульбашками пропозиції.
- Кількість обмінів є сильною стороною алгоритму. Відбувається максимум n-1 обмінів, що набагато менше, ніж квадратична кількість ходів, яку можуть зробити інші прості сортування.
- Використання пам'яті є константним. Потрібні лише лічильники циклів та дві тимчасові змінні index та smallerNumber, тому допоміжний простір займає O(1), а сортування відбувається на місці.
Квадратичне зростання є практичною межею. Подвоєння розміру масиву приблизно вчетверо збільшує обсяг порівняння, тому сортування вибором підходить для навчання, невеликих масивів та вбудованого коду, а не для виробничих наборів даних, де правильним вибором є алгоритми O(n log n).
Переваги та недоліки сортування вибором
Розуміння того, де алгоритм допомагає, а де шкодить, полегшує вирішення, коли його використання є доцільним.
Переваги
- Логіка коротка та зрозуміла, тому це стандартна вправа на першу сортування поряд сортування вставки.
- Він сортує на місці, тому другий масив не виділяється, а використання пам'яті не зростає разом із вхідними даними.
- Він виконує максимум n-1 записів у масив, що має значення для сховища, де записи повільні або зношують носій.
- Час його виконання повністю передбачуваний, оскільки кількість порівнянь залежить лише від довжини масиву.
Недоліки
- Кожен випадок є O(n²), тому алгоритм не масштабується для великих колекцій.
- Він не може виявити вже відсортований масив і тому ніколи не завершує роботу раніше.
- Класична форма, показана вище, є нестабільною, тому два рівні значення можуть опинитися в протилежному порядку.
- Він порівнює дані частіше, ніж сортування вставками, на майже впорядкованих даних, де сортування вставками наближається до лінійного часу.
Коротше кажучи, вибирайте сортування вибором, коли масив малий, і кожен запис є дорогим, і уникайте його, коли набір даних великий або вже близький до відсортування.
Сортування вибором проти Bubble-сортування проти сортування вставками
Усі три алгоритми є квадратичними сортуваннями на місці, проте вони поводяться по-різному, коли змінюється форма вхідних даних.
| критерій | Сортування вибором | Bubblсортування | Сортування вставкою |
|---|---|---|---|
| Найкращий час | O (n²) | О (п) | О (п) |
| Середній та найгірший час | O (n²) | O (n²) | O (n²) |
| Обміни або зміщення у найгіршому випадку | n-1 свопів | n(n-1)/2 обмінів | До n(n-1)/2 змін |
| Стабільний | Немає | Так | Так |
| Адаптивний до відсортованого вхідного сигналу | Немає | Так | Так |
| Допоміжний простір | O (1) | O (1) | O (1) |
| Типове використання | Найменша кількість записів | Навчання та виявлення відсортованих даних | Малі або майже відсортовані масиви |
У таблиці пояснюється поширена відповідь на співбесіді. Сортування вибором перемагає за кількістю обмінів, бульбашкове сортування – за розпізнаванням уже впорядкованих вхідних даних, а сортування вставками зазвичай є найшвидшим з трьох на практиці, оскільки реальні дані часто частково відсортовані. Жоден з них не конкурує з сортуванням злиттям або швидким сортуванням, коли масив перевищує кілька десятків елементів.
