Избор Сортиране в Java Програма с пример
Джеймс Хартман
⚡ Умно обобщение
Сортиране на селекцията Java многократно сканира несортираната част от масив, намира най-малката оставаща стойност и я разменя на позиция, завършвайки работата с най-много n-1 размени, независимо от реда на въвеждане.
Как работи Selection Sort?
Selection Sort прилага прост алгоритъм за сортиране, както следва:
- Алгоритъмът многократно търси най-ниския елемент.
- Разменете текущия елемент с елемент с най-ниска стойност
- При всяка итерация/преминаване на сортиране на селекцията елементите се разменят.
Следователно всяко преминаване третира масив като две области: сортиран блок, който расте отляво, и несортиран блок, който се свива отдясно. Алгоритъмът обхожда несортирания блок, запомня индекса на най-малката стойност, която среща, и разменя тази стойност с първата несортирана позиция.
Тъй като се извършва само една размяна на елементи на проход, масив от n елемента се подрежда след най-много n-1 размени. Това свойство е това, което отличава тази рутина от другите за начинаещи. Java алгоритми за сортиране, които преместват данни много по-често.
- tracПо-долу следва примерния масив {860, 8, 200, 9} точно както програмата в следващия раздел го отпечатва по време на изпълнение.
| Pass | Отпечатани сравнения | Най-малката намерена стойност | Масив след размяната |
|---|---|---|---|
| Начало | - | - | 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 Сортиране срещу сортиране с вмъкване
И трите алгоритъма са квадратични, сравняващи на място сортове, но се държат различно, след като формата на входните данни се промени.
| критерий | Сортиране по избор | Bubble сортиране | Сортиране на вмъкване |
|---|---|---|---|
| Време за най-добър случай | O(n²) | О (п) | О (п) |
| Средно и най-лошо време | O(n²) | O(n²) | O(n²) |
| Размени или промени в най-лошия случай | n-1 суапове | n(n-1)/2 размени | До n(n-1)/2 смени |
| Стабилен | Не | Да | Да |
| Адаптивен към сортиран вход | Не | Да | Да |
| Спомагателно пространство | O (1) | O (1) | O (1) |
| Типична употреба | Най-малко необходими писания | Обучение и откриване на сортирани данни | Малки или почти сортирани масиви |
Таблицата обяснява често срещан отговор на интервю. Сортирането с селекция печели по брой обмени, сортирането с мехурчета печели по разпознаване на вече подреден вход, а сортирането с вмъкване обикновено е най-бързото от трите на практика, защото реалните данни често са частично сортирани. Никое от тях не се конкурира със сортирането с сливане или бързото сортиране, след като масивът нарасне над няколко десетки елемента.
