Gruntle Software & Testing

Ordenar por inserción en C++ con exemplos

Por Stewart TristianPublicado en Publicado en Guías

Unha ollada en profundidade á clasificación por inserción con exemplos clásicos.

A clasificación por inserción é unha técnica de clasificación que se pode ver dun xeito que xogamos ás cartas a man. A forma en que inserimos calquera tarxeta nunha baralla ou a eliminamos, as clasificacións de inserción funcionan dun xeito similar.

A técnica do algoritmo de clasificación por inserción é máis eficiente que as técnicas de ordenación de burbulla e selección, pero é menos eficiente que as outras técnicas. como Quicksort e Merge sort.

Visión xeral

Na técnica de ordenación por inserción, partimos do segundo elemento e comparámolo co primeiro elemento e poñémolo nun lugar axeitado. Despois realizamos este proceso para os elementos posteriores.

Comparamos cada elemento con todos os seus elementos anteriores e poñemos ou inserimos o elemento na súa posición correcta. A técnica de ordenación por inserción é máis factible para matrices cun número menor de elementos. Tamén é útil para ordenar listas enlazadas.

As listas enlazadas teñen un punteiro ao seguinte elemento (no caso dunha lista ligada individualmente) e tamén un punteiro ao elemento anterior (no caso dunha lista dobremente ligada). ). Polo tanto, resulta máis doado implementar a ordenación por inserción para unha lista ligada.

Exploremos todo sobre a ordenación por inserción neste tutorial.

Algoritmo xeral

Paso 1 : repita os pasos 2 a 5 para K = 1 a N-1

Paso 2 : establecer temperatura = A[K]

Paso 3 : establece J = K– 1

Paso 4 : Repita mentres a temperatura =A[J]

configura A[J + 1] = A[J]

set J = J – 1

[fin do bucle interno]

Paso 5 : establece A[J + 1] = temp

[ fin do bucle]

Paso 6 : saída

Así, na técnica de ordenación por inserción, partimos do segundo elemento xa que asumimos que o primeiro elemento sempre está ordenado . Despois, dende o segundo elemento ata o último elemento, comparamos cada elemento con todos os seus elementos anteriores e poñemos ese elemento na posición correcta.

Pseudocódigo

O pseudocódigo para A continuación indícase a ordenación por inserción. 

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

Dado arriba o pseudocódigo para a ordenación por inserción, a continuación, ilustraremos esta técnica no seguinte exemplo.

Ilustración

A matriz a ordenar é a seguinte:

Agora para cada pasada, comparamos o elemento actual con todos os seus elementos anteriores. Polo tanto, na primeira pasada, comezamos co segundo elemento.

Por iso, necesitamos N número de pasadas para ordenar completamente unha matriz que contén N número de elementos.

A ilustración anterior pódese resumir nunha táboa:

Pasar Lista sen ordenar comparación Ordenadolista
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}

Como se mostra en na ilustración anterior, comezamos co 2º elemento xa que asumimos que o primeiro elemento sempre está ordenado. Entón comezamos comparando o segundo elemento co primeiro e cambiamos a posición se o segundo elemento é menor que o primeiro.

Este proceso de comparación e intercambio sitúa dous elementos nos seus lugares axeitados. A continuación, comparamos o terceiro elemento cos seus elementos anteriores (primeiro e segundo) e realizamos o mesmo procedemento para colocar o terceiro elemento no lugar axeitado.

Deste xeito, para cada pasada, colocamos un elemento en o seu lugar. Para a primeira pasada, colocamos o segundo elemento no seu lugar. Así, en xeral, para colocar N elementos no seu lugar axeitado, necesitamos N-1 pasadas.

A continuación, demostraremos a implementación da técnica de ordenación por inserción en linguaxe C++.

Exemplo 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.
Desprazarse arriba