Beszúrás Rendezés Java nyelven

A tömbök rendezése az egyik leggyakoribb művelet, amelyet a Java kezdőknek tudnia kell. Bár a tömbök nem mindig a legkényelmesebb módja az adatok elrendezésének, és ez többnyire kis számokra vonatkozik, a tömbrendezés mögött meghúzódó koncepció rengeteg alkalmazást rejt magában az összetett szoftverekben és az adattudományban. Ebben a bejegyzésben közelebbről megvizsgáljuk, mi az a beillesztési rendezés. Felsoroltunk néhány példát és gyakorlati problémát, hogy segítsünk teljesen megismerni ezt a koncepciót.

Mi az a beillesztési rendezés?

Alapvetően a beillesztési rendezés egy olyan algoritmus, amelyet a fejlesztők kis számokból álló karakterláncok rendezésére használnak. Az összes értéket két veremre osztja – egy rendezettre és egy rendezetlenre. A „válogatás nélküli” kötegben lévő számok egyenként kerülnek ki, és a megfelelő sorrendbe kerülnek. Nézzük meg közelebbről a beillesztési rendezés bemenetét és kimenetét:

• Bemenet: egy A tömb rendezetlen numerikus elemekkel: A[0,1, n, n-2...].
• Kimenet: azonos számokat tartalmazó, de teljesen rendezett tömb. Ezt általában B-nek nevezik: B[0]B[1]...B[n-1].

A beszúrásos rendezés használatának maroknyi módja van – itt vannak a legnépszerűbbek:

• Számszerű rendezés (növekvő sorrend): [1, 2, 3, 4, 5]
• Számszerű rendezés (csökkenő sorrend): [5, 4, 3, 2, 1]
• ABC sorrendben: [a, b, c, d]

Megjegyzés: ha van egy üres tömbje vagy egy szingli, akkor ezek alapértelmezés szerint rendezettnek számítanak.

A beillesztés elméletének megértése Rendezés

Mielőtt megvizsgálnánk a beillesztési rendezés mögötti kódot, bontsuk le az algoritmust egy nem technikai nyelv használatával. Mivel a rendezési kódot növekvő sorrendben fogjuk megjeleníteni, érdemes ebben a bejegyzésben lépésről lépésre elmagyarázni az algoritmust. 1. lépés: iteráció a arr[1]és a között arr[n], ahol negy számérték általában kisebb, mint 10. 2. lépés: Hasonlítsa össze a választott elemet (más néven key) a sorozat előző számával a sort()metódus használatával. 3. lépés: Ha az összes elem kisebb, mint az utódjai, ismételje meg az összehasonlítást, amíg nagyobb értéket nem talál. 4. lépés: Cserélj egy nagyobb értéket egy pozícióval a kisebb fölé, hogy rendezett sorozatot hozz létre. 5. lépés. Ismételje meg a folyamatot, amíg meg nem kap egy rendezett karakterláncot

Primitív tömbök rendezése

Mivel az algoritmus az egyik legegyszerűbb Java-művelet, még a teljesen kezdőknek sem okozhat gondot az implementáció. Íme egy lépésről lépésre szóló útmutató egy tömb rendezéséhez

1. Deklaráljon egy tömböt a rendezéshez

Kezdésként hozzunk létre egy értéksort, amelyet később Java használatával fogunk megjeleníteni. A beillesztési rendezés használatához létre kell hoznia egy tömböt. Ehhez használdint[]

int[] arrayA = {10, 14, 20, 30};

2. Használja a sort_arr-t az algoritmus megvalósításához

A sort_arr metódus az egyik leggyakoribb módja a beillesztési rendezés megvalósításának. A gyakorlatban ez így néz ki:

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. Hozzon létre egy ciklust és egy iterátort

Ha a beillesztési rendezési algoritmusban hurkot használ, a fejlesztőknek nem kell minden elemnél megismételniük a logikát. Bár a hurkok létrehozása bonyolultnak tűnik, meglehetősen egyszerű – íme egy példa:

