Алгоритъм за сортиране чрез селекция с Python Code Пример

Какво е сортиране при избор?

СОРТИРАНЕ НА ИЗБОР е алгоритъм за сортиране на сравнение, който се използва за сортиране на произволен списък от елементи във възходящ ред. Сравнението не изисква много допълнително място. Изисква само едно допълнително място в паметта за времевата променлива.

Това е известно като на място сортиране. Сортирането на селекцията има времева сложност O(n²), където n е общият брой елементи в списъка. Времевата сложност измерва броя на итерациите, необходими за сортиране на списъка. Списъкът е разделен на две части: Първият списък съдържа сортирани елементи, докато вторият списък съдържа несортирани елементи.

По подразбиране сортираният списък е празен, а несортираният съдържа всички елементи. След това несортираният списък се сканира за минималната стойност, която след това се поставя в сортирания списък. Този процес се повтаря, докато всички стойности бъдат сравнени и сортирани.

Как работи сортирането при избор?

Първият елемент в несортирания дял се сравнява с всички стойности от дясната страна, за да се провери дали е минималната стойност. Ако не е минималната стойност, тогава нейната позиция се разменя с минималната стойност.

Пример

• Например, ако индексът на минималната стойност е 3, тогава стойността на елемента с индекс 3 се поставя на индекс 0, докато стойността, която е била на индекс 0, се поставя на индекс 3. Ако първият елемент в несортирания дял е минималната стойност, след което връща позициите си.
• Елементът, който е определен като минимална стойност, след това се премества в дяла от лявата страна, който е сортираният списък.
• Разделената страна вече има един елемент, докато неразделената страна има (n – 1) елемента, където n е общият брой елементи в списъка. Този процес се повтаря отново и отново, докато всички елементи бъдат сравнени и сортирани въз основа на техните стойности.

Определяне на проблема

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

[21,6,9,33,3]

Горният списък трябва да бъде сортиран, за да се получат следните резултати

[3,6,9,21,33]

Решение (алгоритъм)

Стъпка 1) Вземете стойността на n, която е общият размер на масива

Стъпка 2) Разделете списъка на сортирани и несортирани секции. Сортираният раздел първоначално е празен, докато несортираният съдържа целия списък

Стъпка 3) Изберете минималната стойност от неразделената секция и я поставете в сортираната секция.

Стъпка 4) Повторете процеса (n – 1) пъти, докато всички елементи в списъка бъдат сортирани.

Визуално представяне

Като се има предвид списък от пет елемента, следните изображения илюстрират как алгоритъмът за сортиране на селекция итерира през стойностите, когато ги сортира.

Следното изображение показва несортирания списък

Стъпка 1)

Първата стойност 21 се сравнява с останалите стойности, за да се провери дали е минималната стойност.

3 е минималната стойност, така че позициите на 21 и 3 са разменени. Стойностите със зелен фон представляват сортирания дял на списъка.

Стъпка 2)

Стойността 6, която е първият елемент в несортирания дял, се сравнява с останалите стойности, за да се установи дали съществува по-ниска стойност

Стойността 6 е минималната стойност, така че запазва позицията си.

Стъпка 3)

Първият елемент от несортирания списък със стойност 9 се сравнява с останалите стойности, за да се провери дали е минималната стойност.

Стойността 9 е минималната стойност, така че запазва позицията си в сортирания дял.

Стъпка 4)

Стойността 33 се сравнява с останалите стойности.

Стойността 21 е по-ниска от 33, така че позициите се разменят, за да се получи горният нов списък.

Стъпка 5)

Имаме само една останала стойност в неразделения списък. Следователно вече е сортиран.

Крайният списък е като този, показан на изображението по-горе.

Използване на програма за сортиране на селекция Python 3

Следващият код показва изпълнението на сортиране на селекция с помощта на Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ):
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

Изпълнението на горния код води до следните резултати

[3, 6, 9, 21, 33]

Code Обяснение

Обяснението на кода е следното

Ето Code обяснение:

1. Дефинира функция с име selectionSort
2. Получава общия брой елементи в списъка. Нуждаем се от това, за да определим броя на преминаванията, които трябва да бъдат направени при сравняване на стойности.
3. Външен контур. Използва цикъла за итерация през стойностите на списъка. Броят на повторенията е (n – 1). Стойността на n е 5, така че (5 – 1) ни дава 4. Това означава, че външните итерации ще бъдат извършени 4 пъти. Във всяка итерация стойността на променливата i се присвоява на променливата minValueIndex
4. Вътрешен контур. Използва цикъла, за да сравни най-лявата стойност с другите стойности от дясната страна. Стойността за j обаче не започва от индекс 0. Тя започва от (i + 1). Това изключва стойностите, които вече са били сортирани, така че да се фокусираме върху елементи, които все още не са сортирани.
5. Намира минималната стойност в несортирания списък и я поставя на правилната й позиция
6. Актуализира стойността на minValueIndex при размянатаping условието е вярно
7. Сравнява стойностите на индексните числа minValueIndex и i, за да види дали не са равни
8. Най-лявата стойност се съхранява във времева променлива
9. По-ниската стойност от дясната страна заема първата позиция
10. Стойността, която е била съхранена във времевата стойност, се съхранява в позицията, която преди това е била задържана от минималната стойност
11. Връща сортирания списък като резултат от функцията
12. Създава списък el, който съдържа произволни числа
13. Отпечатайте сортирания списък, след като извикате функцията за сортиране на избора, предавайки el като параметър.

Времева сложност на сортиране на избора

Сложността на сортиране се използва за изразяване на броя пъти на изпълнение, необходими за сортиране на списъка. Изпълнението има два цикъла.

Външният цикъл, който избира стойностите една по една от списъка, се изпълнява n пъти, където n е общият брой стойности в списъка.

Вътрешният цикъл, който сравнява стойността от външния цикъл с останалите стойности, също се изпълнява n пъти, където n е общият брой елементи в списъка.

Следователно броят на изпълненията е (n * n), което също може да бъде изразено като O(n²).

Сортирането на селекцията има три категории на сложност, а именно;

• Най-лошия случай – тук е предоставеният списък в низходящ ред. Алгоритъмът изпълнява максималния брой изпълнения, който се изразява като [Big-O] O(n²)
• Най-добър случай – това се случва, когато предоставеният списък е вече сортиран. Алгоритъмът извършва минималния брой изпълнения, който се изразява като [Big-Omega] Ω(n²)
• Среден случай – това се случва, когато списъкът е подреден произволно. Средната сложност се изразява като [Big-theta] Θ(n²)

Сортирането чрез селекция има пространствена сложност O(1), тъй като изисква една темпорална променлива, използвана за размяна.ping стойности.

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

Сортирането на селекцията се използва най-добре, когато искате да:

• Трябва да сортирате малък списък от елементи във възходящ ред
• Когато цената на замянатаping стойностите са незначителни
• Използва се и когато трябва да се уверите, че всички стойности в списъка са проверени.

Предимства на Selection Sort

Следните са предимствата на селекцията

• Представя се много добре на малки списъци
• Това е алгоритъм на място. Не изисква много място за сортиране. Само едно допълнително място е необходимо за задържане на времевата променлива.
• Той се представя добре на елементи, които вече са сортирани.

Недостатъци на Selection Sort

Следните са недостатъците на селекцията.

• Той се представя зле, когато работи върху огромни списъци.
• Броят итерации, направени по време на сортирането, е n-квадрат, където n е общият брой елементи в списъка.
• Други алгоритми, като бързо сортиране, имат по-добра производителност в сравнение със сортирането чрез избор.

Въпроси и Отговори