Atlases kārtošana: Algoritms izskaidrots ar Python koda piemēru

Satura rādītājs:

Anonim

Kas ir atlases kārtošana?

SELECTION SORT ir salīdzināšanas šķirošanas algoritms, ko izmanto, lai kārtotu nejaušus priekšmetu sarakstus augošā secībā. Salīdzinājums neprasa daudz papildu vietas. Laika mainīgajam ir nepieciešama tikai viena papildu atmiņas vieta.

To sauc par šķirošanu uz vietas . Atlases kārtošanai ir laika sarežģītība O (n 2 ), kur n ir kopējais vienību skaits sarakstā. Laika sarežģītība mēra atkārtojumu skaitu, kas nepieciešams saraksta kārtošanai. Saraksts ir sadalīts divās nodalījumos: Pirmajā sarakstā ir sakārtoti vienumi, bet otrajā - nešķiroti vienumi.

Pēc noklusējuma sakārtotais saraksts ir tukšs, un nešķirotajā sarakstā ir visi elementi. Pēc tam nešķiroto sarakstu skenē pēc minimālās vērtības, kas pēc tam tiek ievietota sakārtotajā sarakstā. Šis process tiek atkārtots, līdz visas vērtības ir salīdzinātas un sakārtotas.

Šajā algoritma apmācībā jūs uzzināsiet:

  • Kas ir atlases kārtošana?
  • Kā notiek atlases kārtošana?
  • Problēmas definīcija
  • Risinājums (algoritms)
  • Vizuālā pārstāvība
  • Atlases kārtošanas programma, izmantojot Python 3
  • Kods Paskaidrojums
  • Atlases kārtošanas laika sarežģītība
  • Kad izmantot atlases kārtošanu?
  • Atlases šķirošanas priekšrocības
  • Atlases šķirošanas trūkumi

Kā notiek atlases kārtošana?

Pirmais nešķirotā nodalījuma elements tiek salīdzināts ar visām vērtībām labajā pusē, lai pārbaudītu, vai tā ir minimālā vērtība. Ja tā nav minimālā vērtība, tā pozīcija tiek aizstāta ar minimālo vērtību.

Piemērs:

  • Piemēram, ja minimālās vērtības indekss ir 3, tad elementa ar indeksu 3 vērtība tiek ievietota indeksā 0, bet vērtība, kas bija indeksā 0, tiek ievietota indeksā 3. Ja pirmais nešķirotā nodalījuma elements ir minimālo vērtību, tad tā atgriež savas pozīcijas.
  • Pēc tam elements, kas noteikts kā minimālā vērtība, tiek pārvietots uz nodalījumu kreisajā pusē, kas ir sakārtots saraksts.
  • Sadalītajā pusē tagad ir viens elements, bet nedalītajā pusē ir (n - 1) elementi, kur n ir kopējais elementu skaits sarakstā. Šis process tiek atkārtots atkal un atkal, līdz visi vienumi ir salīdzināti un sakārtoti, pamatojoties uz to vērtībām.

Problēmas definīcija

Elementu saraksts, kas ir nejaušā secībā, jāsakārto augošā secībā. Apsveriet šādu piemēru kā piemēru.

[21,6,9,33,3]

Iepriekš minētais saraksts ir jāšķiro, lai iegūtu šādus rezultātus

[3,6,9,21,33]

Risinājums (algoritms)

1. solis. Iegūstiet vērtību n, kas ir masīva kopējais lielums

2. solis) Sadaliet sarakstu sakārtotās un nešķirotās sadaļās. Kārtotā sadaļa sākotnēji ir tukša, savukārt nešķirotajā sadaļā ir viss saraksts

3. solis. Izvēlieties minimālo vērtību no nedalītās sadaļas un ievietojiet to šķirotajā sadaļā.

4. darbība. Atkārtojiet procesu (n - 1) reizes, līdz visi saraksta elementi ir sakārtoti.

Vizuālā pārstāvība

Ņemot vērā piecu elementu sarakstu, šie attēli parāda, kā atlases kārtošanas algoritms atkārtojas vērtībās, tos šķirojot.

Šis attēls parāda nešķiroto sarakstu

