Pasirinkimo rūšiavimas: algoritmas paaiškintas „Python“ kodo pavyzdžiu

Turinys:

Anonim

Kas yra atrankos rūšiavimas?

PASIRINKIMO RŪŠIAVIMAS yra palyginimo rūšiavimo algoritmas, naudojamas atsitiktiniam elementų sąrašui rūšiuoti didėjimo tvarka. Palyginimas nereikalauja daug papildomos vietos. Tam reikia tik vienos papildomos atminties vietos kintamajam.

Tai vadinama rūšiavimu vietoje . Pasirinkimo rūšiavimas turi laiko sudėtingumą O (n 2 ), kur n yra bendras elementų skaičius sąraše. Laiko sudėtingumas matuoja pakartojimų, reikalingų sąrašui rūšiuoti, skaičių. Sąrašas yra padalintas į dvi skaidinius: Pirmajame sąraše yra rūšiuojami elementai, o antrame - nerūšiuoti elementai.

Pagal numatytuosius nustatymus rūšiuojamas sąrašas yra tuščias, o nerūšiuotame sąraše yra visi elementai. Tada nerūšiuotas sąrašas nuskaito minimalią vertę, kuri tada įtraukiama į išrūšiuotą sąrašą. Šis procesas kartojamas tol, kol visos vertės bus palygintos ir surūšiuotos.

Šioje algoritmo pamokoje sužinosite:

  • Kas yra atrankos rūšiavimas?
  • Kaip vyksta atrankos rūšiavimas?
  • Problemos apibrėžimas
  • Sprendimas (algoritmas)
  • Vaizdinis vaizdavimas
  • Pasirinkimo rūšiavimo programa naudojant „Python 3“
  • Kodo paaiškinimas
  • Pasirinkimo rūšiavimo laiko sudėtingumas
  • Kada naudoti pasirinkimo rūšiavimą?
  • Pasirinkimo rūšiavimo pranašumai
  • Pasirinkimo rūšiavimo trūkumai

Kaip vyksta atrankos rūšiavimas?

Pirmasis nesurūšiuoto skaidinio elementas palyginamas su visomis reikšmėmis dešinėje pusėje, kad būtų patikrinta, ar ji yra mažiausia vertė. Jei tai nėra minimali vertė, tada jos padėtis keičiama su mažiausiąja.

Pavyzdys:

  • Pvz., Jei mažiausios vertės indeksas yra 3, tada elemento su indeksu 3 vertė yra 0, o 0 indekso vertė - 3 indekso. Jei pirmasis nerūšiuoto skaidinio elementas yra minimalią vertę, tada ji grąžina savo pozicijas.
  • Tada elementas, kuris buvo nustatytas kaip minimali vertė, perkeliamas į skaidinį kairėje pusėje, kuris yra rūšiuojamas sąrašas.
  • Pertvarkytoje pusėje dabar yra vienas elementas, o neskaidytoje pusėje yra (n - 1) elementų, kur n yra bendras elementų skaičius sąraše. Šis procesas kartojamas dar kartą, kol visi elementai bus palyginti ir surūšiuoti pagal jų vertes.

Problemos apibrėžimas

Elementų, kurie yra atsitiktine tvarka, sąrašą reikia surikiuoti didėjimo tvarka. Apsvarstykite šį sąrašą kaip pavyzdį.

[21,6,9,33,3]

Aukščiau pateiktas sąrašas turėtų būti rūšiuojamas taip, kad būtų gauti šie rezultatai

[3,6,9,21,33]

Sprendimas (algoritmas)

1 žingsnis. Gaukite n reikšmę, kuri yra bendras masyvo dydis

2 žingsnis) Padalykite sąrašą į rūšiuojamas ir nerūšiuotas dalis. Rūšiuota skiltis iš pradžių tuščia, o nerūšiuotoje skiltyje yra visas sąrašas

3 žingsnis) Pasirinkite mažiausią vertę iš neskirstyto skyriaus ir padėkite ją į rūšiuojamą skyrių.

4 žingsnis. Pakartokite procesą (n - 1), kol visi sąrašo elementai bus surūšiuoti.

Vaizdinis vaizdavimas

Pateikiant penkių elementų sąrašą, šie vaizdai iliustruoja, kaip atrankos rūšiavimo algoritmas kartojasi per vertes jas rūšiuojant.

