- Vështrim i përgjithshëm
- Algoritmi i përgjithshëm
- Pseudokodi
- Ilustrim
- Shembull C++
- Java Example
- Complexity Analysis Of The Insertion Sort Algorithm
- Conclusion
Një vështrim i thelluar në renditjen e futjes me shembuj klasikë.
Rregullimi i futjes është një teknikë renditjeje e cila mund të shihet në një mënyrë që ne luajmë letra në dorë. Mënyra se si ne futim ndonjë kartë në një kuvertë ose e heqim atë, renditja e futjes funksionon në mënyrë të ngjashme.
Teknika e algoritmit të renditjes së futjes është më efikase se teknikat e renditjes me flluskë dhe renditjes së përzgjedhjes, por është më pak efikase se teknikat e tjera si Quicksort dhe Merge sort.
Vështrim i përgjithshëm
Në teknikën e renditjes së futjes, fillojmë nga elementi i dytë dhe e krahasojmë me elementin e parë dhe e vendosim në vendin e duhur. Më pas e kryejmë këtë proces për elementët pasardhës.
Ne e krahasojmë çdo element me të gjithë elementët e tij të mëparshëm dhe e vendosim ose e fusim elementin në pozicionin e duhur. Teknika e renditjes së futjes është më e realizueshme për vargje me një numër më të vogël elementësh. Është gjithashtu i dobishëm për renditjen e listave të lidhura.
Listat e lidhura kanë një tregues për elementin tjetër (në rastin e një liste të lidhur vetëm) dhe një tregues gjithashtu për elementin e mëparshëm (në rastin e një liste të lidhur dyfish ). Prandaj, bëhet më e lehtë të zbatohet renditja e futjes për një listë të lidhur.
Le të shqyrtojmë gjithçka rreth renditjes së futjes në këtë tutorial.
Algoritmi i përgjithshëm
Hapi 1 : Përsëritni hapat 2 deri në 5 për K = 1 deri në N-1
Hapi 2 : caktoni temperaturën = A[K]
Hapi 3 : vendosni J = K– 1
Hapi 4 : Përsëriteni ndërsa temp =A[J]
caktoni A[J + 1] = A[J]
vendosja J = J – 1
[fundi i lakut të brendshëm]
Hapi 5 : vendos A[J + 1] = temp
[ fundi i ciklit]
Hapi 6 : dalje
Kështu, në teknikën e renditjes së futjes, fillojmë nga elementi i dytë pasi supozojmë se elementi i parë është gjithmonë i renditur . Pastaj nga elementi i dytë deri te elementi i fundit, ne krahasojmë secilin element me të gjithë elementët e tij të mëparshëm dhe e vendosim atë element në pozicionin e duhur.
Pseudokodi
Pseudokodi për renditja e futjes është dhënë më poshtë.
procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array[i] freePosition = i //locate free position to insert the element whilefreePosition> 0 and array[freePosition -1] >insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //insert the number at free position array [freePosition] = insert_val end for end procedure
I dhënë më sipër është pseudokodi për renditjen e futjes, më pas, ne do ta ilustrojmë këtë teknikë në shembullin e mëposhtëm.
Ilustrim
Rrethimi që do të renditet është si më poshtë:
Tani për çdo kalim, ne krahasojmë elementin aktual me të gjithë elementët e tij të mëparshëm. Pra, në kalimin e parë, fillojmë me elementin e dytë.
Kështu ne kërkojmë N numër kalimesh për të renditur plotësisht një grup që përmban N numër elementesh.
0> Ilustrimi i mësipërm mund të përmblidhet në një formë tabelare:
| Pass | Lista e pazgjidhur | krahasimi | Renditurlista |
|---|---|---|---|
| 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} |
Siç tregohet në Në ilustrimin e mësipërm, fillojmë me elementin e dytë pasi supozojmë se elementi i parë është gjithmonë i renditur. Pra, fillojmë me krahasimin e elementit të dytë me të parin dhe ndërrojmë pozicionin nëse elementi i dytë është më i vogël se i pari.
Ky proces krahasimi dhe ndërrimi i pozicionon dy elementë në vendet e tyre të duhura. Më pas, ne krahasojmë elementin e tretë me elementët e tij të mëparshëm (të parë dhe të dytë) dhe kryejmë të njëjtën procedurë për të vendosur elementin e tretë në vendin e duhur.
Në këtë mënyrë, për çdo kalim, vendosim një element në vendin e saj. Për kalimin e parë, ne vendosim elementin e dytë në vendin e tij. Kështu në përgjithësi, për të vendosur N elementë në vendin e tyre të duhur, na duhen kalimet N-1.
Më pas, do të demonstrojmë zbatimin e teknikës së renditjes së futjes në gjuhën C++.
Shembull C++
#include using namespace std; int main () { int myarray[10] = { 12,4,3,1,15,45,33,21,10,2}; cout"\nInput list is \n"; for(int i=0;i10;i++) { cout ="" Output:
Input list is
12 4 3 1 15 45 33 21 10 2
Sorted list is
1 2 3 4 10 12 15 21 33 45
Next, we will see the Java implementation of the Insertion sort technique.
Java Example
public class Main { public static void main(String[] args) { int[] myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println("Input list of elements ..."); for(int i=0;i10;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("\nsorted list of elements ..."); for(int i=0;i10;i++) { System.out.print(myarray[i] + " "); } } } Output:
Input list of elements …
12 4 3 1 15 45 33 21 10 2
sorted list of elements …
1 2 3 4 10 12 15 21 33 45
In both the implementations, we can see that we begin sorting from the 2nd element of the array (loop variable j = 1) and repeatedly compare the current element to all its previous elements and then sort the element to place it in its correct position if the current element is not in order with all its previous elements.
Insertion sort works the best and can be completed in fewer passes if the array is partially sorted. But as the list grows bigger, its performance decreases. Another advantage of Insertion sort is that it is a Stable sort which means it maintains the order of equal elements in the list.
Complexity Analysis Of The Insertion Sort Algorithm
From the pseudo code and the illustration above, insertion sort is the efficient algorithm when compared to bubble sort or selection sort. Instead of using for loop and present conditions, it uses a while loop that does not perform any more extra steps when the array is sorted.
However, even if we pass the sorted array to the Insertion sort technique, it will still execute the outer for loop thereby requiring n number of steps to sort an already sorted array. This makes the best time complexity of insertion sort a linear function of N where N is the number of elements in the array.
Thus the various complexities for Insertion sort technique are given below:
Worst case time complexity O(n 2 ) Best case time complexity O(n) Average time complexity O(n 2 ) Space complexity O(1)
In spite of these complexities, we can still conclude that Insertion sort is the most efficient algorithm when compared with the other sorting techniques like Bubble sort and Selection sort.
Conclusion
Insertion sort is the most efficient of all the three techniques discussed so far. Here, we assume that the first element is sorted and then repeatedly compare every element to all its previous elements and then place the current element in its correct position in the array.
In this tutorial, while discussing Insertion sort we have noticed that we compare the elements using an increment of 1 and also they are contiguous. This feature results in requiring more passes to get the sorted list.
In our upcoming tutorial, we will discuss “Shell sort” which is an improvement over the Selection sort.
In shell sort, we introduce a variable known as “increment” or a “gap” using which we divide the list into sublists containing non-contiguous elements that “gap” apart. Shell sort requires fewer passes when compared to Insertion sort and is also faster.
In our future tutorials, we will learn about two sorting techniques, “Quicksort” and “Mergesort” which use “Divide and conquer” strategy for sorting data lists.