1. darbība)

Pirmo vērtību 21 salīdzina ar pārējām vērtībām, lai pārbaudītu, vai tā ir minimālā vērtība.

3 ir minimālā vērtība, tāpēc 21 un 3 pozīcijas tiek apmainītas. Vērtības ar zaļu fonu attēlo sarindoto saraksta nodalījumu.

2. solis)

Vērtību 6, kas ir pirmais nešķirotā nodalījuma elements, salīdzina ar pārējām vērtībām, lai uzzinātu, vai pastāv zemāka vērtība

6. vērtība ir minimālā vērtība, tāpēc tā saglabā savu pozīciju.

3. solis)

Nešķirotā saraksta pirmais elements ar vērtību 9 tiek salīdzināts ar pārējām vērtībām, lai pārbaudītu, vai tā ir minimālā vērtība.

9. vērtība ir minimālā vērtība, tāpēc tā saglabā savu pozīciju šķirotajā nodalījumā.

4. solis)

Vērtība 33 tiek salīdzināta ar pārējām vērtībām.

Vērtība 21 ir zemāka par 33, tāpēc pozīcijas tiek mainītas, lai izveidotu iepriekš minēto jauno sarakstu.

5. solis)

Nesadalītā sarakstā mums ir palikusi tikai viena vērtība. Tāpēc tas jau ir sakārtots.

Galīgais saraksts ir tāds pats kā parādīts augšējā attēlā.

Atlases kārtošanas programma, izmantojot Python 3

Šis kods parāda atlases kārtošanas ieviešanu, izmantojot 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))

Palaist iepriekš minēto kodu rada šādus rezultātus

[3, 6, 9, 21, 33]

Kods Paskaidrojums

Kods ir izskaidrots šādi

Šeit ir koda skaidrojums:

  1. Definē funkciju ar nosaukumu selectSort
  2. Tiek iegūts kopējais elementu skaits sarakstā. Mums tas ir nepieciešams, lai noteiktu veicamo caurbraukšanas reižu skaitu, salīdzinot vērtības.
  3. Ārējā cilpa. Izmanto cilpu, lai atkārtotu saraksta vērtības. Atkārtojumu skaits ir (n - 1). N vērtība ir 5, tāpēc (5 - 1) dod mums 4. Tas nozīmē, ka ārējās iterācijas tiks veiktas 4 reizes. Katrā atkārtojumā mainīgā i vērtība tiek piešķirta mainīgajam minValueIndex
  4. Iekšējā cilpa. Izmanto cilpu, lai salīdzinātu kreiso vērtību ar citām vērtībām labajā pusē. Tomēr j vērtība nesākas ar indeksu 0. Tā sākas ar (i + 1). Tas izslēdz vērtības, kas jau ir sakārtotas tā, lai mēs koncentrētos uz vienumiem, kas vēl nav kārtoti.
  5. Nešķirotajā sarakstā atrod minimālo vērtību un ievieto to pareizajā pozīcijā
  6. Atjaunina minValueIndex vērtību, kad mainīšanas nosacījums ir patiess
  7. Salīdzina indeksu skaitļu minValueIndex un i vērtības, lai redzētu, vai tās nav vienādas
  8. Kreisākā vērtība tiek saglabāta laika mainīgajā
  9. Zemākā vērtība no labās puses ieņem pirmo pozīciju
  10. Laika vērtībā saglabātā vērtība tiek saglabāta pozīcijā, kuru iepriekš turēja minimālā vērtība
  11. Atgriež sakārtoto sarakstu kā funkcijas rezultātu
  12. Izveido sarakstu el, kuram ir nejauši skaitļi
  13. Drukājiet sakārtoto sarakstu pēc tam, kad izsaukāt atlases funkciju Kārtot, kā parametrs ievadot el.

Atlases kārtošanas laika sarežģītība

Kārtošanas sarežģītība tiek izmantota, lai izteiktu izpildes reižu skaitu, kas nepieciešams saraksta kārtošanai. Īstenošanai ir divas cilpas.

Ārējā cilpa, kas pa vienam izvēlas vērtības no saraksta, tiek izpildīta n reizes, kur n ir kopējais vērtību skaits sarakstā.

