Gruntle Software & Testing

Innsetning Raða í C++ með dæmum

Eftir Stewart TristianBirt á Birt í Leiðsögumenn

Ítarlega skoðun á innsetningarflokkun með klassískum dæmum.

Innsetningarflokkun er flokkunartækni sem hægt er að skoða á þann hátt að við spilum spil fyrir hendi. Eins og við setjum hvaða spil sem er í stokk eða fjarlægjum það, þá virkar innsetningarröðun á svipaðan hátt.

Innsetningarröðunaralgrímstækni er skilvirkari en kúlaflokkunartæknin og úrvalsflokkunin en er óhagkvæmari en hinar aðferðirnar. eins og Quicksort og Merge sort.

Yfirlit

Í innsetningarröðunartækninni, byrjum við á öðrum þættinum og berum það saman við fyrsta þáttinn og setjum hann inn á réttum stað. Síðan framkvæmum við þetta ferli fyrir síðari þættina.

Við berum hvert frumefni saman við alla fyrri þætti þess og setjum eða setjum þáttinn inn í rétta stöðu. Innsetningarflokkunartækni er framkvæmanlegri fyrir fylki með minni fjölda þátta. Það er einnig gagnlegt til að flokka tengda lista.

Tengdir listar eru með bendi í næsta stak (ef um er að ræða einn tengdan lista) og bendi á fyrri þáttinn líka (ef um er að ræða tvöfalt tengdan lista) ). Þess vegna verður auðveldara að innleiða innsetningarröðun fyrir tengdan lista.

Við skulum kanna allt um innsetningarröðun í þessari kennslu.

Almennt reiknirit

Skref 1 : Endurtaktu skref 2 til 5 fyrir K = 1 til N-1

Skref 2 : stilla hitastig = A[K]

Skref 3 : stilltu J = K– 1

Skref 4 : Endurtaktu meðan hitastig =A[J]

stillir A[J + 1] = A[J]

sett J = J – 1

[enda innri lykkju]

Skref 5 : stillt A[J + 1] = hitastig

[ lok lykkju]

Skref 6 : hætta

Þannig, í innsetningarröðunartækninni, byrjum við frá öðru stakinu þar sem við gerum ráð fyrir að fyrsti þátturinn sé alltaf flokkaður . Síðan, frá öðru staki til síðasta staks, berum við hvert stak saman við alla fyrri þætti þess og setjum það stak í rétta stöðu.

Gervikóði

Gerjukóðinn fyrir innsetningarröðun er gefin upp hér að neðan. 

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

Gefin hér að ofan er gervikóðinn fyrir innsetningarröðun, næst munum við sýna þessa tækni í eftirfarandi dæmi.

Mynd

Fylkið sem á að raða er sem hér segir:

Nú, fyrir hverja leið, berum við núverandi þætti saman við alla fyrri þætti hans. Þannig að í fyrstu umferð, byrjum við á öðru stakinu.

Þannig þurfum við N fjölda sendinga til að raða algjörlega fylki sem inniheldur N fjölda staka.

Hægt er að draga saman myndina hér að ofan í töfluformi:

Pass Óflokkaður listi samanburður Raðaðlisti
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}

Eins og sýnt er í ofangreindri mynd, byrjum við á 2. stakinu þar sem við gerum ráð fyrir að fyrsti þátturinn sé alltaf flokkaður. Þannig að við byrjum á því að bera saman annan þáttinn við þann fyrsta og skipta um stöðu ef annar þátturinn er minni en sá fyrri.

Þetta samanburðar- og skiptiferli staðsetur tvo þætti á sínum rétta stað. Næst berum við saman þriðja þáttinn við fyrri (fyrsta og annan) þætti hans og framkvæmum sömu aðferð til að setja þriðja þáttinn á réttan stað.

Þannig, fyrir hverja umferð, setjum við einn þátt í stað þess. Fyrir fyrstu umferðina setjum við annan þáttinn í staðinn. Þannig að almennt, til að setja N þætti á réttan stað, þurfum við N-1 passa.

Næst munum við sýna innsetningarröðunartæknina í C++ tungumáli.

C++ Dæmi

#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 complexityO(n 2 )
Best case time complexityO(n)
Average time complexityO(n 2 )
Space complexityO(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.
Skruna á topp