Šiame paveikslėlyje rodomas nerūšiuotas sąrašas

1 žingsnis)

Pirmoji reikšmė 21 palyginama su kitomis reikšmėmis, siekiant patikrinti, ar ji yra mažiausia reikšmė.

3 yra minimali vertė, todėl 21 ir 3 pozicijos keičiamos. Vertės su žaliu fonu nurodo surūšiuotą sąrašo skaidinį.

2 žingsnis)

6 reikšmė, kuri yra pirmasis nerūšiuoto skaidinio elementas, palyginama su kitomis reikšmėmis, kad sužinotumėte, ar yra mažesnė vertė

6 vertė yra mažiausia vertė, todėl ji išlaiko savo poziciją.

3 žingsnis)

Pirmasis nesurūšiuoto sąrašo elementas, kurio vertė 9, palyginamas su kitomis reikšmėmis, kad būtų patikrinta, ar tai yra mažiausia vertė.

9 reikšmė yra mažiausia vertė, todėl ji išlaiko savo vietą išrūšiuotame skaidinyje.

4 žingsnis)

33 vertė lyginama su kitomis reikšmėmis.

21 vertė yra mažesnė nei 33, todėl pozicijos keičiamos, kad būtų pateiktas aukščiau pateiktas naujas sąrašas.

5 žingsnis)

Neskirstytame sąraše turime tik vieną vertę. Todėl jis jau yra rūšiuojamas.

Galutinis sąrašas yra panašus į pateiktą aukščiau esančiame paveikslėlyje.

Pasirinkimo rūšiavimo programa naudojant „Python 3“

Šis kodas rodo pasirinkimo rūšiavimo įgyvendinimą naudojant „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))

Vykdydami pirmiau pateiktą kodą gaunami šie rezultatai

[3, 6, 9, 21, 33]

Kodo paaiškinimas

Kodo paaiškinimas yra toks

Čia yra kodo paaiškinimas:

  1. Apibrėžia funkciją, pavadintą selectSort
  2. Gauna bendrą sąrašo elementų skaičių. Mums to reikia norint nustatyti pravažiavimų skaičių, lyginant vertes.
  3. Išorinė kilpa. Naudoja kilpą, kad pakartotų sąrašo reikšmes. Kartojimų skaičius yra (n - 1). N reikšmė yra 5, taigi (5 - 1) suteikia mums 4. Tai reiškia, kad išorinės iteracijos bus atliekamos 4 kartus. Kiekvienoje iteracijoje kintamojo i vertė priskiriama kintamajam minValueIndex
  4. Vidinė kilpa. Naudoja kilpą, kad palygintų kairiausią vertę su kitomis vertėmis dešinėje. Tačiau j reikšmė neprasideda nuo indekso 0. Ji prasideda nuo (i + 1). Tai neįtraukia jau išrūšiuotų reikšmių, kad sutelktume dėmesį į dar nerūšiuotus elementus.
  5. Randa nerūšiuotame sąraše mažiausią vertę ir padeda ją į tinkamą vietą
  6. Atnaujina minValueIndex vertę, kai sukeitimo sąlyga yra teisinga
  7. Palygina indeksų skaičių „minValueIndex“ ir „i“ vertes, kad pamatytumėte, ar jos nėra lygios
  8. Kairiausia vertė saugoma laikinajame kintamajame
  9. Apatinė vertė iš dešinės pusės užima pirmąją poziciją
  10. Vertė, kuri buvo laikoma laiko vertėje, saugoma pozicijoje, kurią anksčiau laikė minimali vertė
  11. Grąžina surūšiuotą sąrašą kaip funkcijos rezultatą
  12. Sukuria el. Sąrašą, kuriame yra atsitiktiniai skaičiai
  13. Atspausdinę išrūšiuotą sąrašą, paskambinę pasirinkimo rūšiavimo funkcijai, perduodama el kaip parametras.

Pasirinkimo rūšiavimo laiko sudėtingumas

Rūšiavimo sudėtingumas naudojamas išreikšti vykdymo kartų, reikalingų sąrašui rūšiuoti, skaičių. Įgyvendinimas turi dvi kilpas.

Išorinė kilpa, kuri po vieną surenka vertes iš sąrašo, vykdoma n kartus, kur n yra bendras reikšmių skaičius sąraše.

