Tipo de inserción

Posted on by Rudeus Greyrat
 

La clasificación por inserción es un algoritmo de clasificación simple que funciona de manera similar a la forma en que clasifica las cartas en sus manos. La array se divide virtualmente en una parte ordenada y otra no ordenada. Los valores de la parte no ordenada se seleccionan y colocan en la posición correcta en la parte ordenada.

Características de la ordenación por inserción:

  • Este algoritmo es uno de los algoritmos más simples con una implementación simple.
  • Básicamente, la ordenación por inserción es eficiente para valores de datos pequeños
  • La ordenación por inserción es de naturaleza adaptativa, es decir, es adecuada para conjuntos de datos que ya están parcialmente ordenados.

Funcionamiento del algoritmo de ordenación por inserción:

Considere un ejemplo: arr[]: {12, 11, 13, 5, 6}

Haga clic aquí para el curso completo!
   12       11       13       5       6   

Primer pase:

  • Inicialmente, los primeros dos elementos de la array se comparan en el ordenamiento por inserción.
   12       11       13       5       6   
  • Aquí, 12 es mayor que 11, por lo que no están en orden ascendente y 12 no está en su posición correcta. Por lo tanto, intercambie 11 y 12.
  • Entonces, por ahora 11 se almacena en un subconjunto ordenado.
   11       12       13       5       6   

Segundo pase:

  •  Ahora, pase a los siguientes dos elementos y compárelos.
   11       12       13       5       6   
  • Aquí, 13 es mayor que 12, por lo que ambos elementos parecen estar en orden ascendente, por lo tanto, no se producirá ningún intercambio. 12 también almacenados en un subconjunto ordenado junto con 11

Tercer Pase:

  • Ahora, dos elementos están presentes en el subconjunto ordenado que son 11 y 12
  • Avanzando hacia los siguientes dos elementos que son 13 y 5
   11       12       13       5       6   
  • Tanto el 5 como el 13 no están presentes en su lugar correcto, así que cámbielos
   11       12       5       13       6   
  • Después del intercambio, los elementos 12 y 5 no se ordenan, por lo tanto, vuelva a intercambiar
   11       5       12       13       6   
  • Aquí, nuevamente 11 y 5 no están ordenados, por lo tanto, intercambie nuevamente
   5       11       12       13       6   
  • aquí, está en su posición correcta

Cuarto Pase:

  • Ahora, los elementos que están presentes en el subconjunto ordenado son 5, 11 y 12
  • Pasando a los siguientes dos elementos 13 y 6
   5       11       12       13       6   
  • Claramente, no están ordenados, por lo tanto, realice un intercambio entre ambos.
   5       11       12       6       13   
  • Ahora, 6 es más pequeño que 12, por lo tanto, cambia de nuevo
   5       11       6       12       13   
  • Aquí, también el intercambio hace que 11 y 6 no estén ordenados, por lo tanto, intercambie nuevamente
   5       6       11       12       13   
  • Finalmente, la array está completamente ordenada.

Complete Interview Preparation - GFG

Ilustraciones:

insertion-sort
 

Algoritmo de clasificación por inserción 

Para ordenar una array de tamaño N en orden ascendente: 

  • Iterar de arr[1] a arr[N] sobre la array. 
  • Compare el elemento actual (clave) con su predecesor. 
  • Si el elemento clave es más pequeño que su predecesor, compárelo con los elementos anteriores. Mueva los elementos más grandes una posición hacia arriba para hacer espacio para el elemento intercambiado.
 

A continuación se muestra la implementación:

C++

// C++ program for insertion sort
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to sort an array using 
// insertion sort
void insertionSort(int arr[], int n) 
{ 
    int i, key, j; 
    for (i = 1; i < n; i++)
    { 
        key = arr[i]; 
        j = i - 1; 
  
        // Move elements of arr[0..i-1],  
        // that are greater than key, to one 
        // position ahead of their 
        // current position
        while (j >= 0 && arr[j] > key)
        { 
            arr[j + 1] = arr[j]; 
            j = j - 1; 
        } 
        arr[j + 1] = key; 
    } 
} 
  
