Bevezetés a beszúrásból
Ha programozó vagy, akkor már hallottál sokat a válogatásról. A rendezés alapvetõen az elemeket növekvõ vagy csökkenõ sorrendben rendezi. Olyan sok rendezési algoritmus érhető el az elemek rendezéséhez, és minden algoritmusnak különféle módja van a rendezésnek, eltérő bonyolultsággal. Tehát az adott forgatókönyvetől és az elemek számától függ, hogy mely algoritmust kell használni. A beszúrás az O (n 2) bonyolultságú, általánosan használt válogatási algoritmusok egyike is, és úgy hajtják végre, ahogy a kezünkben lévő játékkártyákat rendezzük. Ebben a témában megismerjük a Java beillesztési rendezést.
Hogyan működik a beszúrási rendezés a Java-ban?
Megértjük a beszúrási rendezés működését egy példa segítségével. Tegyük fel, hogy van egy arr névű tömb, amely az alábbiakban említett elemeket tartalmazza:
10 5 8 20 30 2 9 7
1. lépés - A beszúrási sorrend a tömb 2. elemével kezdődik, azaz 5., figyelembe véve a tömb első elemét, amely önmagában válogatott. Most az 5 elemet összehasonlítjuk a 10-gyel, mivel az 5-nél kevesebb, mint 10, tehát a 10-et 1 pozícióval előremozgatjuk, és az 5 behelyezzük előtte.
A kapott tömb most:
5 10 8 20 30 2 9 7
2. lépés - Most az arr (2), azaz a 8 elemet összehasonlítják az arr (1) elemmel, azaz 10. Mivel a 8 kisebb, mint az előző 10 elem, akkor egy lépéssel előre lép a helyzetéből, majd az Mivel a 8 nagyobb, mint 5, tehát utána beillesztjük.
A kapott tömb akkor:
5 8 10 20 30 2 9 7
3. lépés - Most a 20 elemet összehasonlítjuk a 10-gyel, mivel nagyobb, mint 10, így marad a helyzetében.
5 8 10 20 30 2 9 7
4. lépés - A 30. elemet összehasonlítjuk a 20-zal, és mivel ez nagyobb, mint 20, semmilyen változtatást nem hajtunk végre, és a tömb megmarad. Most a tömb lenne
5 8 10 20 30 2 9 7
5. lépés - A 2. elemet összehasonlítják a 30-zal, mivel kisebb, mint 30, egy pozícióval előre mozgatják, majd egyenként összehasonlítják a 20, 10, 8, 5-rel, és az összes elem 1 pozícióba tolódik. és a 2. pont beillesztésre kerül az 5 előtt.
A kapott tömb:
2 5 8 10 20 30 9 7
6. lépés - A 9. elemet összehasonlítjuk a 30-zal, mivel kisebb, mint 30, egyenként hasonlítják össze a 20-os, 10-gyel, és az elem elmozdul 1 helyzettel előre, és a 9-et behelyezi 10 előtt és 8 után. A kapott tömb:
2 5 8 9 10 20 30 7
7. lépés - A 7 elemet összehasonlítják a 30-zal, és mivel ez kisebb, mint 30, akkor összehasonlítják a 30, 20, 10, 9, 8-tal, és az összes elemet egymás után 1-helyzetben elmozdítják, a 7-et pedig 8 elé helyezik. A kapott tömb így lesz:
2 5 7 8 9 10 20 30
Ilyen módon a tömb összes elemét beszúrási sorrend szerint rendezzük, kezdve az összehasonlítást az előző elemmel.
Példák a beillesztés végrehajtására Rendezés Java-ban
A beszúrási szortírozás a Java-ban egy egyszerű válogatási algoritmus, amely alkalmas minden kicsi adatkészletre.
public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)
Kimenet:
12 15 18 21 23 52 61
Magyarázat:
A beszúrási sorrend fenti programjában az insertionSort () függvényt használjuk az eredeti tömb elemeinek rendezésére. A rendezés a második elemtől kezdődik, mivel az első elem önmagában rendezésnek tekinthető. Tehát a 'j' hurok a tömb indexéből indul. 'i' az index változó nyomon követése közvetlenül a 'j' elõtt az érték összehasonlítása érdekében. ' kulcs ”az az aktuális elem értékét megtartó változó, amelyet rendezett helyzetbe kell rendezni. míg a () hurkot akkor hajtják végre, ha az aktuális érték kisebb, mint a bal szélső érték, hogy az elemek eltolódása feldolgozható legyen, és az aktuális elem a jobb helyzetbe való beillesztése végezhető el. A printArray () függvény a rendezett tömb végleges kinyomtatására szolgál.
1. Legjobb eset
A beszúrási sorrendben a legjobb eset lenne, ha a tömb összes eleme már rendezve van. Tehát, ha valamelyik elemet összehasonlítják a bal oldali elemmel, akkor mindig nagyobb, ezért az elemek eltolása és beillesztése nem kerül feldolgozásra. Ebben az esetben a legjobb eset összetettsége lineáris lenne, azaz O (n).
2. Legrosszabb eset
A fenti beillesztési kód esetén a legrosszabb eset akkor fordul elő, ha a tömb fordított sorrendben van, tehát minden egyes elem összehasonlításakor a bal legszélső elemmel mindig kisebb, majd összehasonlítva az összes folyamatban lévő elemmel, amely eltolódik és eltolódik és a behelyezés megtörtént. Ebben az esetben a beillesztési sorrend összetettsége O (n 2).
3. Átlagos eset
Még egy átlagos esetben is az inszertációs fajtának O (n 2) bonyolultsága van, amelyben egyes elemek nem igényelnek eltolást, míg egyes elemek elmozdulnak a helyükről, és a behelyezés a megfelelő helyzetbe kerül.
4. Legjobb felhasználás
A beszúrási rendezés akkor a legjobb, ha a tömb mérete nem túl nagy, vagy csak kevés elemet kell rendezni, amelyben szinte az összes elem rendezve van, és csak néhány módosítást kell végrehajtani. A beszúrási rendezés az egyik leggyorsabb algoritmus a kis méretű tömb számára, még gyorsabb, mint a Gyors rendezésnél. Valójában a quicksort az Insertion rendezést használja a tömb apró részeinek rendezésekor.
Következtetés
A fenti magyarázat egyértelműen bemutatja a beszúrási rendezés működését és megvalósítását Java-ban. Más programozási nyelveken is, a beszúrási rendezés logikája változatlan marad, csak a szintaxis megváltozik. Bármely válogató algoritmus végrehajtása előtt nagyon fontos elemezni a forgatókönyvet, ahol a válogatást el kell végezni, mivel nem minden rendezési algoritmus illeszkedik minden forgatókönyvhöz.
Ajánlott cikkek
Ez egy útmutató a Java beillesztési rendezéshez. Itt tárgyaljuk, hogyan működik a beszúrási szortírozás java-ban a példákkal a beszúrási szortírozás végrehajtására Java-ban. Lehet, hogy megnézi a következő cikkeket is, ha többet szeretne megtudni -
- Négyzetgyökér Java-ban
- BorderLayout Java-ban
- Fordított szám Java-ban
- StringBuffer Java-ban
- Négyzetgyökér a PHP-ben
- Négyzetgyökér a JavaScript-ben
- Útmutató a Python 6 legfontosabb rendezési algoritmusához