Сортирање избора: Алгоритам је објашњен на примеру Питхон кода

Преглед садржаја:

Anonim

Шта је сортирање избора?

СЕЛЕЦТИОН СОРТ је алгоритам сортирања поређења који се користи за сортирање случајне листе предмета у растућем редоследу. Поређење не захтева пуно додатног простора. Потребан је само један додатни простор меморије за временску променљиву.

Ово је познато као сортирање на месту . Сортирање избора има временску сложеност О (н 2 ) где је н укупан број ставки на листи. Сложеност времена мери број итерација потребних за сортирање листе. Листа је подељена на две партиције: Прва листа садржи сортиране ставке, док друга листа садржи неразврстане ставке.

Поређана листа је подразумевано празна, а несортирана листа садржи све елементе. Неразврстана листа се затим скенира за минималну вредност, која се затим ставља на сортирану листу. Овај поступак се понавља све док се све вредности не упореде и сортирају.

У овом упутству из алгоритма научићете:

  • Шта је сортирање избора?
  • Како функционише сортирање селекције?
  • Дефинисање проблема
  • Решење (алгоритам)
  • Визуелни приказ
  • Програм сортирања избора помоћу Питхона 3
  • Објашњење кода
  • Сложеност времена сортирања избора
  • Када користити сортирање избора?
  • Предности сортирања избора
  • Мане сортирања избора

Како функционише сортирање селекције?

Прва ставка на неразврстаној партицији упоређује се са свим вредностима на десној страни да би се проверило да ли је то минимална вредност. Ако то није минимална вредност, тада се њен положај замењује минималном вредношћу.

Пример:

  • На пример, ако је индекс минималне вредности 3, тада се вредност елемента са индексом 3 поставља на индекс 0, док се вредност која је била на индексу 0 ставља на индекс 3. Ако је први елемент у несортованој партицији минималну вредност, а затим враћа своје позиције.
  • Затим се елемент који је одређен као минимална вредност премешта на партицију на левој страни, а то је сортирана листа.
  • Партиционирана страна сада има један елемент, док непартиционирана страна има (н - 1) елементе где је н укупан број елемената на листи. Овај поступак се понавља изнова и изнова док се све ставке не упореде и сортирају на основу њихових вредности.

Дефинисање проблема

Списак елемената који су насумичним редоследом потребно је сортирати у растућем редоследу. Размотрите следећу листу као пример.

[21,6,9,33,3]

Горњу листу треба сортирати да би се добили следећи резултати

[3,6,9,21,33]

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

Корак 1) Добијте вредност н која је укупна величина низа

Корак 2) Поделите листу на сортиране и несортиране одељке. Сортирани одељак је у почетку празан, а неразврстани одељак садржи целу листу

Корак 3) Изаберите најмању вредност из неподељеног одељка и ставите је у разврстани одељак.

Корак 4) Поновите поступак (н - 1) пута док се сви елементи на листи не сортирају.

Визуелни приказ

С обзиром на листу од пет елемената, следеће слике илуструју како алгоритам селекције сортирања прелази кроз вредности приликом њиховог сортирања.

Следећа слика приказује несортирану листу

Корак 1)

Прва вредност 21 се упоређује са осталим вредностима како би се проверило да ли је то минимална вредност.

3 је минимална вредност, па се позиције 21 и 3 замењују. Вредности са зеленом позадином представљају сортирану партицију листе.

Корак 2)

Вредност 6 која је први елемент на несортованој партицији упоређује се са остатком вредности да би се утврдило постоји ли нижа вредност

Вредност 6 је минимална вредност, тако да задржава свој положај.

Корак 3)

Први елемент несортиране листе са вредношћу 9 упоређује се са осталим вредностима како би се проверило да ли је то минимална вредност.

Вредност 9 је минимална вредност, тако да задржава свој положај у разврстаној партицији.

Корак 4)

Вредност 33 се упоређује са осталим вредностима.

Вредност 21 је нижа од 33, па се позиције замењују како би се добила горња нова листа.

Корак 5)

На неподељеној листи нам је остала само једна вредност. Стога је већ сортирано.

Коначна листа је попут оне приказане на горњој слици.

Програм сортирања избора помоћу Питхона 3

Следећи код приказује имплементацију сортирања избора користећи Питхон 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]

Објашњење кода

Објашњење кода је следеће

