Sortering av matriser är en av de vanligaste operationerna som en Java-nybörjare bör veta hur man gör. Även om arrayer inte alltid är det bekvämaste sättet att ordna data och detta gäller mest för små antal, har konceptet bakom arraysortering massor av applikationer inom komplex programvara och datavetenskap. I det här inlägget kommer vi att titta närmare på vad insättningssort är. Vi inkluderade några exempel och övningsproblem för att hjälpa dig att förstå detta koncept fullt ut.
Vad är insättningssortering?
I grund och botten är insättningssortering en algoritm som utvecklare använder för att organisera strängar med små nummer. Den delar upp alla värden i två stackar - en sorterad och en osorterad. En efter en plockas siffrorna i den ”osorterade” stapeln ut och placeras i rätt ordning. Låt oss ta en närmare titt på ingången och utmatningen av infogningssort:
Indata: en matris A med osorterade numeriska element: A[0,1, n, n-2...].
Utdata: en matris som innehåller samma nummer men helt sorterad. Denna kallas vanligtvis B: B[0]B[1]...B[n-1].
Det finns en handfull sätt att använda infogningssortering - här är de mest populära:
Obs: om du har en tom array eller en singleton, anses dessa vara sorterade som standard.
Förstå Theory of Insertion Sort
Innan vi utforskar koden bakom insättningssortering, låt oss bryta ner algoritmen med ett icke-tekniskt språk. Eftersom vi kommer att visa koden för sortering i stigande ordning, är det vettigt att förklara algoritmen steg för steg i det här inlägget. Steg 1. Iteration mellan arr[1]och arr[n]var när ett numeriskt värde som vanligtvis är mindre än 10. Steg 2. Jämför elementet du valde (känd som ) keymed föregående nummer i sekvensen med sort()metoden. Steg 3. Om alla element är mindre än deras efterföljare, upprepa jämförelsen tills du hittar ett större värde. Steg 4. Byt ett större värde en position utöver det mindre för att skapa en ordnad sekvens. Steg 5. Upprepa processen tills du får en sorterad teckensträng
Sortering av primitiva arrayer
Eftersom algoritmen är en av de mest enkla Java-operationerna bör inte ens nybörjare ha mycket problem med att implementera den. Här är en steg-för-steg-guide för att sortera en array
1. Ange en array för sorteringen
Till att börja med, låt oss skapa en sträng med värden som vi senare kommer att visa med hjälp av Java. För att använda infogningssortering måste du skapa en array. För det, användint[]
int[] arrayA = {10, 14, 20, 30};
2. Använd sort_arr för att implementera algoritmen
Metoden sort_arr är ett av de vanligaste sätten att implementera insättningssortering. I praktiken ser det ut så här:
for(int i=0; i< sort_arr.length; ++i){
int j = i;
3. Skapa en loop och en iterator
Genom att använda en loop i insättningssorteringsalgoritmen behöver utvecklarna inte upprepa logiken för varje element. Även om det verkar komplicerat att skapa loopar är det ganska enkelt - här är ett exempel:
for(int i=0; i< sort_arr.length; ++i){
Nu när du har en fungerande loop är det dags att skapa en iterator som kommer att sortera alla element i önskad ordning. Från och med nu kommer vi att hänvisa till iteratorn som " " j.
int j = i;
4. Skapa en "while loop"
När det gäller insättningssortering är en "while"-slinga väsentlig för en ny, sorterad array. För att ställa in den för en insättningssortering i stigande ordning måste en utvecklare uppfylla två villkor:
Värdet som tilldelas j måste vara större än 0
Värdet som tilldelas j-1måste vara större än jindexet
Så snart båda villkoren i while-loopen är sanna, kommer arrayens nyckelvärde att vara lika med indexet j.
5. Sortering av arrayen
När du har ställt in while-slingan kommer värdena joch j-1att bytas tills ett eller båda villkoren i while-slingan misslyckas. På samma sätt kommer sorteringen att upprepas för varje värde i for-slingan tills även for-loop-villkoren misslyckas. Så här fungerar insättningssorteringsprocessen i praktiken:
Även om det är viktigt att förstå matematiken bakom insättningssortering, kommer du att sortera ArrayLists mycket mer än sekvenser i primitiva arrayer när det kommer till verklig mjukvaruutveckling. Här är en steg-för-steg-guide för att sortera en ArrayList:
Skapa en ny Elementklass för föremålen som hör till samlingen.
public class Element {
private int id;
public Element(int id) {
this.id = id;
}
Inom en samling finns det en compareTo()metod - vi kommer att använda den för att jämföra id för två element.
public int compareTo(Element element) {
int res = 0;
if (this.id < element.getId()) {
res = -1;
}
if (this.id > element.getId()) {
res = 1;
}
return res;
}
}
Använd algoritmen och skapa några loopar för att sortera objekten i en ArrayLististället för att jämföra dem.
public static void insertionSortArrayList(List<element> list) {
for (int j = 1; j < list.size(); j++) {
Element current = list.get(j);
int i = j-1;
while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
list.set(i+1, list.get(i));
i--;
}
list.set(i+1, current);
}
}
ArrayListDu kan också lägga till fler element, som visas nedan:
List<element> list = new ArrayList<>();
// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
list.add(new Element(i));
}
// To use insertion sort, shuffle the values
Collections.shuffle(list);
Nu är det dags att sortera:
// This helps print values before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));
// Sort the list
insertionSortArrayList(list);
System.out.println();
// Display a sorted array
list.forEach(e -> System.out.print(e.getId() + ", "));
Låt oss nu jämföra input och output för att säkerställa att vi inte gjorde några misstag. Här är jämförelsen av strängen vi använde som exempel.
Nu när du har koll på den här sorteringsalgoritmen är det dags att sätta dina teoretiska och praktiska färdigheter på prov. Teoriquiz #1 Du får en array [1, 4, 6, 8] och lägger till ett nytt element n = 7 till den. Hur många jämförelser behöver du göra för att få en sorterad talföljd? Ange slutvärdet för index n i arrayen. Teoriquiz #2 Vid en anställningsintervju ber en gruppledare dig att bevisa att sorteringsinsättning är en ineffektiv metod. Givet en siffersträng på [0, 3, 6, 8, 9], vilken ordning bör din inmatningssekvens vara för att maximera den körtid som krävs för sortering? Övningsproblem Sortera arrayen [0, 1, 4, 5, 2, 3, 7, 9, 8] i sin stigande ordning med hjälp av insättningssortering för Java.
Slutsats
Den största utmaningen med att förstå insättningssorteringen är att förstå hur processen fungerar. När du väl har kläm på det, är det en plätt att förvandla mallen till kod. Så länge du övar och återkommer med relevanta övningsproblem över tid, kommer du snabbt att förbättra din insättningssorteringshastighet.
Låt oss ta en närmare titt på ingången och utmatningen av infogningssort:
GO TO FULL VERSION