Kijelölés rendezése: Az algoritmus magyarázata a Python Kódpélda

Mi az a kijelölés rendezése?

VÁLASZTÁSI VÁLASZTÁS egy összehasonlító rendezési algoritmus, amely az elemek véletlenszerű listájának növekvő sorrendbe rendezésére szolgál. Az összehasonlítás nem igényel sok extra helyet. Csak egy extra memóriaterületet igényel az időbeli változóhoz.

Ezt úgy ismerjük, mint a helyén osztályozás. A kiválasztási rendezés időbeli összetettsége O(n²) ahol n a lista elemeinek teljes száma. Az időbonyolultság a lista rendezéséhez szükséges iterációk számát méri. A lista két részre oszlik: Az első lista rendezett elemeket tartalmaz, míg a második lista a rendezetlen elemeket.

Alapértelmezés szerint a rendezett lista üres, a rendezetlen lista pedig az összes elemet tartalmazza. A rendezetlen listát ezután a rendszer átvizsgálja a minimális értékre, amely ezután bekerül a rendezett listába. Ezt a folyamatot addig ismételjük, amíg az összes értéket össze nem hasonlítjuk és rendezzük.

Hogyan működik a kiválasztási rendezés?

A rendezetlen partíció első elemét a rendszer összehasonlítja a jobb oldalon lévő összes értékkel, hogy ellenőrizze, hogy ez-e a minimális érték. Ha nem a minimális érték, akkor a pozíciója felcserélődik 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 indexbe kerül, míg a 0 indexű érték a 3. indexbe kerül. Ha a rendezetlen 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 átkerül a bal oldali partícióra, amely a rendezett lista.
A particionált oldal most egy elemet tartalmaz, míg a nem particionált oldal (n – 1) elemet tartalmaz, ahol n a lista összes elemének száma. Ez a folyamat újra és újra megismétlődik, amíg az összes elemet össze nem hasonlítják és az értékek alapján rendezik.

Probléma meghatározás

A véletlenszerű sorrendben lévő elemek listáját növekvő sorrendbe kell rendezni. Tekintsük példaként a következő listát.

[21,6,9,33,3]

A fenti listát rendezni kell a következő eredmények eléréséhez

[3,6,9,21,33]

Megoldás (algoritmus)

Step 1) Kapja meg n értékét, amely a tömb teljes mérete

Step 2) Ossza fel a listát rendezett és rendezetlen szakaszokra. A rendezett szakasz kezdetben üres, míg a rendezetlen szakasz a teljes listát tartalmazza

Step 3) Válassza ki a minimális értéket a particionálatlan szakaszból, és helyezze a rendezett szakaszba.

Step 4) Ismételje meg a folyamatot (n – 1) mindaddig, amíg a lista összes eleme nem rendeződik.

Vizuális ábrázolás

Egy öt elemből álló lista alapján a következő képek szemléltetik, hogy a kiválasztási rendezési algoritmus hogyan iterál az értékeken a rendezés során.

A következő kép a rendezetlen listát mutatja

Step 1)

Az első 21 értéket a rendszer összehasonlítja a többi értékkel annak ellenőrzésére, hogy ez a minimális érték.

A 3 a minimális érték, így a 21 és a 3 pozíciója felcserélődik. A zöld hátterű értékek a lista rendezett partícióját jelentik.

Step 2)

A 6-os értéket, amely a rendezetlen partíció első eleme, a rendszer összehasonlítja a többi értékkel, hogy megtudja, létezik-e alacsonyabb érték

A 6-os érték a minimális érték, tehát megtartja pozícióját.

Step 3)

A rendezetlen lista első, 9-es értékű elemét a rendszer összehasonlítja a többi értékkel annak ellenőrzésére, hogy ez a minimális érték.

A 9-es érték a minimális érték, tehát megtartja pozícióját a rendezett partícióban.

Step 4)

A 33-as értéket a rendszer összehasonlítja a többi értékkel.

A 21 érték kisebb, mint 33, ezért a pozíciók felcserélődnek a fenti új lista létrehozásához.

Step 5)

Már csak egy értékünk maradt a fel nem particionált listában. Ezért már rendezve van.

A végső lista olyan, mint a fenti képen látható.

Kiválasztás Program rendezése segítségével Python 3

A következő kód a kiválasztási rendezés megvalósítását mutatja be Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

A fenti kód futtatása a következő eredményeket produkálja

[3, 6, 9, 21, 33]

Kód Magyarázat

A kód magyarázata a következő

Íme a kód magyarázata:

