Uvod o razvrščanju vstavka v Javi
Če ste programer, ste gotovo že slišali o razvrščanju. Razvrščanje je v osnovi razporeditev elementov v naraščajočem ali padajočem vrstnem redu. Na voljo je toliko algoritmov za razvrščanje elementov in vsak algoritem ima različne načine razvrščanja, različne zapletenosti. Torej je odvisno od konkretnega scenarija in števila elementov, kateri algoritem je treba uporabiti. Vstavljanje je tudi eden najpogosteje uporabljenih algoritmov za razvrščanje, ki ima na splošno kompleksnost O (n 2) in se izvaja tako, kot da razvrščamo igralne karte v svojih rokah. V tej temi bomo spoznali Razvrsti vstavljanje na Javi.
Kako razvrščanje vstavkov deluje na Javi?
Poglejmo, kako deluje primer razvrščanja z uporabo primera. Recimo, da obstaja matrika z imeno arr, ki vsebuje spodaj omenjene elemente:
10 5 8 20 30 2 9 7
Korak # 1 - Vstavljanje vrstice se začne z 2. elementom matrike, tj. 5, upoštevajoč 1. element matrike, ki je izbran v sebi. Zdaj se element 5 primerja z 10, saj je 5 manjši od 10, torej 10 premaknemo 1 položaj naprej in 5 vstavimo pred njo.
Zdaj je niz:
5 10 8 20 30 2 9 7
Korak # 2 - Zdaj se element arr (2), tj. 8 primerja z elementom arr (1), to je 10. Ker je 8 manjši od prejšnjega elementa 10, se premakne za korak naprej od svojega položaja in potem je v primerjavi s 5. Ker je 8 večje od 5, se vstavi za njim.
Potem je dobljeni niz:
5 8 10 20 30 2 9 7
Korak # 3 - Zdaj se element 20 primerja z 10, ker je večji od 10, ostane v svojem položaju.
5 8 10 20 30 2 9 7
4. korak - Element 30 primerjamo z 20, in ker je večji od 20, sprememb ne bi bilo, nobena matrika ostane takšna, kot je. Zdaj bi bila matrika
5 8 10 20 30 2 9 7
Korak # 5 - Element 2 primerjamo s 30, saj je manjši od 30, ga premaknemo za eno pozicijo naprej, nato ga primerjamo z 20, 10, 8, 5, eden za drugim in vsi elementi se premaknejo v 1 položaj naprej in 2 se vstavi pred 5.
Nastali niz je:
2 5 8 10 20 30 9 7
Korak # 6 - Element 9 primerjamo s 30, saj je manjši od 30, primerjamo ga z 20, 10 drug za drugim in element se premakne za 1 položaj naprej in 9 se vstavi pred 10 in po 8. Rezultat matrike je:
2 5 8 9 10 20 30 7
Korak # 7 - Element 7 primerjamo s 30 in ker je manjši od 30, ga primerjamo s 30, 20, 10, 9, 8 in vsi elementi se premaknejo za 1 položaj naprej enega za drugim in 7 se vstavi pred 8 . Nastali niz bi postal:
2 5 7 8 9 10 20 30
Na ta način so razvrščeni vsi elementi matrike z uporabo vstavitvene vrste, ki začne primerjavo s predhodnim elementom.
Primeri za izvajanje razvrščanja vstavka v Javi
Vstavljanje Razvrsti v Javi je preprost algoritem za razvrščanje, primeren za vse majhne nabore podatkov.
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);
)
)
Izhod:
12 15 18 21 23 52 61
Pojasnilo:
V zgornjem programu Razvrsti vstavljanje se funkcija sortiranjaSort () uporablja za razvrščanje elementov izvirne matrike. Razvrščanje se začne od drugega elementa, saj prvi element meni, da je sam razvrščen. Torej, zanka 'j' se začne od indeksa 1 matrike. 'i' je spremenljivka, ki sledi indeksu tik pred 'j', da bi primerjala vrednost. ' tipka 'je spremenljivka, ki vsebuje vrednost trenutnega elementa, ki mora biti razporejen v razvrščenem položaju. medtem ko se zanka () izvaja, če je trenutna vrednost manjša od skrajne leve vrednosti, tako da je mogoče premikati elemente in ob koncu vstaviti trenutni element na desni položaj. funkcija printArray () se uporablja za končno tiskanje razvrščenega niza.
1. Najboljši primer
Pri razvrstitvi vstavljanja bi bil najboljši primer, ko so vsi elementi matrike že razvrščeni. Torej, če je kateri koli element v primerjavi z njegovim levim levim elementom, je vedno večji, zato se ne bo prestavljalo premikanje in vstavljanje elementov. V tem primeru bi bila najboljša zapletenost primerov linearna, torej O (n).
2. Najslabši primer
V zgornji razvrstitveni kodi najhujšega primera bi bilo, če je matrika v obratnem vrstnem redu, tako da je vsakič, ko element primerjamo z njegovim skrajnim levim elementom, vedno manjši, nato pa ga primerjamo z vsemi nadaljevalnimi elementi, ki se odvijajo in premikajo in vstavljanje se opravi. V tem primeru je zahtevnost sorte vstavljanja O (n 2).
3. Povprečen primer
Tudi v povprečnem primeru ima sorta vstavljanja kompleksnost O (n 2), pri kateri nekateri elementi ne potrebujejo premika, medtem ko so nekateri elementi premaknjeni iz svojih položajev in vstavitev v pravi položaj.
4. Najboljša uporaba
Razvrstitev vstavka je najbolje uporabiti, kadar velikost matrike ni zelo velika ali pa je treba razvrstiti le majhno število elementov, v katerih so razvrščeni skoraj vsi elementi in so potrebne le nekatere spremembe. Vstavljanje razvrščanja je eden najhitrejših algoritmov za niz majhnih velikosti, še hitrejši od hitrega razvrščanja. Dejstvo je, da quicksort uporablja sortiranje Insertion, ko razvršča svoje majhne dele matrike.
Zaključek
Zgornja razlaga jasno prikazuje delovanje in izvajanje razvrščanja vstavitve v Javi. Tudi v drugih programskih jezikih logika za izvedbo vstavljanja ostane enaka, le spremembe sintakse. Pred uvedbo katerega koli algoritma za razvrščanje je zelo pomembno narediti analizo scenarija, kjer je treba razvrstiti, saj ni vsak algoritem za razvrščanje primeren za vse scenarije.
Priporočeni članki
To je vodnik za Razvrščanje vstavkov v Javi. Tukaj smo razpravljali o tem, kako razvrstitev vstavljanja deluje v javi s primeri za izvajanje razvrščanja vstavitve na Javi Za več informacij si lahko ogledate tudi naslednje članke -
- Kvadratni koren na Javi
- BorderLayout na Javi
- Povratna številka na Javi
- StringBuffer v Javi
- Kvadratni koren v PHP
- Kvadratni koren v JavaScript
- Vodnik po top 6 razvrstitev algoritmov v Python