- Oversigt
- Generel algoritme
- Pseudokode
- Illustration
- C++ eksempel
- Java eksempel
- Kompleksitetsanalyse af algoritmen til indsættelse af sorteringsalgoritmen
- Konklusion
En dybdegående gennemgang af indsætningssortering med klassiske eksempler.
Indsætningssortering er en sorteringsteknik, som kan ses på samme måde som når vi spiller kort i hånden. På samme måde som vi indsætter eller fjerner et kort i et spil, fungerer indsætningssortering på samme måde.
Indsættelse af sorteringsalgoritmen er mere effektiv end Bubble Sort- og Selection Sort-teknikkerne, men mindre effektiv end andre teknikker som Quicksort og Merge Sort.
Oversigt
I indsættelsessorteringsteknikken starter vi med det andet element og sammenligner det med det første element og placerer det på et passende sted. Derefter udfører vi denne proces for de efterfølgende elementer.
Vi sammenligner hvert element med alle dets tidligere elementer og placerer eller indsætter elementet på den rigtige plads. Indsætningssorteringsteknikken er mere anvendelig for arrays med et mindre antal elementer. Den er også nyttig til sortering af linkede lister.
Sammenkædede lister har en pegepind til det næste element (i tilfælde af en enkeltkoblet liste) og en pegepind til det foregående element (i tilfælde af en dobbeltkoblet liste). Det er derfor lettere at implementere indsættelsessortering for en sammenkoblet liste.
Lad os udforske alt om indsætningssortering i denne vejledning.
Generel algoritme
Trin 1 : Gentag trin 2 til 5 for K = 1 til N-1
Trin 2 : sæt temp = A[K]
Trin 3 : sæt J = K - 1
Trin 4 : Gentag mens temp <=A[J]
sæt A[J + 1] = A[J]
sæt J = J - 1
[slutningen af den indre sløjfe]
Trin 5 : sæt A[J + 1] = temp
[slutningen af løkken]
Trin 6 : exit
I indsættelsessorteringsteknikken starter vi således fra det andet element, da vi antager, at det første element altid er sorteret. Fra det andet element til det sidste element sammenligner vi derefter hvert element med alle dets tidligere elementer og placerer det pågældende element på den rigtige plads.
Pseudokode
Pseudokoden for indsætningssortering er angivet nedenfor.
procedure insertionSort(array,N ) array - array, der skal sorteres N- antal elementer begin int freePosition int insert_val for i = 1 til N -1 do: insert_val = array[i] freePosition = i //placere fri position til at indsætte elementet whilefreePosition> 0 and array[freePosition -1]>insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //indsætte elementetnummer på fri position array [freePosition] = insert_val end for end procedure end
Ovenstående er pseudokoden for indsætningssortering, og vi vil nu illustrere denne teknik i følgende eksempel.
Illustration
Det array, der skal sorteres, er som følger:
For hvert gennemløb sammenligner vi det aktuelle element med alle de foregående elementer. I det første gennemløb starter vi med det andet element.
Vi har således brug for N antal gennemløb for at sortere et array med N antal elementer fuldstændigt.
Ovenstående illustration kan sammenfattes i en tabelform:
| Pass | Usorteret liste | sammenligning | Sorteret liste |
|---|---|---|---|
| 1 | {12,3,5,10,8,1} | {12,3} | {3,12,5,10,8,1} |
| 2 | {3,12,5,10,8,1} | {3,12,5} | {3,5,12,10,8,1} |
| 3 | {3,5,12,10,8,1} | {3,5,12,10} | {3,5,10,12,8,1} |
| 4 | {3,5,10,12,8,1} | {3,5,10,12,8} | {3,5,8,10,12,1} |
| 5 | {3,5,8,10,12,1} | {3,5,8,10,12,1} | {1,3,5,8,10,12} |
| 6 | {} | {} | {1,3,5,8,10,12} |
Som vist i illustrationen ovenfor begynder vi med det andet element, da vi antager, at det første element altid er sorteret. Vi begynder derfor med at sammenligne det andet element med det første og bytter positionen, hvis det andet element er mindre end det første.
Denne sammenlignings- og bytteproces placerer to elementer på deres rette plads. Dernæst sammenligner vi det tredje element med de foregående (første og andet) elementer og udfører den samme procedure for at placere det tredje element på den rette plads.
På denne måde placerer vi et element på dets plads i hvert gennemløb. I det første gennemløb placerer vi det andet element på dets plads. For at placere N elementer på deres rette plads skal vi således generelt bruge N-1 gennemløb.
Dernæst vil vi demonstrere implementeringen af Insertion Sort-teknikken i C++-sproget.
C++ eksempel
#include using namespace std; int main () { int myarray[10] = { 12,4,3,3,1,1,15,45,33,21,10,2}; cout<<"\nInputlisten er \n"; for(int i=0;i<10;i++) { cout < ="" Output:
Indtastningslisten er
12 4 3 1 15 45 33 21 10 2
Sorteret liste er
1 2 3 4 10 12 15 21 33 45
Dernæst vil vi se Java-implementeringen af indsætningssorteringsteknikken.
Java eksempel
public class Main { public static void main(String[] args) { int[] myarray = {12,4,3,3,1,15,45,33,21,10,2}; System.out.println("Input-liste over elementer ..."); for(int i=0;i<10;i++) { System.out.print(myarray[i] + " "); } for(int k=1; k=0 && temp <= myarray[j]) { myarray[j+1] = myarray[j]; j = j-1; } myarray[j+1] = temp; } System.out.println("\nsorteret liste over elementer ..."); for(inti=0;i<10;i++) { System.out.print(myarray[i] + " "); } } } Output:
Indtastning af en liste af elementer ...
12 4 3 1 15 45 33 21 10 2
sorteret liste over elementer ...
1 2 3 4 10 12 15 21 33 45
I begge implementeringer kan vi se, at vi begynder at sortere fra det andet element i arrayet (løkkevariabel j = 1) og gentagne gange sammenligner det aktuelle element med alle dets tidligere elementer og derefter sorterer elementet for at placere det på den korrekte position, hvis det aktuelle element ikke er i rækkefølge med alle dets tidligere elementer.
Insertion sortering fungerer bedst og kan gennemføres i færre omgange, hvis arrayet er delvist sorteret. Men når listen bliver større, falder ydelsen. En anden fordel ved Insertion sortering er, at det er en stabil sortering, hvilket betyder, at den bevarer rækkefølgen af ens elementer i listen.
Kompleksitetsanalyse af algoritmen til indsættelse af sorteringsalgoritmen
Ud fra pseudokoden og illustrationen ovenfor er insertion sort den effektive algoritme sammenlignet med bubble sort eller selection sort. I stedet for at bruge for loop og nuværende betingelser bruger den en while loop, som ikke udfører flere ekstra trin, når arrayet er sorteret.
Men selv hvis vi sender det sorterede array til indsættelsessorteringsteknikken, vil den stadig udføre den ydre for-loop og dermed kræve n antal trin for at sortere et allerede sorteret array. Dette gør den bedste tidskompleksitet for indsættelsessortering til en lineær funktion af N, hvor N er antallet af elementer i arrayet.
De forskellige kompleksiteter ved indsættelse af sorteringsteknikken er således angivet nedenfor:
Tidskompleksitet i værste tilfælde O(n 2 ) Tidskompleksitet i bedste fald O(n) Gennemsnitlig tidskompleksitet O(n 2 ) Kompleksitet i rummet O(1)
På trods af disse kompleksiteter kan vi stadig konkludere, at Insertion sort er den mest effektive algoritme sammenlignet med de andre sorteringsteknikker som Bubble sort og Selection sort.
Konklusion
Indsætningssortering er den mest effektive af alle de tre hidtil diskuterede teknikker. Her antager vi, at det første element er sorteret, hvorefter vi gentagne gange sammenligner hvert element med alle dets tidligere elementer og derefter placerer det aktuelle element på den korrekte position i arrayet.
I denne vejledning har vi under diskussionen af Insertion sort bemærket, at vi sammenligner elementerne ved hjælp af en stigning på 1, og at de også er sammenhængende. Denne funktion resulterer i, at der kræves flere gennemløb for at få den sorterede liste.
I vores kommende vejledning vil vi diskutere "Shell sortering", som er en forbedring af Selection sortering.
I shell-sortering indfører vi en variabel kaldet "increment" eller et "gap", hvormed vi opdeler listen i dellister, der indeholder ikke-sammenhængende elementer, som "gap" fra hinanden. Shell-sortering kræver færre gennemløb sammenlignet med Insertion-sortering og er også hurtigere.
I vores fremtidige tutorials vil vi lære om to sorteringsteknikker, "Quicksort" og "Mergesort", som bruger "Divide and conquer"-strategien til at sortere datalister.