Introduktion til indsættelsessortering i Java
Hvis du er en programmør, skal du allerede have hørt om sortering af en masse. Sortering ordner grundlæggende elementerne enten i stigende rækkefølge eller i faldende rækkefølge. Der er så mange sorteringsalgoritmer tilgængelige til at sortere elementerne, og hver algoritme har forskellige måder at sortere, forskellig kompleksitet. Så det afhænger af det specifikke scenario og antallet af elementer til hvilken algoritme, der skal bruges. Indsættelse er også en af de almindeligt anvendte sorteringsalgoritmer med kompleksiteten O (n 2) generelt og udføres, ligesom vi sorterer spillekortene i vores hænder. I dette emne skal vi lære om indsættelsessortering i Java.
Hvordan fungerer indsættelsessortering i Java?
Lad os forstå funktionen af indsættelsessortering ved hjælp af et eksempel. Antag, at der er en matrix med navnet arr, der har de nævnte elementer:
10 5 8 20 30 2 9 7
Trin 1 - Indsættelsessortering starter med det andet element i array, dvs. 5, i betragtning af det første element i arrayet, der er assorteret i sig selv. Nu sammenlignes elementet 5 med 10, da 5 er mindre end 10, så 10 bevæges 1 position foran og 5 indsættes før det.
Nu er den resulterende matrix:
5 10 8 20 30 2 9 7
Trin # 2 - Nu sammenlignes elementet arr (2), dvs. 8, med elementet arr (1), dvs. 10. Da 8 er mindre end det foregående element 10, forskydes det et trin foran fra sin position, og så er det sammenlignet med 5. Da 8 er større end 5, indsættes det derefter efter det.
Så er den resulterende matrix:
5 8 10 20 30 2 9 7
Trin # 3 - Nu sammenlignes elementet 20 med 10, da det er større end 10, det forbliver i sin position.
5 8 10 20 30 2 9 7
Trin # 4 - Element 30 sammenlignes med 20, og da det er større end 20, ville der ikke blive foretaget ændringer, og array forbliver som det er. Nu ville arrayet være
5 8 10 20 30 2 9 7
Trin # 5 - Element 2 sammenlignes med 30, da det er mindre end 30, det skiftes en position foran, så sammenlignes det med 20, 10, 8, 5, en efter en, og alle elementer skiftes til 1 position foran og 2 indsættes før 5.
Det resulterende array er:
2 5 8 10 20 30 9 7
Trin 6 - Element 9 sammenlignes med 30, da det er mindre end 30, det sammenlignes med 20, 10 en efter en, og elementet skiftes 1 position foran og 9 indsættes før 10 og efter 8. Den resulterende matrix er:
2 5 8 9 10 20 30 7
Trin 7 - Element 7 sammenlignes med 30, og da det er mindre end 30, sammenlignes det med 30, 20, 10, 9, 8, og alle elementer forskydes 1 position foran et efter et og 7 indsættes inden 8 Det resulterende array vil blive:
2 5 7 8 9 10 20 30
På denne måde sorteres alle elementerne i arrayet ved hjælp af indsættelsessort, idet man starter sammenligningen med det foregående element.
Eksempler på implementering af indsættelsessortering i Java
Indsættelsessortering i Java er en simpel sorteringsalgoritme, der er egnet til alle små datasæt.
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);
)
)
Produktion:
12 15 18 21 23 52 61
Forklaring:
I ovenstående program for indsættelsessortering anvendes insertionSort () -funktionen til at sortere elementerne i den originale matrix. Sortering starter fra det andet element, da det første element betragter som sorteret i sig selv. Så løkken af 'j' starter fra indekset 1 for matrixen. 'i' er den variabel, der holder styr på indekset lige før 'j' for at sammenligne værdien. ' nøgle 'er den variabel, der holder værdien af det aktuelle element, der skal arrangeres i sorteret position. mens () loop udføres, hvis den aktuelle værdi er mindre end den venstre værdi, så forskydningen af elementer kan behandles og i slutningen kan indsættelse af det aktuelle element i den rigtige position udføres. funktionen printArray () bruges til endelig at udskrive den sorterede matrix.
1. Bedste sag
I indsættelsessorten ville det bedste tilfælde være, når alle elementerne i arrayet allerede er sorteret. Så når ethvert element sammenlignes med dets venstre element, er det altid større, og derfor vil ingen forskydning og indsættelse af elementer blive behandlet. I dette tilfælde ville det bedste tilfælde være kompleks, dvs. O (n).
2. Værste sag
I ovennævnte kodning for indsættelsessortering ville det værste tilfælde være, når matrixen er i omvendt rækkefølge, så hver gang, når elementet sammenlignes med det venstre element, er det altid mindre og sammenlignes derefter med alle de videreførende elementer, der finder sted og skifter. og indsættelse er gjort. I dette tilfælde er indsættelsessortens kompleksitet O (n 2).
3. Gennemsnitlig sag
Selv i et gennemsnitligt tilfælde har indsættelsessort O (n 2) kompleksitet, hvor nogle elementer ikke kræver forskydning, mens nogle elementer forskydes fra deres positioner, og indsættelse i den rigtige position udføres.
4. Bedste brug
Indsættelsessortering er bedst at bruge, når størrelsen på en matrix ikke er meget stor, eller kun et lille antal elementer skal sorteres, hvor næsten alle elementerne er sorteret, og kun nogle ændringer skal foretages. Indsættelsessortering er en af de hurtigste algoritmer til array med lille størrelse endnu hurtigere end Quick Sort. Faktisk bruger quicksort indsættelsessortering, når de små dele af arrayet sorteres.
Konklusion
Ovenstående forklaring viser klart arbejdet og implementeringen af Insertion Sort i Java. Også på andre programmeringssprog forbliver logikken for at udføre indsættelsessorter den samme, kun syntaksændringerne. Før du implementerer en sorteringsalgoritme, er det meget vigtigt at foretage en analyse af scenariet, hvor sortering skal udføres, da ikke alle sorteringsalgoritmer passer ind i alle scenarier.
Anbefalede artikler
Dette er en guide til indsættelsessortering i Java. Her diskuterer vi hvordan fungerer indsættelsessorter i java med eksempler til implementering af indsættelsessortering i Java. Du kan også se på de følgende artikler for at lære mere -
- Firkantet rod i Java
- BorderLayout i Java
- Omvendt nummer i Java
- StringBuffer i Java
- Firkantet rod i PHP
- Firkantet rod i JavaScript
- Vejledning til top 6 sortering af algoritmer i Python