// A utility function to print an array 
// of size n 
void printArray(int arr[], int n) 
{ 
    int i; 
    for (i = 0; i < n; i++) 
        cout << arr[i] << " "; 
    cout << endl;
} 
  
// Driver code
int main() 
{ 
    int arr[] = { 12, 11, 13, 5, 6 }; 
    int N = sizeof(arr) / sizeof(arr[0]); 
  
    insertionSort(arr, N); 
    printArray(arr, N); 
  
    return 0; 
} 
// This is code is contributed by rathbhupendra

C

// C program for insertion sort
#include <math.h>
#include <stdio.h>
  
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
  
        /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
  
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
  
/* Driver program to test insertion sort */
int main()
{
    int arr[] = { 12, 11, 13, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    insertionSort(arr, n);
    printArray(arr, n);
  
    return 0;
}

Java

// Java program for implementation of Insertion Sort
class InsertionSort {
    /*Function to sort array using insertion sort*/
    void sort(int arr[])
    {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;
  
            /* Move elements of arr[0..i-1], that are
               greater than key, to one position ahead
               of their current position */
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
  
    /* A utility function to print array of size n*/
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
  
        System.out.println();
    }
  
    // Driver method
    public static void main(String args[])
    {
        int arr[] = { 12, 11, 13, 5, 6 };
  
        InsertionSort ob = new InsertionSort();
        ob.sort(arr);
  
        printArray(arr);
    }
} /* This code is contributed by Rajat Mishra. */

Python

# Python program for implementation of Insertion Sort
  
# Function to do insertion sort
def insertionSort(arr):
  
    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)):
  
        key = arr[i]
  
        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i-1
        while j >= 0 and key < arr[j] :
                arr[j + 1] = arr[j]
                j -= 1
        arr[j + 1] = key
  
  
# Driver code to test above
arr = [12, 11, 13, 5, 6]
insertionSort(arr)
for i in range(len(arr)):
    print ("% d" % arr[i])
  
# This code is contributed by Mohit Kumra

C#

// C# program for implementation of Insertion Sort
using System;
  
class InsertionSort {
  
    // Function to sort array
    // using insertion sort
    void sort(int[] arr)
    {
        int n = arr.Length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;
  
            // Move elements of arr[0..i-1],
            // that are greater than key,
            // to one position ahead of
            // their current position
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
  
    // A utility function to print
    // array of size n
    static void printArray(int[] arr)
    {
        int n = arr.Length;
        for (int i = 0; i < n; ++i)
            Console.Write(arr[i] + " ");
  
        Console.Write("\n");
    }
  
    // Driver Code
    public static void Main()
    {
        int[] arr = { 12, 11, 13, 5, 6 };
        InsertionSort ob = new InsertionSort();
        ob.sort(arr);
        printArray(arr);
    }
}
  
// This code is contributed by ChitraNayal.

PHP

<?php 
// PHP program for insertion sort
  
// Function to sort an array
// using insertion sort
function insertionSort(&$arr, $n)
{
    for ($i = 1; $i < $n; $i++)
    {
        $key = $arr[$i];
        $j = $i-1;
      
        // Move elements of arr[0..i-1],
        // that are    greater than key, to 
        // one position ahead of their 
        // current position
        while ($j >= 0 && $arr[$j] > $key)
        {
            $arr[$j + 1] = $arr[$j];
            $j = $j - 1;
        }
          
        $arr[$j + 1] = $key;
    }
}
  
// A utility function to
// print an array of size n
function printArray(&$arr, $n)
{
    for ($i = 0; $i < $n; $i++)
        echo $arr[$i]." ";
    echo "\n";
}
  
// Driver Code
$arr = array(12, 11, 13, 5, 6);
$n = sizeof($arr);
insertionSort($arr, $n);
printArray($arr, $n);
  
// This code is contributed by ChitraNayal.
?>

JavaScript

<script>
// Javascript program for insertion sort  
    
// Function to sort an array using insertion sort
function insertionSort(arr, n)  
{  
    let i, key, j;  
    for (i = 1; i < n; i++) 
    {  
        key = arr[i];  
        j = i - 1;  
    
        /* Move elements of arr[0..i-1], that are  
        greater than key, to one position ahead  
        of their current position */
        while (j >= 0 && arr[j] > key) 
        {  
            arr[j + 1] = arr[j];  
            j = j - 1;  
        }  
        arr[j + 1] = key;  
    }  
}  
    
// A utility function to print an array of size n  
function printArray(arr, n)  
{  
    let i;  
    for (i = 0; i < n; i++)  
        document.write(arr[i] + " ");  
    document.write("<br>"); 
}  
    
// Driver code 
    let arr = [12, 11, 13, 5, 6 ];  
    let n = arr.length;  
    
