Introduksjon om Insertion Sort i Java
Hvis du er en programmerer, må du allerede ha hørt om å sortere mye. Sortering ordner i utgangspunktet elementene enten i stigende rekkefølge eller i synkende rekkefølge. Det er så mange sorteringsalgoritmer tilgjengelig for å sortere elementene, og hver algoritme har forskjellige måter å sortere, forskjellig kompleksitet. Så det avhenger av det spesifikke scenariet og antall elementer for hvilken algoritme som skal brukes. Innlegging er også en av de ofte brukte sorteringsalgoritmene som har kompleksiteten til O (n 2) generelt og utføres som vi sorterer spillkortene i hendene våre. I dette emnet skal vi lære om Insertion Sort i Java.
Hvordan fungerer innsetting sortering i Java?
La oss forstå hvordan Insertion fungerer, ved å bruke et eksempel. Anta at det er en matrise med navnet arr som har de nedenfor nevnte elementene:
10 5 8 20 30 2 9 7
Trinn 1 - Innleggssortering starter med det andre elementet i matrisen, dvs. 5, med tanke på det første elementet i matrisen assortert i seg selv. Nå blir elementet 5 sammenlignet med 10 siden 5 er mindre enn 10, så 10 blir flyttet 1 stilling foran og 5 blir satt inn før det.
Nå er den resulterende matrisen:
5 10 8 20 30 2 9 7
Trinn # 2 - Nå blir elementet arr (2), dvs. 8 sammenlignet med elementet arr (1), dvs. 10. Siden 8 er mindre enn det foregående elementet 10, blir det forskjøvet et skritt foran fra sin stilling og deretter er det sammenlignet med 5. Siden 8 er større enn 5, så settes det inn etter det.
Da er den resulterende matrisen:
5 8 10 20 30 2 9 7
Trinn 3 - Nå blir elementet 20 sammenlignet med 10 siden det er større enn 10, det forblir i sin posisjon.
5 8 10 20 30 2 9 7
Trinn 4 - Element 30 sammenlignes med 20, og siden det er større enn 20, vil ingen endringer bli gjort og matrisen forblir som den er. Nå ville matrisen være
5 8 10 20 30 2 9 7
Trinn 5 - Element 2 blir sammenlignet med 30, ettersom det er mindre enn 30, blir det forskjøvet en posisjon foran, så sammenlignes det med 20, 10, 8, 5, ett etter ett, og alle elementene blir forskjøvet til en posisjon foran og 2 settes inn før 5.
Den resulterende matrisen er:
2 5 8 10 20 30 9 7
Trinn 6 - Element 9 sammenlignes med 30 siden det er mindre enn 30, det sammenlignes med 20, 10 en etter ett og elementet blir forskjøvet 1 posisjon foran og 9 settes inn før 10 og etter 8. Den resulterende matrisen er:
2 5 8 9 10 20 30 7
Trinn 7 - Element 7 blir sammenlignet med 30, og siden det er mindre enn 30, sammenlignes det med 30, 20, 10, 9, 8 og alle elementene forskyves en posisjon foran en etter en og 7 settes inn før 8 Den resulterende matrisen vil bli:
2 5 7 8 9 10 20 30
På denne måten blir alle elementene i arrayet sortert ved å bruke innsettingssorteringen og starter sammenligningen med det foregående elementet.
Eksempler på Implement Insertion Sort i Java
Insertion Sort in Java er en enkel sorteringsalgoritme som passer for alle små datasett.
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);
)
)
Produksjon:
12 15 18 21 23 52 61
Forklaring:
I programmet over for Insertion Sort brukes insertionSort () -funksjonen for å sortere elementene i den opprinnelige arrayen. Sortering starter fra det andre elementet ettersom det første elementet anser å være sortert i seg selv. Så sløyfen til 'j' starter fra indeksen 1 for matrisen. 'i' er variabelen som holder oversikt over indeksen rett før 'j' for å sammenligne verdien. ' nøkkel 'er variabelen som holder verdien til det gjeldende elementet som skal ordnes i sortert stilling. mens () sløyfen utføres hvis gjeldende verdi er mindre enn verdien til venstre, slik at forskyvningen av elementer kan behandles og på slutten kan innføringen av det gjeldende elementet i riktig posisjon utføres. printArray () -funksjonen brukes til å endelig skrive ut den sorterte matrisen.
1. Beste sak
Når det gjelder innsetting, vil det beste tilfellet være når alle elementene i matrisen allerede er sortert. Så når noe element sammenlignes med det venstre elementet, er det alltid større, og derfor blir ingen skifting og innsetting av elementer behandlet. I dette tilfellet ville best case-kompleksiteten være lineær, dvs. O (n).
2. Verste sak
I ovennevnte kode for innsetting, vil det verste tilfelle være når matrisen er i omvendt rekkefølge, så hver gang elementet blir sammenlignet med det venstre elementet, er det alltid mindre og deretter sammenlignet med alle elementene som foregår og skifter og innsetting er gjort. I dette tilfellet er kompleksiteten til innsettingssorten O (n 2).
3. Gjennomsnittlig sak
Selv i et gjennomsnittlig tilfelle har innsettingssortering O (n 2) kompleksitet der noen elementer ikke krever forskyvning mens noen elementer forskyves fra sine posisjoner og innsetting i riktig posisjon utføres.
4. Beste bruk
Innføringssortering er best å bruke når størrelsen på en matrise ikke er veldig stor, eller bare et lite antall elementer trenger å sorteres der nesten alle elementene er sortert og bare noen endringer må gjøres. Innleggssortering er en av de raskeste algoritmene for matriser av liten størrelse enda raskere enn Quick Sort. Faktisk bruker quicksort Insertion sort når du sorterer de små delene av matrisen.
Konklusjon
Ovennevnte forklaring viser tydelig arbeidet og implementeringen av Insertion Sort i Java. Også i andre programmeringsspråk forblir logikken for å utføre Insertion sort den samme bare syntaks endres. Før du implementerer noen sorteringsalgoritme, er det veldig viktig å gjøre en analyse av scenariet der sortering må gjøres, da ikke alle sorteringsalgoritmer passer inn i alle scenarier.
Anbefalte artikler
Dette er en guide til Insertion Sort i Java. Her diskuterer vi hvordan fungerer insertion sort i java med eksempler på implementering Insertion Sort in Java. Du kan også se på følgende artikler for å lære mer -
- Square Root i Java
- BorderLayout i Java
- Omvendt nummer i Java
- StringBuffer i Java
- Square Root i PHP
- Square Root i JavaScript
- Guide til Topp 6 sorteringsalgoritmer i Python