Ево објашњења кода:

  1. Дефинише функцију која се зове селецтионСорт
  2. Добија укупан број елемената на листи. То нам је потребно да бисмо одредили број пролаза који треба извршити приликом упоређивања вредности.
  3. Спољна петља. Користи петљу за итирање кроз вредности листе. Број итерација је (н - 1). Вредност н је 5, па нам (5 - 1) даје 4. То значи да ће се спољне итерације извршити 4 пута. У свакој итерацији вредност променљиве и додељује се променљивој минВалуеИндек
  4. Унутрашња петља. Користи петљу за поређење крајње леве вредности са осталим вредностима на десној страни. Међутим, вредност за ј не почиње са индексом 0. Почиње са (и + 1). Ово искључује вредности које су већ сортиране тако да се фокусирамо на ставке које још нису сортиране.
  5. Проналази минималну вредност на несортованој листи и поставља је на прави положај
  6. Ажурира вредност минВалуеИндек када је услов замене тачан
  7. Упоређује вредности индексних бројева минВалуеИндек и и да би се утврдило да ли су једнаке
  8. Крајња лева вредност је ускладиштена у временској променљивој
  9. Доња вредност са десне стране заузима положај првог положаја
  10. Вредност која је била ускладиштена у привременој вредности чува се у положају који је претходно заузимала минимална вредност
  11. Приказује сортирану листу као резултат функције
  12. Ствара списак који има случајне бројеве
  13. Одштампајте сортирану листу након што позовете функцију Сортирање која се као параметар предаје ел.

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

Сложеност сортирања користи се за изражавање броја времена извршавања потребних за сортирање листе. Имплементација има две петље.

Спољна петља која бира вредности једну по једну са листе извршава се н пута, где је н укупан број вредности на листи.

Унутрашња петља, која упоређује вредност из спољне петље са остатком вредности, такође се извршава н пута, где је н укупан број елемената на листи.

Стога је број извршења (н * н), који се такође може изразити као О (н 2 ).

Сорта избора има наиме три категорије сложености;

  • Најгори случај - овде је наведена листа у опадајућем редоследу. Алгоритам изводи максималан број извршавања који се изражава као [Биг-О] О (н 2 )
  • Најбољи случај - ово се дешава када је наведена листа већ сортирана. Алгоритам изводи минимални број извршавања који се изражава као [Биг-Омега] Ω (н 2 )
  • Просечан случај - ово се дешава када је листа насумичним редоследом. Просечна сложеност изражава се као [Биг-тхета] ⊝ (н 2 )

Сортирање избора има сложеност простора О (1) јер захтева једну временску променљиву која се користи за замену вредности.

Када користити сортирање избора?

Сортирање избора најбоље се користи када желите:

  • Морате сортирати малу листу предмета у растућем редоследу
  • Када су трошкови замене вредности незнатни
  • Такође се користи када треба да будете сигурни да су све вредности на листи означене.

Предности сортирања избора

Следе предности овог избора

  • На малим листама има врло добре резултате
  • То је алгоритам на месту. Не захтева пуно простора за сортирање. За задржавање временске променљиве потребан је само један додатни простор.
  • Добро се изводи на ставкама које су већ сортиране.

Мане сортирања избора

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

  • Лоше се сналази када ради на огромним листама.
  • Број понављања извршених током сортирања је н-квадрат, где је н укупан број елемената на листи.
  • Остали алгоритми, попут брзог сортирања, имају боље перформансе у поређењу са сортирањем избора.

Резиме:

  • Сортирање избора је алгоритам за поређење на месту који се користи за сортирање случајне листе у уређену листу. Има временску сложеност од О (н 2 )
  • Листа је подељена у два одељка, сортирана и несортирана. Минимална вредност се бира из несортираног одељка и ставља у сортирани одељак.
  • Ова ствар се понавља све док се сви предмети не сортирају.
  • Имплементација псеудокода у Питхон 3 укључује употребу две фор петље и изјаве да ли је потребно заменити
  • Сложеност времена мери број корака потребних за сортирање листе.
  • Сложеност времена у најгорем случају се дешава када је листа у опадајућем редоследу. Има временску сложеност од [Биг-О] О (н 2 )
  • Сложеност времена у најбољем случају се дешава када је листа већ у растућем редоследу. Има временску сложеност од [Биг-Омега] Ω (н 2 )
  • Сложеност времена у просечном случају се дешава када је листа насумичним редоследом. Има временску сложеност од [Биг-тхета] ⊝ (н 2 )
  • Сортирање избора најбоље се користи када имате малу листу предмета за сортирање, трошкови замене вредности нису битни, а провера свих вредности је обавезна.
  • Сорта избора не даје добар учинак на огромним листама
  • Остали алгоритми за сортирање, као што је брзи сортирање, имају боље перформансе у поређењу са сортирањем избора.