for(int i=0; i< sort_arr.length; ++i){

Most, hogy rendelkezik egy működő ciklussal, ideje létrehozni egy iterátort, amely az összes elemet a kívánt sorrendbe rendezi. Ezentúl az iterátort " j" néven fogjuk használni.

        int j = i;

4. "while ciklus" létrehozása

Ha a beillesztési rendezésről van szó, a "while" ciklus elengedhetetlen egy új, rendezett tömbhöz. A növekvő sorrendű beillesztési rendezés beállításához a fejlesztőnek két feltételnek kell megfelelnie:

• A j-hez rendelt értéknek nagyobbnak kell lennie 0-nál
• A hozzárendelt értéknek j-1nagyobbnak kell lennie, mint az jindex

Amint a while ciklus mindkét feltétele igaz, a tömb kulcsértéke megegyezik az jindexszel.

5. A tömb rendezése

A while ciklus beállítása után a jés j-1értékek felcserélődnek mindaddig, amíg a while ciklus egyik vagy mindkét feltétele meghiúsul. Hasonlóképpen, a rendezés megismétlődik a for ciklus minden értékénél, amíg a for ciklus feltételei is meghiúsulnak. A beszúrási rendezés folyamata a gyakorlatban így működik:

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

ArrayList rendezése

Bár fontos megérteni a beillesztés mögötti rendezés mögött rejlő matematikát, ha valós szoftverfejlesztésről van szó, az ArrayList-eket sokkal inkább rendezi, mint a primitív tömbök sorozatait. Íme egy lépésről lépésre szóló útmutató az ArrayList rendezéséhez:

1. Hozzon létre egy új Elementosztályt a gyűjteményhez tartozó elemekhez.

   
   public class Element {
       private int id;
   
       public Element(int id) {
           this.id = id;
       }
   

2. Egy gyűjteményen belül van egy compareTo()módszer – ezt fogjuk használni két elem azonosítójának összehasonlítására.

   
       public int compareTo(Element element) {
           int res = 0;
           if (this.id < element.getId()) {
               res = -1;
           }
           if (this.id > element.getId()) {
               res = 1;
           }
           return res;
       }
   }
   

3. Alkalmazza az algoritmust, és hozzon létre néhány hurkot az objektumok rendezéséhez ahelyett, ArrayListhogy összehasonlítaná őket.

   
   public static void insertionSortArrayList(List<element> list) {
       for (int j = 1; j < list.size(); j++) {
           Element current = list.get(j);
           int i = j-1;
           while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
               list.set(i+1, list.get(i));
               i--;
           }
           list.set(i+1, current);
       }
   }
   

4. További elemeket is hozzáadhat az ArrayListalábbiak szerint:

   
   List<element> list = new ArrayList<>();
   
   // Create elements w/ IDs 0-24
   for (int i = 0; i < 25; i++) {
       list.add(new Element(i));
   }
   
   // To use insertion sort, shuffle the values
   Collections.shuffle(list);
   

5. Itt az ideje a válogatásnak:

   
   // This helps print values before sorting
   list.forEach(e -> System.out.print(e.getId() + ", "));
   
   // Sort the list
   insertionSortArrayList(list);
   
   System.out.println();
   
   // Display a sorted array 
   list.forEach(e -> System.out.print(e.getId() + ", "));
   

6. Hasonlítsuk össze a bemenetet és a kimenetet, hogy megbizonyosodjunk arról, hogy nem követtünk el hibákat. Itt van a példaként használt karakterlánc összehasonlítása.

   
   4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
   

Beillesztési rendezési gyakorlati problémák

Most, hogy ismeri ezt a rendezési algoritmust, itt az ideje, hogy próbára tegye elméleti és gyakorlati készségeit. 1. elméleti kvíz Kapsz egy tömböt [1, 4, 6, 8], és egy új elemet adsz hozzá, n = 7. Hány összehasonlítást kell végrehajtania, hogy rendezett számsorozatot kapjon? Adja meg az n index végső értékét a tömbben. 2. elméleti kvíz Egy állásinterjún egy csapatvezető arra kér, hogy bizonyítsd be, hogy a rendezési beszúrás nem hatékony módszer. Ha adott egy [0, 3, 6, 8, 9] számsor, milyen sorrendben kell szerepelnie a bemeneti sorozatnak, hogy maximalizálja a rendezéshez szükséges futási időt? Gyakorlati probléma Rendezze a [0, 1, 4, 5, 2, 3, 7, 9, 8] tömböt növekvő sorrendbe a Java beszúrási rendezése segítségével.

Következtetés

A beszúrási rendezés megértésében a legnagyobb kihívás a folyamat működésének megértése. Ha már rájöttél, a sablon kóddá alakítása egy szelet torta. Mindaddig, amíg gyakorol, és idővel újra megvizsgálja a releváns gyakorlati problémákat, gyorsan javítja a beillesztési rendezési sebességet.