Introduktion om insättningssortering i Java
Om du är programmerare måste du redan ha hört talas om hur du sorterar mycket. Sortering ordnar i princip elementen antingen i stigande ordning eller i fallande ordning. Det finns så många sorteringsalgoritmer tillgängliga för att sortera elementen och varje algoritm har olika sätt att sortera, olika komplexitet. Så det beror på det specifika scenariot och antalet element för vilken algoritm som ska användas. Insättning är också en av de vanligtvis använda sorteringsalgoritmerna som har komplexiteten O (n 2) i allmänhet och utförs som om vi sorterar spelkorten i våra händer. I det här ämnet kommer vi att lära oss om Insertion Sort i Java.
Hur fungerar insättningssortering i Java?
Låt oss förstå hur Insertion fungerar med hjälp av ett exempel. Anta att det finns en matris med namnet arr med de nedan nämnda elementen:
10 5 8 20 30 2 9 7
Steg # 1 - Insättningssortering börjar med det andra elementet i matrisen, dvs. 5, med tanke på det första elementet i matrisen i sig själv. Nu jämförs elementet 5 med 10 eftersom 5 är mindre än 10, så 10 flyttas 1 läge framåt och 5 införs före det.
Nu är den resulterande matrisen:
5 10 8 20 30 2 9 7
Steg # 2 - Nu jämförs elementet arr (2), dvs 8 med elementet arr (1), dvs 10. Eftersom 8 är mindre än dess föregående element 10, flyttas det ett steg framåt från sitt läge och sedan är det jämfört med 5. Eftersom 8 är större än 5, så sätts det in efter det.
Då är den resulterande matrisen:
5 8 10 20 30 2 9 7
Steg 3 - Nu jämförs elementet 20 med 10 eftersom det är större än 10, det förblir i sin position.
5 8 10 20 30 2 9 7
Steg 4 - Element 30 jämförs med 20, och eftersom det är större än 20 skulle inga förändringar göras och matrisen kvarstår som det är. Nu skulle matrisen vara
5 8 10 20 30 2 9 7
Steg # 5 - Element 2 jämförs med 30, eftersom det är mindre än 30, det flyttas en position framåt sedan jämförs det med 20, 10, 8, 5, en efter en och alla element flyttas till 1 position framåt och 2 införs före 5.
Den resulterande matrisen är:
2 5 8 10 20 30 9 7
Steg # 6 - Element 9 jämförs med 30 eftersom det är mindre än 30, det jämförs med 20, 10 en efter en och elementet flyttas 1 läge framåt och 9 införs före 10 och efter 8. Den resulterande matrisen är:
2 5 8 9 10 20 30 7
Steg 7 - Element 7 jämförs med 30, och eftersom det är mindre än 30 jämförs det med 30, 20, 10, 9, 8 och alla element flyttas ett läge framåt en efter en och 7 införs innan 8 Den resulterande matrisen skulle bli:
2 5 7 8 9 10 20 30
På detta sätt sorteras alla elementen i matrisen med hjälp av infogningssorten och börjar jämförelsen med föregående element.
Exempel på Implement Insertion Sort i Java
Insertion Sort in Java är en enkel sorteringsalgoritm som passar alla små datamängder.
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
Förklaring:
I ovanstående program för Insertion Sort används insertionSort () -funktionen för att sortera elementen i den ursprungliga matrisen. Sortering börjar från det andra elementet eftersom det första elementet anser vara sorterat i sig själv. Så slingan till 'j' börjar från index 1 i matrisen. 'i' är den variabel som håller reda på indexet strax före 'j' för att jämföra värdet. ' nyckel 'är den variabel som håller värdet på det aktuella elementet som ska ordnas i sorterad position. medan () slingan exekveras om det aktuella värdet är mindre än värdet längst till vänster så att skiftningen av element kan bearbetas och vid slutet kan införandet av det aktuella elementet till höger position utföras. funktionen printArray () används för att slutligen skriva ut den sorterade matrisen.
1. Bästa fall
I infogningssorten skulle det bästa fallet vara när alla element i matrisen redan är sorterade. Så när något element jämförs med det vänstra elementet, är det alltid större och därför kommer ingen förskjutning och infogning av element att bearbetas. I detta fall skulle det bästa fallet vara linjärt, dvs O (n).
2. Värsta fall
I ovanstående kod för infogning är det värsta fallet när matrisen är i omvänd ordning, så varje gång elementet jämförs med det vänstra elementet är det alltid mindre och jämförs sedan med alla fortsatta element som äger rum och växlar och införandet är gjort. I det här fallet är komplexiteten för införingssorten O (n 2).
3. Medelfall
Även i ett genomsnitt har insättningssortering O (n 2) -komplexitet där vissa element inte kräver förskjutning medan vissa element flyttas från sina positioner och införing i rätt position utförs.
4. Bästa användning
Insättningssortering är bäst att använda när storleken på en matris inte är särskilt stor eller endast ett litet antal element behöver sorteras där nästan alla element sorteras och bara några ändringar behöver göras. Insättningssortering är en av de snabbaste algoritmerna för små storlekar ännu snabbare än Quick Sort. Faktum är att quicksort använder Insertion sort när man sorterar sina små delar av matrisen.
Slutsats
Ovanstående förklaring visar tydligt arbetet och implementeringen av Insertion Sort i Java. Även på andra programmeringsspråk förblir logiken för att utföra Insertion sortering densamma bara Syntax ändras. Innan någon sorteringsalgoritm implementeras är det mycket viktigt att göra en analys av scenariot där sortering måste göras eftersom inte alla sorteringsalgoritmer passar in i alla scenarier.
Rekommenderade artiklar
Detta är en guide till Insertion Sort i Java. Här diskuterar vi hur fungerar insättningssortering i java med exempel på implementeringssortering i Java. Du kan också titta på följande artiklar för att lära dig mer -
- Fyrkantig rot i Java
- BorderLayout i Java
- Omvänd nummer i Java
- StringBuffer i Java
- Square Root i PHP
- Square Root i JavaScript
- Guide till topp 6-sorteringsalgoritmer i Python