1. Въведение
В този урок ще научим Selection Sort , ще видим изпълнението му в Java и ще анализираме неговата ефективност.
2. Преглед на алгоритъма
Selection Sort започва с елемента в 1-ва позиция на несортиран масив и сканира през следващите елементи, за да намери най-малкия елемент . След като бъде намерен, най-малкият елемент се разменя с елемента на 1-ва позиция.
След това алгоритъмът преминава към елемента на 2-ра позиция и сканира през следващите елементи, за да намери индекса на 2-рия най-малък елемент. След като бъде намерен, вторият най-малък елемент се разменя с елемента на 2-ра позиция.
Този процес продължава, докато стигнем до n-1-ия елемент на масива, който поставя n-1-ия най-малък елемент в n-1-ва позиция. Последният елемент автоматично попада на място, в n-1-та итерация, като по този начин сортира масива.
Намираме най-големия елемент вместо най-малкия, за да сортираме масива в низходящ ред.
Нека да видим пример за несортиран масив и да го сортираме във възходящ ред, за да разберем визуално алгоритъма.
2.1. Пример
Помислете за следния несортиран масив:
int [] arr = {5, 4, 1, 6, 2}
Итерация 1
Имайки предвид горната работа на алгоритъма, започваме с елемента в 1-ва позиция - 5 - и сканираме през всички следващи елементи, за да намерим най-малкия елемент - 1. След това сменяме най-малкия елемент с елемента в 1-ва позиция.
Модифицираният масив nows изглежда така:
{1, 4, 5, 6, 2}
Общо направени сравнения: 4
Итерация 2
Във втората итерация преминаваме към 2-ри елемент - 4 - и сканираме през следващите елементи, за да намерим втория най-малък елемент - 2. След това сменяме втория най-малък елемент с елемента на 2-ра позиция.
Модифицираният масив сега изглежда така:
{1, 2, 5, 6, 4}
Общо направени сравнения: 3
Продължавайки по подобен начин, имаме следните повторения:
Итерация 3
{1, 2, 4, 6, 5}
Общо направени сравнения: 2
Итерация 4
{1, 2, 4, 5, 6}
Общо направени сравнения: 1
3. Прилагане
Нека да приложим Selection Sort, като използваме няколко цикъла for :
public static void sortAscending(final int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int minElementIndex = i; for (int j = i + 1; j arr[j]) { minElementIndex = j; } } if (minElementIndex != i) { int temp = arr[i]; arr[i] = arr[minElementIndex]; arr[minElementIndex] = temp; } } }Разбира се, за да го обърнем, бихме могли да направим нещо доста подобно:
public static void sortDescending(final int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int maxElementIndex = i; for (int j = i + 1; j < arr.length; j++) { if (arr[maxElementIndex] < arr[j]) { maxElementIndex = j; } } if (maxElementIndex != i) { int temp = arr[i]; arr[i] = arr[maxElementIndex]; arr[maxElementIndex] = temp; } } }И с малко повече смазка за лакти, бихме могли да ги комбинираме с помощта на Comparator s.
4. Преглед на изпълнението
4.1. Време
In the example that we saw earlier, selecting the smallest element required a total of (n-1) comparisons followed by swapping it to the 1st position. Similarly, selecting the next smallest element required total (n-2) comparisons followed by swapping in the 2nd position, and so on.
Thus, starting from index 0, we perform n-1, n-2, n-3, n-4 …. 1 comparisons. The last element automatically falls in place due to previous iterations and swaps.
Mathematically, the sum of the first n-1 natural numbers will tell us how many comparisons we need in order to sort an array of size n using Selection Sort.
The formula for the sum of n natural numbers is n(n+1)/2.
In our case, we need the sum of first n-1 natural numbers. Therefore, we replace n with n-1 in the above formula to get:
(n-1)(n-1+1)/2 = (n-1)n/2 = (n^2-n)/2
As n^2 grows prominently as n grows, we consider the higher power of n as the performance benchmark, making this algorithm have a time complexity of O(n^2).
4.2. Space
По отношение на допълнителната сложност на пространството, Selection Sort изисква една допълнителна променлива, която да държи стойността временно за размяна. Следователно сложността на пространството за сортиране на селекцията е O (1) .
5. Заключение
Selection Sort е много прост алгоритъм за сортиране за разбиране и прилагане. За съжаление, неговата квадратична времева сложност го прави скъпа техника за сортиране . Освен това, тъй като алгоритъмът трябва да сканира през всеки елемент, сложността на най-добрия случай, средния случай и най-лошия случай е еднаква .
Други техники за сортиране като Insertion Sort и Shell Sort също имат квадратична сложност в най-лошия случай, но те се представят по-добре в най-добрите и средни случаи.
Вижте пълния код за Selection Sort over на GitHub.