Какво е сортиране на подбора?
SELECTION SORT е алгоритъм за сортиране за сравнение, който се използва за сортиране на произволен списък с елементи във възходящ ред. Сравнението не изисква много допълнително пространство. Изисква само едно допълнително място в паметта за временната променлива.
Това е известно като сортиране на място . Сортирането на селекцията има времева сложност на O (n 2 ), където n е общият брой елементи в списъка. Сложността на времето измерва броя повторения, необходими за сортиране на списъка. Списъкът е разделен на два дяла: Първият списък съдържа сортирани елементи, докато вторият списък съдържа несортирани елементи.
По подразбиране сортираният списък е празен и несортираният списък съдържа всички елементи. След това несортираният списък се сканира за минималната стойност, която след това се поставя в сортирания списък. Този процес се повтаря, докато всички стойности бъдат сравнени и сортирани.
В този урок по алгоритъм ще научите:
- Какво е сортиране на подбора?
- Как работи сортирането на подбора?
- Определение на проблема
- Решение (алгоритъм)
- Визуално представяне
- Програма за сортиране на избор с помощта на Python 3
- Обяснение на кода
- Сложност във времето на сортиране на подбора
- Кога да се използва сортиране на селекцията?
- Предимства на сорта за подбор
- Недостатъци на сортирането на селекцията
Как работи сортирането на подбора?
Първият елемент в несортирания дял се сравнява с всички стойности от дясната страна, за да се провери дали това е минималната стойност. Ако това не е минималната стойност, тогава нейната позиция се разменя с минималната стойност.
Пример:
- Например, ако индексът на минималната стойност е 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 = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [21,6,9,33,3]print(selectionSort(el))
Изпълнението на горния код дава следните резултати
[3, 6, 9, 21, 33]
Обяснение на кода
Обяснението на кода е следното
Ето обяснение на кода:
- Определя функция, наречена selectionSort
- Получава общия брой елементи в списъка. Това ни е необходимо, за да определим броя на преминаванията, които трябва да се направят при сравняване на стойностите.
- Външен контур. Използва цикъла за итерация през стойностите на списъка. Броят на повторенията е (n - 1). Стойността на n е 5, така че (5 - 1) ни дава 4. Това означава, че външните итерации ще бъдат извършени 4 пъти. Във всяка итерация стойността на променливата i се присвоява на променливата minValueIndex
- Вътрешен контур. Използва цикъла за сравняване на най-лявата стойност с останалите стойности от дясната страна. Стойността за j обаче не започва при индекс 0. Тя започва от (i + 1). Това изключва стойностите, които вече са сортирани, така че да се съсредоточим върху елементи, които все още не са сортирани.
- Намира минималната стойност в несортирания списък и я поставя в правилното й положение
- Актуализира стойността на minValueIndex, когато условието за размяна е вярно
- Сравнява стойностите на индексните числа minValueIndex и i, за да види дали не са равни
- Най-лявата стойност се съхранява във временна променлива
- Долната стойност от дясната страна заема позицията първа позиция
- Стойността, която е била съхранена във временната стойност, се съхранява в позицията, която преди е била задържана от минималната стойност
- Връща сортирания списък като резултат от функцията
- Създава списък el, който има произволни числа
- Отпечатайте сортирания списък, след като извикате функцията за сортиране, предавайки el като параметър.
Сложност във времето на сортиране на подбора
Сложността на сортирането се използва за изразяване на броя пъти за изпълнение, необходими за сортиране на списъка. Изпълнението има два цикъла.
Външният цикъл, който избира стойностите една по една от списъка, се изпълнява n пъти, където n е общият брой стойности в списъка.
Вътрешният цикъл, който сравнява стойността от външния цикъл с останалите стойности, също се изпълнява n пъти, където n е общият брой елементи в списъка.
Следователно броят на екзекуциите е (n * n), който също може да бъде изразен като O (n 2 ).
Сортирането на селекцията има три категории сложност, а именно;
- Най-лошият случай - тук предоставяният списък е в низходящ ред. Алгоритъмът изпълнява максималния брой изпълнения, който се изразява като [Big-O] O (n 2 )
- Най-добрият случай - това се случва, когато предоставеният списък вече е сортиран. Алгоритъмът изпълнява минималния брой изпълнения, който се изразява като [Big-Omega] Ω (n 2 )
- Среден случай - това се случва, когато списъкът е в произволен ред. Средната сложност се изразява като [Big-theta] ⊝ (n 2 )
Сортирането на селекцията има сложност на пространството от O (1), тъй като изисква една временна променлива, използвана за размяна на стойности.
Кога да се използва сортиране на селекцията?
Сортирането на селекцията се използва най-добре, когато искате:
- Трябва да сортирате малък списък с елементи във възходящ ред
- Когато разходите за размяна на стойности са незначителни
- Използва се и когато трябва да се уверите, че всички стойности в списъка са проверени.
Предимства на сорта за подбор
По-долу са предимствата на селекцията
- Той се представя много добре в малки списъци
- Това е алгоритъм на място. Не изисква много място за сортиране. За задържане на временната променлива се изисква само едно допълнително пространство.
- Той се представя добре на елементи, които вече са сортирани.
Недостатъци на сортирането на селекцията
По-долу са недостатъците на сортирането на селекцията.
- Той се представя слабо при работа по огромни списъци.
- Броят на итерациите, направени по време на сортирането, е n-квадрат, където n е общият брой елементи в списъка.
- Други алгоритми, като например бърза сортировка, имат по-добра производителност в сравнение със сортирането на избора.
Резюме:
- Сортирането по избор е алгоритъм за сравнение на място, който се използва за сортиране на произволен списък в подреден списък. Той има времева сложност на O (n 2 )
- Списъкът е разделен на два раздела, сортиран и несортиран. Минималната стойност се избира от несортираната секция и се поставя в сортираната секция.
- Това нещо се повтаря, докато всички елементи бъдат сортирани.
- Внедряването на псевдокода в Python 3 включва използването на два for цикли и ако инструкции за проверка дали е необходимо размяна
- Сложността на времето измерва броя стъпки, необходими за сортиране на списъка.
- Сложността от време в най-лошия случай се случва, когато списъкът е в низходящ ред. Той има времева сложност на [Big-O] O (n 2 )
- Сложността на времето в най-добрия случай се случва, когато списъкът вече е във възходящ ред. Той има времева сложност на [Big-Omega] Ω (n 2 )
- Сложността на времето в средния случай се случва, когато списъкът е в произволен ред. Той има времева сложност на [Big-theta] ⊝ (n 2 )
- Сортирането на селекцията се използва най-добре, когато имате малък списък с елементи за сортиране, разходите за размяна на стойности не са от значение и проверката на всички стойности е задължителна.
- Сортирането на селекцията не се представя добре в огромни списъци
- Други алгоритми за сортиране, като например бърза сортировка, имат по-добра производителност в сравнение със сортирането на селекцията.