Gruntle Software & Testing

Ordenació d'inserció en C++ amb exemples

Per Stewart TristianPublicat el Publicat a Guies

Una mirada en profunditat a l'ordenació per inserció amb exemples clàssics.

L'ordenació per inserció és una tècnica d'ordenació que es pot veure de la manera que juguem a les cartes. La manera com inserim qualsevol carta d'una baralla o la traiem, les ordenacions d'inserció funciona de manera similar.

La tècnica de l'algorisme d'ordenació d'inserció és més eficient que les tècniques d'ordenació de bombolles i selecció, però és menys eficient que les altres tècniques. com Quicksort i Merge sort.

Visió general

En la tècnica d'ordenació per inserció, partim del segon element i el comparem amb el primer element i el posem en un lloc adequat. Després realitzem aquest procés per als elements posteriors.

Comparem cada element amb tots els seus elements anteriors i posem o inserim l'element en la seva posició adequada. La tècnica d'ordenació per inserció és més factible per a matrius amb un nombre menor d'elements. També és útil per ordenar llistes enllaçades.

Les llistes enllaçades tenen un punter a l'element següent (en el cas d'una llista enllaçada individualment) i també un punter a l'element anterior (en cas d'una llista doblement enllaçada). ). Per tant, és més fàcil implementar l'ordenació per inserció per a una llista enllaçada.

Explorem tot sobre l'ordenació per inserció en aquest tutorial.

Algorisme general

Pas 1 : repetiu els passos del 2 al 5 per a K = 1 a N-1

Pas 2 : establiu la temperatura = A[K]

Pas 3 : establiu J = K– 1

Pas 4 : Repetiu mentre la temperatura =A[J]

estableix A[J + 1] = A[J]

set J = J – 1

[final del bucle interior]

Pas 5 : establiu A[J + 1] = temp

[ final del bucle]

Pas 6 : sortida

Així, en la tècnica d'ordenació per inserció, partim del segon element ja que suposem que el primer element sempre està ordenat . A continuació, des del segon element fins a l'últim element, comparem cada element amb tots els seus elements anteriors i posem aquest element a la posició adequada.

Pseudocodi

El pseudocodi per a A continuació es mostra l'ordenació d'inserció. 

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

A dalt és el pseudocodi per a l'ordenació d'inserció, a continuació, il·lustrarem aquesta tècnica en l'exemple següent.

Il·lustració

La matriu a ordenar és la següent:

Ara per a cada passada, comparem l'element actual amb tots els seus elements anteriors. Per tant, a la primera passada, comencem amb el segon element.

Per tant, necessitem N nombre de passades per ordenar completament una matriu que conté N nombre d'elements.

La il·lustració anterior es pot resumir en forma de taula:

Passa Llista no ordenada comparació Ordenatllista
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}

Com es mostra a la il·lustració anterior, comencem amb el segon element ja que suposem que el primer element sempre està ordenat. Per tant, comencem comparant el segon element amb el primer i intercanviem la posició si el segon element és menor que el primer.

Aquest procés de comparació i intercanvi situa dos elements en els seus llocs adequats. A continuació, comparem el tercer element amb els seus elements anteriors (primer i segon) i fem el mateix procediment per col·locar el tercer element al lloc adequat.

D'aquesta manera, per a cada passada, col·loquem un element en el seu lloc. Per a la primera passada, col·loquem el segon element al seu lloc. Així, en general, per col·locar N elements al seu lloc adequat, necessitem N-1 passades.

A continuació, demostrarem la implementació de la tècnica d'ordenació d'inserció en llenguatge C++.

Exemple 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 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.
Desplaçar cap amunt