Úvod k triedeniu vkladania v jazyku Java
Ak ste programátor, musíte už veľa počuť o triedení. Triedenie je v zásade usporiadanie prvkov vzostupne alebo zostupne. K dispozícii je toľko triediacich algoritmov na triedenie prvkov a každý algoritmus má rôzne spôsoby triedenia, rôznu zložitosť. Závisí to od konkrétneho scenára a počtu prvkov, na základe ktorých by sa mal algoritmus použiť. Vkladanie je tiež jedným z bežne používaných triediacich algoritmov, ktoré majú všeobecne komplexnosť O (n 2), a vykonáva sa tak, že v rukách triedime hracie karty. V tejto téme sa dozvieme viac o Insertion Sort in Java.
Ako funguje triedenie vkladania v jazyku Java?
Poďme pochopiť fungovanie triedenia vloženia pomocou príkladu. Predpokladajme, že existuje pole, ktorého názov má nasledujúce prvky:
10 5 8 20 30 2 9 7
Krok č. 1 - Zoradenie vloženia začína druhým prvkom poľa, tj 5, pričom sa berie do úvahy prvý prvok poľa samotný. Teraz je prvok 5 porovnávaný s 10, pretože 5 je menej ako 10, takže 10 sa posunie o 1 pozíciu dopredu a 5 sa vloží pred neho.
Výsledné pole je teraz:
5 10 8 20 30 2 9 7
Krok # 2 - Teraz je prvok arr (2), tj 8 porovnávaný s prvkom arr (1), tj 10. Pretože 8 je menšie ako jeho predchádzajúci prvok 10, posunie sa o jeden krok pred svojou polohou a potom je v porovnaní s 5. Pretože 8 je väčší ako 5, vkladá sa za neho.
Výsledné pole je potom:
5 8 10 20 30 2 9 7
Krok # 3 - Teraz je prvok 20 porovnávaný s 10, pretože je väčší ako 10, zostáva vo svojej polohe.
5 8 10 20 30 2 9 7
Krok č. 4 - Prvok 30 je porovnávaný s 20 a keďže je väčší ako 20, nevykonali by sa žiadne zmeny a zostava zostala taká, aká je. Teraz by to bolo pole
5 8 10 20 30 2 9 7
Krok č. 5 - Prvok 2 je porovnávaný s 30, pretože je menší ako 30, je posunutý o jednu pozíciu dopredu, potom je porovnávaný s 20, 10, 8, 5, jeden po druhom a všetky prvky sa posunú na 1 pozíciu dopredu a 2 sa vkladá pred 5.
Výsledné pole je:
2 5 8 10 20 30 9 7
Krok č. 6 - Prvok 9 je porovnávaný s 30, pretože je menší ako 30, porovnáva sa s 20, 10 jeden po druhom a prvok sa posunie o 1 pozíciu dopredu a 9 sa vloží pred 10 a po 8. Výsledné pole je:
2 5 8 9 10 20 30 7
Krok č. 7 - Prvok 7 je porovnávaný s 30 a keďže je menší ako 30, porovnáva sa s 30, 20, 10, 9, 8 a všetky prvky sú posunuté o 1 pozíciu pred sebou a 7 je vložené pred 8 Výsledné pole by sa stalo:
2 5 7 8 9 10 20 30
Týmto spôsobom sú všetky prvky poľa zoradené pomocou triedenia vloženia, pričom sa začína porovnávanie s predchádzajúcim prvkom.
Príklady implementácie triedenia vkladania v jazyku Java
Insertion Sort in Java je jednoduchý triediaci algoritmus vhodný pre všetky malé množiny údajov.
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);
)
)
Výkon:
12 15 18 21 23 52 61
vysvetlenie:
Vo vyššie uvedenom programe Insertion Sort sa funkcia inserttionSort () používa na triedenie prvkov pôvodného poľa. Zoradenie začína od druhého prvku, pretože prvý prvok sa považuje za usporiadaný sám o sebe. Slučka „j“ teda začína indexom 1 poľa. „i“ je premenná, ktorá sleduje index tesne pred „j“ na účely porovnania hodnoty. “ kľúč 'je premenná, ktorá drží hodnotu aktuálneho prvku, ktorý má byť usporiadaný v zoradenej polohe. while () je vykonaná slučka, ak je aktuálna hodnota menšia ako hodnota úplne vľavo, takže je možné spracovávať posun prvkov a na konci vloženia aktuálneho prvku do správnej polohy. Funkcia printArray () sa používa na konečnú tlač zoradeného poľa.
1. Najlepší prípad
Pri usporiadaní vkladania by najlepším prípadom bolo, keď by boli všetky prvky poľa už zoradené. Ak je teda nejaký prvok porovnaný s prvkom úplne vľavo, je vždy väčší, a preto sa nespracováva posun a vkladanie prvkov. V tomto prípade by najlepšia zložitosť prípadu bola lineárna, tj O (n).
2. Najhorší prípad
Vo vyššie uvedenom kóde vkladania by bol najhorší prípad, keď by sa pole nachádzalo v opačnom poradí, takže zakaždým, keď sa prvok porovná so svojím ľavým ľavým prvkom, je vždy menší a potom sa porovná so všetkými prebiehajúcimi prvkami, ktoré sa vyskytujú a posúvajú a vkladanie je hotové. V tomto prípade je zložitosť usporiadania vloženia O (n 2).
3. Priemerný prípad
Dokonca aj v priemernom prípade má druh vloženia O (n 2) zložitosť, v ktorej niektoré prvky nevyžadujú radenie, zatiaľ čo niektoré prvky sú posunuté zo svojich polôh a vykonáva sa vkladanie do správnej polohy.
4. Najlepšie použitie
Najlepšie je použiť vkladanie, keď veľkosť poľa nie je príliš veľká alebo je potrebné zoradiť iba malý počet prvkov, v ktorých sú zoradené takmer všetky prvky a je potrebné vykonať iba určité zmeny. Zoradenie vloženia je jedným z najrýchlejších algoritmov pre pole s malou veľkosťou ešte rýchlejšie ako v prípade rýchleho zoradenia. V skutočnosti rýchly server používa triedenie vloženia pri triedení jeho malých častí poľa.
záver
Vyššie uvedené vysvetlenie jasne ukazuje fungovanie a implementáciu triedenia vloženia v jazyku Java. Aj v iných programovacích jazykoch zostane logika na vykonanie zoradenia vloženia rovnaká iba v prípade zmien syntaxe. Pred implementáciou akéhokoľvek triediaceho algoritmu je veľmi dôležité urobiť nejakú analýzu scenára, kde je potrebné triedenie vykonať, pretože nie každý triediaci algoritmus sa hodí do všetkých scenárov.
Odporúčané články
Toto je sprievodca triedením vkladania v Jave. V tejto časti si preberieme, ako funguje triedenie vkladania v jazyku Java s príkladmi implementácie triedenia vkladania v jazyku Java. Ďalšie informácie nájdete aj v nasledujúcich článkoch -
- Square Root v Jave
- BorderLayout v Jave
- Reverzné číslo v jazyku Java
- StringBuffer v Jave
- Štvorcový koreň v PHP
- Štvorcový koreň v JavaScripte
- Sprievodca top 6 triediacich algoritmov v Pythone