Meghatározza a selectionSort nevű függvényt
Lekéri a lista elemeinek teljes számát. Erre azért van szükségünk, hogy meghatározzuk az értékek összehasonlításakor végrehajtandó lépések számát.
Külső hurok. A ciklust használja a lista értékei közötti iterációhoz. 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 4-szer hajtjuk végre. Minden iterációban az i változó értéke a minValueIndex változóhoz van rendelve
Belső hurok. A ciklus segítségével összehasonlítja a bal szélső értéket a jobb oldalon lévő többi értékkel. A j értéke azonban nem a 0 indexnél kezdődik, hanem (i + 1) értékkel kezdődik. Ez kizárja a már rendezett értékeket, így a még nem rendezett tételekre összpontosítunk.
Megkeresi a minimális értéket a rendezetlen 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 az i indexszámok értékeit, hogy megnézze, nem egyenlőek-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 pozícióban kerül tárolásra, amelyet korábban a minimális érték tartott
A rendezett listát adja vissza függvény eredményeként
Létrehoz egy listát, amely véletlen számokat tartalmaz
Nyomtassa ki a rendezett listát az el paraméterként átadó Sort függvény meghívása után.

A kiválasztási rendezés időbeli összetettsége

A rendezés bonyolultsága a lista rendezéséhez szükséges végrehajtási idők számának kifejezésére szolgál. A megvalósítás két hurokból áll.

A külső ciklus, amely egyesével kiválasztja az értékeket a listából, n-szer kerül végrehajtásra, ahol n a lista összes értékének száma.

A belső ciklus, amely összehasonlítja a külső ciklus értékét a többi értékkel, szintén n-szer kerül végrehajtásra, ahol n a lista elemeinek teljes száma.

Ezért a végrehajtások száma (n * n), ami O(n)-ként is kifejezhető²).

A kiválasztási rendezésnek három összetettségi kategóriája van, nevezetesen;

Legrosszabb esetben – itt van a megadott lista csökkenő sorrendben. Az algoritmus a maximális számú végrehajtást hajtja végre, amelyet [Big-O] O(n²)
Legjobb eset – ez akkor fordul elő, ha a megadott lista már rendezve van. Az algoritmus a minimális számú végrehajtást hajtja végre, amelyet [Big-Omega] ?(n)²)
Átlagos eset – ez akkor fordul elő, ha a lista véletlenszerű sorrendben van. Az átlagos komplexitást [Big-theta] ?(n²)

A kiválasztási rendezés O(1) térbeli komplexitással rendelkezik, mivel egy időbeli változót igényel az értékek felcseréléséhez.

Mikor kell kiválasztani a rendezést?

A kiválasztási rendezést akkor célszerű használni, ha:

A tételek kis listáját növekvő sorrendbe kell rendeznie
Amikor az értékcsere költsége jelentéktelen
Akkor is használatos, ha meg kell győződnie arról, hogy a listában szereplő összes érték ellenőrzése megtörtént.

A Selection Sort előnyei

Az alábbiakban bemutatjuk a kiválasztási rendezés előnyeit

Kis listákon nagyon jól teljesít
Ez egy beépített algoritmus. Nem igényel sok helyet a válogatáshoz. Csak egy extra szóköz szükséges az időbeli változó tárolásához.
Jól teljesít a már rendezett tételeken.

A Selection Sort hátrányai

Az alábbiakban felsoroljuk a kiválasztási rendezés hátrányait.

Hatalmas listákon dolgozva rosszul teljesít.
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, mint például a gyors rendezés, jobb teljesítményt nyújtanak a kiválasztási rendezéshez képest.

Összegzésként

A kijelölési rendezés egy helyben alkalmazott összehasonlító algoritmus, amely véletlenszerű listák rendezett listává történő rendezésére szolgál. Időbonyolultsága O(n²)
A lista két részre oszlik, rendezett és rendezetlen. A minimális értéket a rendszer a rendezetlen szakaszból választja ki, és a rendezett szakaszba helyezi.
Ezt addig ismételjük, amíg az összes elemet el nem rendeztük.
A pszeudokód implementálása in Python A 3 két for ciklus és if utasítások használatát foglalja magában annak ellenőrzésére, hogy szükséges-e a csere
Az időbonyolultság a lista rendezéséhez szükséges lépések számát méri.
A legrosszabb eset bonyolultsága akkor fordul elő, ha a lista csökkenő sorrendben van. Időbonyolultsága [Big-O] O(n²)
A legjobb esetben az időbonyolítás akkor következik be, amikor a lista már növekvő sorrendben van. Időbeli összetettsége [Big-Omega] ?(n²)
Az esetek átlagos összetettsége akkor következik be, ha a lista véletlenszerű sorrendben van. Időbeli összetettsége [Big-theta] ?(n²)
A kijelölési rendezést akkor célszerű használni, ha van egy kis listája a rendezendő elemeknek, 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 rendezés nem teljesít jól hatalmas listákon
Más rendezési algoritmusok, például a gyorsrendezés, jobb teljesítményt nyújtanak a kiválasztási rendezéshez képest.