Iekšējā cilpa, kas salīdzina ārējās cilpas vērtību ar pārējām vērtībām, tiek izpildīta arī n reizes, kur n ir kopējais elementu skaits sarakstā.

Tāpēc izpildījumu skaits ir (n * n), ko var izteikt arī kā O (n 2 ).

Atlases kārtībai ir trīs sarežģītības kategorijas, proti;

  • Sliktākais gadījums - šeit sniegtais saraksts ir dilstošā secībā. Algoritms izpilda maksimālo izpildījumu skaitu, kas izteikts kā [Big-O] O (n 2 )
  • Labākais gadījums - tas notiek, kad sniegtais saraksts jau ir sakārtots. Algoritms veic minimālo izpildījumu skaitu, kas izteikts kā [Big-Omega] Ω (n 2 )
  • Vidējais gadījums - tas notiek, ja saraksts ir nejaušā secībā. Vidējo sarežģītību izsaka kā [Big-theta] ⊝ (n 2 )

Atlases kārtošanai ir telpas sarežģītība O (1), jo tas prasa vienu laika mainīgo, ko izmanto vērtību maiņai.

Kad izmantot atlases kārtošanu?

Atlases kārtošanu vislabāk izmantot, ja vēlaties:

  • Jums jāšķiro neliels vienumu saraksts augošā secībā
  • Kad vērtību maiņas izmaksas ir nenozīmīgas
  • To lieto arī tad, kad jāpārliecinās, vai ir pārbaudītas visas saraksta vērtības.

Atlases šķirošanas priekšrocības

Šīs ir atlases kārtošanas priekšrocības

  • Tas darbojas ļoti labi mazos sarakstos
  • Tas ir vietējs algoritms. Šķirošanai tas neprasa daudz vietas. Laika mainīgā turēšanai ir nepieciešama tikai viena papildu vieta.
  • Tas labi darbojas jau sakārtotajos priekšmetos.

Atlases šķirošanas trūkumi

Šie ir atlases kārtošanas trūkumi.

  • Strādājot pie milzīgiem sarakstiem, tas darbojas slikti.
  • Šķirošanas laikā veikto atkārtojumu skaits ir n kvadrātā, kur n ir kopējais elementu skaits sarakstā.
  • Citiem algoritmiem, piemēram, ātrsortam, ir labāka veiktspēja salīdzinājumā ar atlases kārtošanu.

Kopsavilkums:

  • Atlases kārtošana ir salīdzināšanas algoritms, kas tiek izmantots, lai nejaušo sarakstu kārtotu sakārtotā sarakstā. Tam ir laika sarežģītība O (n 2 )
  • Saraksts ir sadalīts divās sadaļās, sakārtotas un nešķirotas. Minimālā vērtība tiek atlasīta no nešķirotās sadaļas un ievietota sakārtotajā sadaļā.
  • Šī lieta tiek atkārtota, līdz visi vienumi ir sakārtoti.
  • Pseidokoda ieviešana Python 3 ietver divu izmantošanu cilpām un paziņojumus, lai pārbaudītu, vai ir nepieciešama maiņa
  • Laika sarežģītība nosaka to darbību skaitu, kas nepieciešamas saraksta kārtošanai.
  • Sliktākā laika sarežģītība notiek, ja saraksts ir dilstošā secībā. Laika sarežģītība ir [Big-O] O (n 2 )
  • Labākā laika sarežģītība notiek, kad saraksts jau ir augošā secībā. Laika sarežģītība ir [Big-Omega] Ω (n 2 )
  • Laika sarežģītība vidēji notiek, ja saraksts ir nejaušā secībā. Laika sarežģītība ir [Big-theta] ⊝ (n 2 )
  • Atlases kārtošanu vislabāk izmantot, ja jums ir neliels kārtoamo vienumu saraksts, vērtību maiņas izmaksām nav nozīmes, un visu vērtību pārbaude ir obligāta.
  • Atlases kārtošana nedarbojas labi milzīgos sarakstos
  • Citiem šķirošanas algoritmiem, piemēram, ātrsortam, ir labāka veiktspēja, salīdzinot ar atlases kārtošanu.