    insertionSort(arr, n);  
    printArray(arr, n);  
      
// This code is contributed by Mayank Tyagi
    
</script>
Producción

5 6 11 12 13

Complejidad de tiempo: O(N^2) 
Espacio auxiliar: O(1)

¿Qué son los casos límite del algoritmo de ordenación por inserción?

La ordenación por inserción toma el tiempo máximo para ordenar si los elementos se ordenan en orden inverso. Y lleva un tiempo mínimo (Orden de n) cuando los elementos ya están ordenados. 

¿Cuáles son los paradigmas algorítmicos del algoritmo de ordenación por inserción?

El algoritmo de ordenación por inserción sigue un enfoque incremental.

¿Es la clasificación por inserción un algoritmo de clasificación en el lugar?

Sí, la clasificación por inserción es un algoritmo de clasificación en el lugar.

¿Es la ordenación por inserción un algoritmo estable?

Sí, la ordenación por inserción es un algoritmo de ordenación estable.

¿Cuándo se utiliza el algoritmo de ordenación por inserción?

La ordenación por inserción se usa cuando el número de elementos es pequeño. También puede ser útil cuando la array de entrada está casi ordenada, solo unos pocos elementos están fuera de lugar en una array grande completa.

¿Qué es la ordenación por inserción binaria? 

Podemos usar la búsqueda binaria para reducir el número de comparaciones en la ordenación por inserción normal. La ordenación por inserción binaria utiliza la búsqueda binaria para encontrar la ubicación adecuada para insertar el elemento seleccionado en cada iteración. En la inserción normal, la clasificación toma O(i) (en la i-ésima iteración) en el peor de los casos. Podemos reducirlo a O(logi) mediante la búsqueda binaria. El algoritmo, en su conjunto, todavía tiene un tiempo de ejecución en el peor de los casos de O(n^2) debido a la serie de intercambios necesarios para cada inserción. Consulte esto para la implementación.

¿Cómo implementar la ordenación por inserción para la lista enlazada? 

A continuación se muestra un algoritmo de clasificación de inserción simple para la lista vinculada. 

  • Crear una lista ordenada (o de resultados) vacía
  • Recorra la lista dada, haga lo siguiente para cada Node.
    • Inserte el Node actual de forma ordenada en la lista ordenada o de resultados.
  • Cambie el encabezado de la lista vinculada dada al encabezado de la lista ordenada (o de resultados). 

Consulte esto para la implementación.
  
 

Instantáneas: Cuestionario sobre clasificación por inserción

Otros algoritmos de clasificación en GeeksforGeeks/GeeksQuiz Clasificación por
selección Clasificación por burbuja Clasificación por inserción Clasificación por fusión Clasificación en montón Clasificación rápida Clasificación por radix Clasificación por conteo Clasificación en cubo Clasificación en shell Clasificación en peine

Práctica de codificación para la clasificación.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *