Как да използвам сортирането на избора

Сортирането по избор е техника за сортиране, която избира елемент от списък и след това заменя мястото му с друг. Той избира най-големия елемент и след това го разменя с елемент в най-високия индекс на списъка.

Алгоритъмът прави това многократно, докато списъкът не бъде сортиран. Ако не сте съвсем сигурни как работи сортирането на подбора, попаднали сте на правилното място. Ще го обясним по-задълбочено по-долу, заедно с показването на пример.

Сортиране на избора: По-близък поглед

Да предположим, че имате списъка: [39, 82, 2, 51, 30, 42, 7]. За да сортирате списъка с помощта на сортиране на селекцията, първо трябва да намерите най-голямото число в него.

С дадения списък това число е 82. Разменете 82 с числото в най-високия индекс (т.е. 7).

След първото преминаване, новият ред на списъка ще бъде: [39, 7, 2, 51, 30, 42, 82]. Всеки път, когато алгоритъмът премине през целия списък, това се нарича "преминаване".

Забележете, че списъкът поддържа сортиран подсписък и несортиран подсписък по време на процеса на сортиране.

Свързани: Какво е Big-O нотация?

Оригиналният списък започва със сортиран списък с нула елементи и несортиран списък на всички елементи. След това след първото преминаване той има сортиран списък, съдържащ само числото 82.

При второто преминаване най-голямото число в несортирания подлист ще бъде 51. Този номер ще бъде заменен с 42, за да се даде нов ред на списъка по-долу:

[39, 7, 2, 42, 30, 51, 82].

Процесът се повтаря, докато не се сортира целият списък. Фигурата по-долу обобщава целия процес:

Цифрите с удебелен черен цвят показват най-високата стойност в списъка по това време. Тези в зелено показват сортирания подлист.

Анализ на алгоритъма

За да получите сложността (използвайки нотация на Big-O) на този алгоритъм, следвайте по-долу:

При първото преминаване се правят сравнения (n-1). На второто преминаване, (n-2). При третото преминаване, (n-3) и така до (n-1)-то преминаване, което прави само едно сравнение.

Обобщавайки сравненията по-долу, се получава:

(n-1) + (n-1) + (n-1) +... + 1 = ((n-1) n) / 2.

Следователно сортирането на подбора е O (n²).

Прилагане на кода

Кодът показва функции, които можете да използвате за извършване на сортиране на подбор с помощта на Python и Java.

Python:

def selectionSort (mylist):
за x в обхват (len (mylist) - 1, 0, -1):
max_idx = 0
за posn в обхват (1, x + 1):
ако mylist [posn]> mylist [max_idx]:
max_idx = posn
temp = mylist [x]
mylist [x] = mylist [max_idx]
mylist [max_idx] = temp

Java:

void selectionSort (int my_array []) { 
за (int x = 0; x { 
индекс int = x; 
за (int y = x + 1; y if (my_array [y] индекс = y; // намиране на най-ниския индекс 
} 
} 
int temp = my_array [индекс]; // temp е временно съхранение
my_array [индекс] = my_array [x]; 
my_array [x] = temp; 
}}

Преминаване от сортиране на селекция към сортиране на обединяване

Както показа алгоритъмният анализ по-горе, алгоритъмът за сортиране на подбора е O (n²). Той има експоненциална сложност и следователно е неефективен за много големи масиви от данни.

Много по-добрият алгоритъм за използване би бил сортиране на сливане със сложност на O (nlogn). И сега знаете как работи сортирането на подбора, следващото в списъка ви за проучване за алгоритми за сортиране трябва да бъде сортирането на сливане.

За автора