Innsettingssortering i Java

Sortering av matriser er en av de vanligste operasjonene en Java-nybegynner bør vite hvordan de skal gjøre. Selv om arrays ikke alltid er den mest praktiske måten å ordne data på, og dette gjelder for det meste små tall, har konseptet bak array-sortering tonnevis av applikasjoner innen kompleks programvare og datavitenskap. I dette innlegget skal vi se nærmere på hva innsettingssort er. Vi inkluderte noen eksempler og øvingsproblemer for å hjelpe deg med å få taket på dette konseptet.

Hva er innsettingssortering?

I utgangspunktet er innsettingssortering en algoritme utviklere bruker for å organisere strenger med små tall. Den deler alle verdier i to stabler - en sortert og en usortert. En etter en blir tallene i den «usorterte» stabelen plukket ut og satt i riktig rekkefølge. La oss se nærmere på inndata og utdata for innsettingssortering:

• Inndata: en matrise A med usorterte numeriske elementer: A[0,1, n, n-2...].
• Utdata: en matrise som inneholder de samme tallene, men fullstendig sortert. Denne blir vanligvis referert til som B: B[0]B[1]...B[n-1].

Det er en håndfull måter å bruke innsettingssortering på - her er de mest populære:

• Numerisk sortering (økende rekkefølge): [1, 2, 3, 4, 5]
• Numerisk sortering (reduserende rekkefølge): [5, 4, 3, 2, 1]
• Alfabetisk sortering: [a, b, c, d]

Merk: hvis du har en tom matrise eller en singleton, anses disse for å være sortert som standard.

Forstå teorien om innsettingssortering

Før vi utforsker koden bak innsettingssortering, la oss bryte ned algoritmen ved å bruke et ikke-teknisk språk. Fordi vi skal vise koden for sortering i stigende rekkefølge, er det fornuftig å forklare algoritmen trinn for trinn i dette innlegget. Trinn 1. Iterasjon mellom arr[1]og arr[n]hvor ner en numerisk verdi som vanligvis er mindre enn 10. Trinn 2. Sammenlign elementet du valgte (kjent som key) med det forrige tallet i sekvensen ved å bruke metoden sort(). Trinn 3. Hvis alle elementene er mindre enn deres etterfølgere, gjenta sammenligningen til du finner en større verdi. Trinn 4. Bytt en større verdi én posisjon utover den mindre for å lage en ordnet sekvens. Trinn 5. Gjenta prosessen til du får en sortert streng med tegn

Sortering av primitive arrays

Siden algoritmen er en av de mest enkle Java-operasjonene, bør selv nybegynnere ikke ha store problemer med å implementere den. Her er en trinn-for-trinn-veiledning for å sortere en matrise

1. Angi en matrise for sorteringen

Til å begynne med, la oss lage en streng med verdier som vi senere vil vise ved hjelp av Java. For å bruke innsettingssortering, må du opprette en matrise. For det, brukint[]

int[] arrayA = {10, 14, 20, 30};

2. Bruk sort_arr for å implementere algoritmen

Sort_arr-metoden er en av de vanligste måtene å implementere innsettingssortering. I praksis ser det slik ut:

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. Lag en loop og en iterator

Ved å bruke en løkke i innsettingssorteringsalgoritmen, trenger ikke utviklere å gjenta logikken for hvert element. Selv om det virker komplekst å lage looper, er det ganske enkelt - her er et eksempel:

for(int i=0; i< sort_arr.length; ++i){

Nå som du har en fungerende loop, er det på tide å lage en iterator som vil sortere alle elementene i ønsket rekkefølge. Fra nå av vil vi referere til iteratoren som " j".

        int j = i;

4. Opprette en "while loop"

Når det gjelder innsettingssortering, er en "mens"-løkke avgjørende for en ny, sortert matrise. For å sette den opp for en innsettingssortering i stigende rekkefølge, må en utvikler oppfylle to betingelser:

• Verdien tilordnet j må være større enn 0
• Verdien tilordnet j-1må være større enn jindeksen

Så snart begge betingelsene i while-løkken er sanne, vil matrisens nøkkelverdi være lik indeksen j.

5. Sortering av matrisen

Etter at du har satt opp while-løkken, vil verdiene jog j-1byttes om til en eller begge forholdene i while-løkken mislykkes. På samme måte vil sorteringen bli gjentatt for hver verdi i for-løkken inntil for-løkken-betingelsene også mislykkes. Slik fungerer prosessen med innsettingssortering i praksis:

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

Sortering av en ArrayList

Selv om det er viktig å forstå matematikken bak innsettingssortering, vil du sortere ArrayLists mye mer enn sekvenser i primitive arrays når det gjelder programvareutvikling i virkeligheten. Her er en trinn-for-trinn-guide for å sortere en ArrayList:

1. Opprett en ny Elementklasse for elementene som tilhører samlingen.

   
   public class Element {
       private int id;
   
       public Element(int id) {
           this.id = id;
       }
   

2. Innenfor en samling er det en compareTo()metode - vi vil bruke denne til å sammenligne IDene til to elementer.

   
       public int compareTo(Element element) {
           int res = 0;
           if (this.id < element.getId()) {
               res = -1;
           }
           if (this.id > element.getId()) {
               res = 1;
           }
           return res;
       }
   }
   

3. Bruk algoritmen og lag noen løkker for å sortere objektene i en ArrayListi stedet for å sammenligne 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);
       }
   }
   

4. ArrayListDu kan også legge til flere elementer , som vist nedenfor:

   
   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);
   

5. Nå er det tid for sortering:

   
   // 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() + ", "));
   

6. La oss nå sammenligne input og output for å sikre at vi ikke gjorde noen feil. Her er sammenligningen av strengen vi brukte som eksempel.

   
   4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
   

Problemer med innsettingssortering

Nå som du har grepet om denne sorteringsalgoritmen, er det på tide å sette dine teoretiske og praktiske ferdigheter på prøve. Teoriquiz #1 Du får en matrise [1, 4, 6, 8] og legger til et nytt element n = 7 til den. Hvor mange sammenligninger må du gjøre for å få en sortert tallrekke? Angi den endelige verdien av indeks n i matrisen. Teoriquiz #2 På et jobbintervju ber en teamleder deg bevise at sorteringsinnsetting er en ineffektiv metode. Gitt en tallstreng på [0, 3, 6, 8, 9], hva skal rekkefølgen på inndatasekvensen være for å maksimere kjøretiden som kreves for sortering? Øvingsproblem Sorter [0, 1, 4, 5, 2, 3, 7, 9, 8]-matrisen i stigende rekkefølge ved å bruke innsettingssortering for Java.

Konklusjon

Den største utfordringen med å forstå innsettingssortering er å forstå hvordan prosessen fungerer. Når du først har grepet det, er det et stykke kake å gjøre om malen til kode. Så lenge du øver og ser på relevante praksisproblemer over tid, vil du raskt forbedre innsettingssorteringshastigheten.