Vidinė kilpa, lyginanti išorinės kilpos vertę su kitomis reikšmėmis, taip pat vykdoma n kartų, kai n yra bendras sąrašo elementų skaičius.

Todėl egzekucijų skaičius yra (n * n), kuris taip pat gali būti išreikštas O (n 2 ).

Atrankos rūšis turi tris sudėtingumo kategorijas:

  • Blogiausias atvejis - čia pateikiamas sąrašas mažėjančia tvarka. Algoritmas atlieka maksimalų įvykdymų skaičių, kuris išreiškiamas kaip [Big-O] O (n 2 )
  • Geriausias atvejis - tai atsitinka, kai pateiktas sąrašas jau yra rūšiuojamas. Algoritmas atlieka mažiausią įvykdymų skaičių, kuris išreiškiamas [Big-Omega] Ω (n 2 )
  • Vidutinis atvejis - tai atsitinka, kai sąrašas yra atsitiktine tvarka. Vidutinis sudėtingumas išreiškiamas [didele-teta] ⊝ (n 2 )

Pasirinkimo rūšiavimo erdvės sudėtingumas yra O (1), nes tam reikalingas vienas laiko kintamasis, naudojamas reikšmėms sukeisti.

Kada naudoti pasirinkimo rūšiavimą?

Pasirinkimo rūšį geriausia naudoti, kai norite:

  • Turite rūšiuoti nedidelį prekių sąrašą didėjimo tvarka
  • Kai vertės keitimo kaina yra nereikšminga
  • Jis taip pat naudojamas, kai reikia įsitikinti, kad patikrintos visos sąrašo reikšmės.

Pasirinkimo rūšiavimo pranašumai

Toliau pateikiami atrankos rūšiavimo pranašumai

  • Tai labai gerai veikia mažuose sąrašuose
  • Tai vietoje esantis algoritmas. Tam nereikia daug vietos rūšiuoti. Laiko kintamajam laikyti reikia tik vienos papildomos vietos.
  • Tai gerai veikia jau išrūšiuotus daiktus.

Pasirinkimo rūšiavimo trūkumai

Toliau pateikiami atrankos rūšiavimo trūkumai.

  • Prastai veikia dirbant didžiuliuose sąrašuose.
  • Rūšiavimo metu atliktų iteracijų skaičius yra n kvadratas, kur n yra bendras elementų skaičius sąraše.
  • Kiti algoritmai, pvz., „Quicksort“, veikia geriau, palyginti su pasirinkimo rūšiu.

Santrauka:

  • Pasirinkimo rūšiavimas yra vietinis palyginimo algoritmas, naudojamas atsitiktiniam sąrašui rūšiuoti į sutvarkytą sąrašą. Tai laiko O (n 2 ) sudėtingumas
  • Sąrašas suskirstytas į dvi dalis, rūšiuojamas ir nerūšiuotas. Minimali vertė paimama iš nerūšiuoto skyriaus ir įtraukiama į išrūšiuotą skyrių.
  • Šis dalykas kartojamas tol, kol visi daiktai bus išrūšiuoti.
  • Įdiegus pseudokodą „Python 3“, reikia naudoti du kilpoms ir, jei sakiniai, norint patikrinti, ar reikia pakeisti
  • Laiko sudėtingumas matuoja žingsnių, reikalingų sąrašui rūšiuoti, skaičių.
  • Blogiausias laiko sudėtingumas įvyksta, kai sąrašas yra mažėjančia tvarka. Laiko sudėtingumas yra [Big-O] O (n 2 )
  • Geriausias laiko sudėtingumas įvyksta, kai sąrašas jau yra didėjimo tvarka. Laiko sudėtingumas yra [Big-Omega] Ω (n 2 )
  • Vidutinis laiko sudėtingumas įvyksta, kai sąrašas yra atsitiktine tvarka. Laiko sudėtingumas yra [Didžioji teta] ⊝ (n 2 )
  • Pasirinkimo rūšiavimą geriausia naudoti, kai turite nedidelį rūšiuotų elementų sąrašą, reikšmių keitimo kaina nesvarbi, o visų verčių tikrinimas yra privalomas.
  • Pasirinkimo rūšis nėra gerai naudojama didžiuliuose sąrašuose
  • Kiti rūšiavimo algoritmai, pvz., „Quicksort“, veikia geriau, palyginti su pasirinkimo rūšiavimu.