Kiválasztás Rendezés Java Program példával
James Hartman
⚡ Okos összefoglaló
Kijelölés rendezés szerint Java ismételten átvizsgálja egy tömb rendezetlen részét, megkeresi a legkisebb fennmaradó értéket, és azt a megfelelő helyre helyezi, legfeljebb n-1 cserével befejezve a munkát, függetlenül a bemeneti sorrendtől.
Hogyan működik a kijelölés rendezése?
A Selection Sort egy egyszerű rendezési algoritmust valósít meg az alábbiak szerint:
- Az algoritmus ismételten megkeresi a legalacsonyabb elemet.
- Cserélje ki az aktuális elemet a legalacsonyabb értékű elemre
- A kiválasztási rendezés minden iterációja/passzolása során az elemek felcserélődnek.
Minden menet tehát kezeli a sor két régióként van csoportosítva: egy balról növekvő rendezett blokk és egy jobbról zsugorodó rendezetlen blokk. Az algoritmus végigjárja a rendezetlen blokkot, megjegyzi a legkisebb elért érték indexét, és ezt az értéket kicseréli az első rendezetlen pozícióval.
Mivel menetenként csak egy csere történik, legfeljebb n-1 csere után egy n elemből álló tömböt rendezünk el. Ez a tulajdonság különbözteti meg ezt a rutint a többi kezdő szintű rutintól. Java rendező algoritmusok, amelyek sokkal gyakrabban mozgatják az adatokat.
Az tracAz alábbi „e” táblázat a {860, 8, 200, 9} minta tömböt követi pontosan úgy, ahogyan a következő szakaszban szereplő program futásidőben kinyomtatja azt.
| Átmegy | Összehasonlítások nyomtatva | Legkisebb talált érték | Tömb a csere után |
|---|---|---|---|
| Rajt | - | - | 860 8 200 9 |
| 1 | 860 és 8, 8 és 200, 8 és 9 | 8 | 8 860 200 9 |
| 2 | 860 és 200, 200 és 9 | 9 | 8 9 200 860 |
| 3 | 200 és 860 | 200 | 8 9 200 860 |
Két részlet benne tracÉrdemes náluk elidőzni. Először is, a 3. menet továbbra is cserét jelez, annak ellenére, hogy a sorrend nem változik, mivel a legkisebb fennmaradó érték már az aktuális indexen található, és a program önmagával cseréli ki az elemet. Másodszor, az összehasonlítások száma minden menetben eggyel csökken (három, majd kettő, majd egy), ami a lap alján található bonyolultsági adatok mögötti minta.
Java Program a Selection Sort megvalósításához
Az alábbi osztály neve SelectionSortAlgo, és a com.guru99 csomagban található. A main() metódus deklarálja a minta tömböt, kinyomtatja, átadja a selection()-nek rendezésre, majd újra kinyomtatja. A printArray() segédfüggvény az összes elemet egyetlen sorba írja, ami előállítja az olvasható áthaladás-megtagadás naplót.
A selection() függvényen belül a külső ciklus jelöli a rendezett és rendezetlen régiók közötti határt, az index változó az eddig látott legkisebb érték pozícióját tartalmazza, és az egyes menetek végén található három értékadás végzi el a cserét.
package com.guru99; public class SelectionSortAlgo { public static void main(String a[]) { int[] myArray = {860,8,200,9}; System.out.println("------Before Selection Sort-----"); printArray(myArray); selection(myArray);//sorting array using selection sort System.out.println("-----After Selection Sort-----"); printArray(myArray); } public static void selection(int[] array) { for (int i = 0; i < array.length - 1; i++) { System.out.println("Sort Pass Number "+(i+1)); int index = i; for (int j = i + 1; j < array.length; j++) { System.out.println("Comparing "+ array[index] + " and " + array[j]); if (array[j] < array[index]){ System.out.println(array[index] + " is greater than " + array[j] ); index = j; } } int smallerNumber = array[index]; array[index] = array[i]; array[i] = smallerNumber; System.out.println("Swapping Elements: New Array After Swap"); printArray(array); } } static void printArray(int[] array){ for(int i=0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
output:
Az osztály fordítása és futtatása az alábbi konzolnaplót hozza létre, menetenként egy kimeneti blokkal.
------Before Selection Sort----- 860 8 200 9 Sort Pass Number 1 Comparing 860 and 8 860 is greater than 8 Comparing 8 and 200 Comparing 8 and 9 Swapping Elements: New Array After Swap 8 860 200 9 Sort Pass Number 2 Comparing 860 and 200 860 is greater than 200 Comparing 200 and 9 200 is greater than 9 Swapping Elements: New Array After Swap 8 9 200 860 Sort Pass Number 3 Comparing 200 and 860 Swapping Elements: New Array After Swap 8 9 200 860 -----After Selection Sort----- 8 9 200 860
Két probléma akad a kezdőknél, amikor először futtatják ezt a példát. Mivel a fájl deklarálja package com.guru99;, a forrásnak egyező tartományban kell élnie com/guru99 könyvtárban, különben a fordító csomag- vagy osztálynév-eltérést jelez. Az osztályt ezután a teljes képzésű nevével kell elindítani, java com.guru99.SelectionSortAlgo, mert sima java SelectionSortAlgo NoClassDefFoundError hibát okoz.
A ciklushatárok a másik gyakori csapda. A külső ciklus itt áll meg: array.length - 1 és a belső hurok itt kezdődik i + 1Bármelyik határ megváltoztatása egy extra üres menetet vagy ArrayIndexOutOfBoundsException kivételt eredményez.
A szelekció időbeli és térbeli komplexitása
A program belső ciklusa mindig a tömb végéig fut, így az algoritmus ugyanannyi összehasonlítást végez, függetlenül az adatok kinézetétől. Egy n elemből álló tömb esetén ez az összeg n(n-1)/2, ami a négyelemű minta esetében hat, és a fenti kimenet valóban pontosan hat összehasonlító sort nyomtat ki.
| Ügy | Összehasonlítások | csereügyletekkel | Az idő összetettsége | Segédtér |
|---|---|---|---|---|
| Legjobb (a tömb már rendezett) | n (n-1) / 2 | n 1 XNUMX | O(n²) | O (1) |
| Átlag (véletlenszerű sorrend) | n (n-1) / 2 | n 1 XNUMX | O(n²) | O (1) |
| Legrosszabb (fordított sorrendben) | n (n-1) / 2 | n 1 XNUMX | O(n²) | O (1) |
Három következmény következik ebből az egységes számsorból:
- A szelekciós rendezés nem adaptív. A rendezett bemenet pontosan annyiba kerül, mint a megfordított bemenet, így nincs ilyen korai kilépési rövidítés. buborékfajta kínál.
- A csereszám az algoritmus erőssége. Legfeljebb n-1 csere történik, ami jóval kevesebb, mint ahány négyzetes lépést más egyszerű rendezések képesek végrehajtani.
- A memóriahasználat állandó. Csak a ciklusszámlálókra és a két ideiglenes változóra, az indexre és a smallerNumberre van szükség, tehát a segédterület O(1), és a rendezés a helyén történik.
A kvadratikus növekedés a gyakorlati határ. A tömbméret megduplázása nagyjából négyszeresére növeli az összehasonlítási munkát, így a szelekciós rendezés inkább a tanításhoz, a kis tömbökhöz és a beágyazott kódhoz illik, mint az éles adathalmazokhoz, ahol az O(n log n) algoritmus a helyes választás.
A szelekciós rendezés előnyei és hátrányai
Ha megértjük, hogy az algoritmus miben segít és miben árt, könnyebb eldönteni, hogy mikor érdemes hozzányúlni.
Előnyök
- A logika rövid és olvasható, ezért ez egy standard első rendezési gyakorlat a szöveg mellett. beszúrási rendezés.
- Helyben rendez, így nem kerül lefoglalásra második tömb, és a memóriahasználat nem növekszik a bemenettel.
- Legfeljebb n-1 írást hajt végre a tömbben, ami olyan tárolóeszközökön fontos, ahol az írás lassú vagy elhasználja az adathordozót.
- A futási ideje teljesen kiszámítható, mivel az összehasonlítási szám csak a tömb hosszától függ.
Hátrányok
- Minden eset O(n²), így az algoritmus nem skálázható nagy gyűjteményekre.
- Nem képes érzékelni a már rendezett tömböt, ezért soha nem fejezi be korán.
- A fent látható klasszikus forma instabil, így két egyenlő érték ellentétes sorrendbe is kerülhet.
- Gyakrabban hasonlít össze, mint a beszúrásos rendezés közel rendezett adatokon, ahol a beszúrásos rendezés lineáris időt vesz igénybe.
Röviden, a szelekciós rendezést akkor válasszuk, ha a tömb kicsi és minden egyes írás költséges, és kerüljük, ha az adathalmaz nagy vagy már majdnem rendezett.
Kijelölési rendezés vs. BubblRendezés vs. beszúrásos rendezés
Mindhárom algoritmus kvadratikus, helybeni összehasonlító rendezés, mégis másképp viselkednek, ha a bemenet alakja megváltozik.
| Kritérium | Kijelölés rendezése | Bubble-rendezés | Beillesztési rendezés |
|---|---|---|---|
| Legjobb eseti idő | O(n²) | O (n) | O (n) |
| Átlagos és legrosszabb esetre vonatkozó idő | O(n²) | O(n²) | O(n²) |
| Cserék vagy legrosszabb esetben műszakok | n-1 swapügylet | n(n-1)/2 csere | Akár n(n-1)/2 műszak |
| Stabil | Nem | Igen | Igen |
| Alkalmazkodó a rendezett bemenethez | Nem | Igen | Igen |
| Segédtér | O (1) | O (1) | O (1) |
| Tipikus felhasználás | Legkevesebb írási művelet szükséges | Rendezett adatok tanítása és észlelése | Kis vagy majdnem rendezett tömbök |
A táblázat egy gyakori interjúválaszt magyaráz el. A szelekciós rendezés a cserék száma alapján nyer, a buborékos rendezés a már rendezett bemenet felismerése alapján, a beszúrásos rendezés pedig a gyakorlatban általában a három közül a leggyorsabb, mivel a valós adatok gyakran részben rendezettek. Egyik sem versenyez az összevont vagy a gyors rendezéssel, ha a tömb néhány tucat elem fölé nő.
