Mi a Selection Sort?
A SELECTION SORT egy összehasonlító rendezési algoritmus, amelyet az elemek véletlenszerű listájának növekvő sorrendben történő rendezésére használnak. Az összehasonlítás nem igényel sok extra helyet. Csak egy extra memóriahely szükséges az időbeli változó számára.
Ez a helyszíni válogatás néven ismert . A kiválasztási sorrend időbeli összetettsége O (n 2 ), ahol n a lista összes elemének száma. Az idő bonyolultsága méri a lista rendezéséhez szükséges iterációk számát. A lista két partícióra oszlik: Az első lista rendezett elemeket tartalmaz, míg a második nem rendezett elemeket.
Alapértelmezés szerint a rendezett lista üres, és a rendezetlen lista tartalmazza az összes elemet. A rendezetlen listát ezután megvizsgálja a minimális értékre, amelyet azután a rendezett listába helyez. Ezt a folyamatot addig ismételjük, amíg az összes értéket össze nem hasonlítják és rendezik.
Ebben az algoritmus oktatóanyagban megtudhatja:
- Mi a Selection Sort?
- Hogyan működik a kiválasztás rendezése?
- Probléma meghatározás
- Megoldás (algoritmus)
- Vizuális ábrázolás
- Program kiválasztása a Python 3 használatával
- Kód Magyarázat
- A kiválasztás rendezésének időbeli összetettsége
- Mikor kell használni a kijelölés rendezését?
- A Selection Sort előnyei
- A kiválasztás rendezésének hátrányai
Hogyan működik a kiválasztás rendezése?
A nem rendezett partíció első elemét összehasonlítjuk a jobb oldali összes értékkel, hogy ellenőrizzük, ez-e a minimális érték. Ha ez nem a minimális érték, akkor a helyét felcseréljük a minimális értékkel.
Példa:
- Például, ha a minimális érték indexe 3, akkor a 3 indexű elem értéke a 0 indexre kerül, míg a 0 indexen lévő érték a 3. indexre kerül. Ha a nem rendezett partíció első eleme a minimális értéket, akkor visszaadja pozícióit.
- A minimális értékként meghatározott elem ezután a bal oldali partícióra kerül, amely a rendezett lista.
- A particionált oldalon most egy elem van, míg a fel nem osztott oldalon (n - 1) elem van, ahol n a lista összes elemének száma. Ezt a folyamatot addig ismételjük, amíg az összes elemet összehasonlítják és rendezik az értékük alapján.
Probléma meghatározás
A véletlenszerű sorrendben szereplő elemek listáját növekvő sorrendben kell rendezni. Tekintsük példaként az alábbi listát.
[21,6,9,33,3]
A fenti listát a következő eredmények elérése érdekében kell rendezni
[3,6,9,21,33]
Megoldás (algoritmus)
1. lépés: Szerezze meg n értékét, amely a tömb teljes mérete
2. lépés: Ossza fel a listát rendezett és rendezetlen szakaszokra. A rendezett szakasz kezdetben üres, míg a nem rendezett szakasz a teljes listát tartalmazza
3. lépés: Válassza ki a minimális értéket a fel nem osztott szakaszból, és helyezze a rendezett szakaszba.
4. lépés: Ismételje meg az eljárást (n - 1), amíg a lista összes eleme rendeződik.
Vizuális ábrázolás
Öt elemből álló listát adva a következő képek szemléltetik, hogy a szelekció rendezési algoritmus hogyan válogat végig az értékeken rendezéskor.
A következő kép a nem rendezett listát mutatja
1. lépés)
Az első 21 értéket összehasonlítjuk a többi értékkel annak ellenőrzésére, hogy ez a minimális érték-e.
A 3 a minimális érték, így a 21 és 3 pozíciók felcserélődnek. A zöld háttérrel rendelkező értékek a lista rendezett partícióját képviselik.
2. lépés)
A rendezetlen partíció első elemének számító 6 értéket összehasonlítjuk a többi értékkel, hogy kiderüljön, létezik-e alacsonyabb érték
A 6-os érték a minimális érték, így megtartja helyzetét.
3. lépés)
A nem rendezett lista 9 elemű első elemét összehasonlítjuk a többi értékkel annak ellenőrzésére, hogy ez a minimális érték-e.
A 9-es érték a minimális érték, így megtartja pozícióját a rendezett partícióban.
4. lépés)
A 33. értéket összehasonlítjuk a többi értékkel.
A 21 érték alacsonyabb, mint 33, ezért a pozíciókat felcseréljük a fenti új lista előállításához.
5. lépés)
Csak egy érték maradt a fel nem osztott listában. Ezért már rendezve van.
A végleges lista megegyezik a fenti képen látható listával.
Program kiválasztása a Python 3 használatával
Az alábbi kód bemutatja a Python 3 használatával végrehajtott kiválasztási rendezés megvalósítását
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))
A fenti kód futtatása a következő eredményeket eredményezi
[3, 6, 9, 21, 33]
Kód Magyarázat
A kód magyarázata a következő
Itt van a kód magyarázata:
- Meghatározza a selectionSort nevű függvényt
- Megkapja a lista összes elemének számát. Erre szükségünk van az értékek összehasonlításakor elvégzendő áthaladások számának meghatározásához.
- Külső hurok. A ciklust használja a lista értékeinek átismételésére. Az iterációk száma (n - 1). N értéke 5, tehát (5 - 1) 4-et ad. Ez azt jelenti, hogy a külső iterációkat négyszer hajtjuk végre. Minden iterációban az i változó értékét a minValueIndex változóhoz rendeljük
- Belső hurok. A ciklus segítségével összehasonlítja a bal szélső értéket a jobb oldali többi értékkel. A j értéke azonban nem a 0. indexnél kezdődik. (I + 1) -nél kezdődik. Ez kizárja azokat az értékeket, amelyeket már rendezett, így olyan elemekre összpontosítunk, amelyeket még nem rendeztünk.
- Megkeresi a minimális értéket a nem rendezett listában, és a megfelelő pozícióba helyezi
- Frissíti a minValueIndex értékét, ha a cserefeltétel igaz
- Összehasonlítja a minValueIndex és i indexszámok értékét, hogy megnézze, nem egyeznek-e
- A bal szélső értéket egy időbeli változó tárolja
- A jobb oldali alsó érték az első pozíciót foglalja el
- Az időbeli értékben tárolt érték abban a helyzetben tárolódik, amelyet korábban a minimális érték tartott
- A rendezett listát adja vissza a függvény eredményeként
- Létrehoz egy el listát, amely véletlenszerű számokkal rendelkezik
- Nyomja meg a rendezett listát, miután meghívta a Selection Sort függvényt, amely paraméterként megadta az el-t.
A kiválasztás rendezésének időbeli összetettsége
A rendezés összetettségét használjuk a lista rendezéséhez szükséges végrehajtási idők számának kifejezésére. A megvalósítás két hurokkal rendelkezik.
A külső hurok, amely egyesével kiválasztja az értékeket a listából, n -szer végrehajtásra kerül, ahol n a lista összes értékének száma.
A belső hurok, amely összehasonlítja a külső hurok értékét a többi értékkel, szintén n -szer végrehajtásra kerül, ahol n a lista összes elemének száma.
Ezért a végrehajtások száma (n * n), amely O (n 2 ) -ként is kifejezhető .
A kiválasztási sorrendnek három összetettségi kategóriája van, nevezetesen;
- Legrosszabb esetben - itt a megadott lista csökkenő sorrendben van. Az algoritmus a végrehajtások maximális számát hajtja végre, amelyet [Big-O] O (n 2 ) formában fejeznek ki.
- Legjobb eset - ez akkor fordul elő, amikor a megadott lista már rendezve van. Az algoritmus végrehajtja a végrehajtások minimális számát, amelyet [Big-Omega] Ω (n 2 ) -ben fejezünk ki.
- Átlagos eset - ez akkor fordul elő, ha a lista véletlenszerű sorrendben van. Az átlagos komplexitást [Big-theta] ⊝ (n 2 ) -ként fejezzük ki.
A szelekciós rendezés térbeli összetettsége O (1), mivel ehhez egy időbeli változóra van szükség az értékek felcserélésére.
Mikor kell használni a kijelölés rendezését?
A választási sorrendet akkor lehet a legjobban használni, ha:
- Kis tételeket kell növekvő sorrendben rendezni
- Amikor az értékek cseréjének költsége jelentéktelen
- Akkor is használják, ha meg kell győződnie arról, hogy a lista összes értékét ellenőrizte.
A Selection Sort előnyei
A következők a kiválasztási rendezés előnyei
- Kis listákon nagyon jól teljesít
- Ez egy helyben alkalmazott algoritmus. A válogatáshoz nem kell sok hely. Csak egy extra hely szükséges az időbeli változó megtartásához.
- A már rendezett elemeken jól teljesít.
A kiválasztás rendezésének hátrányai
Az alábbiakban bemutatjuk a kiválasztási rend hátrányait.
- Rosszul teljesít, ha hatalmas listákon dolgozik.
- A rendezés során végrehajtott iterációk száma n négyzet, ahol n a lista összes elemének száma.
- Más algoritmusok, például a quicksort, jobb teljesítményt nyújtanak a kiválasztási rendezéshez képest.
Összegzés:
- A Selection sort egy helyben történő összehasonlító algoritmus, amelyet egy véletlenszerű lista rendezett listába rendezésére használnak. Időkomplexuma O (n 2 )
- A lista két szakaszra oszlik, rendezve és rendezetlenül. A minimális értéket a nem rendezett szakaszból választják ki, és a rendezett szakaszba helyezik.
- Ezt a dolgot addig ismételjük, amíg az összes elemet nem rendezik.
- Az álkód Python 3-ban való megvalósítása magában foglalja kettő használatát a ciklusokhoz és az utasításokat annak ellenőrzéséhez, hogy szükség van-e cserére
- Az idő bonyolultsága méri a lista rendezéséhez szükséges lépések számát.
- A legrosszabb esetben az idő bonyolultsága akkor következik be, ha a lista csökkenő sorrendben van. Időkomplexuma [Big-O] O (n 2 )
- A legjobb esetben az idő bonyolultsága akkor következik be, amikor a lista már növekvő sorrendben van. Időkomplexuma [Big-Omega] Ω (n 2 )
- Az átlagos eset-bonyolultság akkor fordul elő, ha a lista véletlenszerű sorrendben van. Időkomplexuma [Big-theta] ⊝ (n 2 )
- A kiválasztási rendezést akkor lehet a legjobban használni, ha van egy kis lista a rendezendő tételekről, az értékek cseréjének költsége nem számít, és az összes érték ellenőrzése kötelező.
- A kiválasztási sorrend hatalmas listákon nem teljesít jól
- Más rendezési algoritmusok, például a quicksort, jobb teljesítményt nyújtanak a kiválasztási rendezéshez képest.