Clasificación por inserción recursiva

La clasificación por inserción es un algoritmo de clasificación simple que funciona de la misma manera que clasificamos las cartas en nuestras manos. A continuación se muestra un algoritmo iterativo para el algoritmo
de ordenación por inserción
 

// Sort an arr[] of size n
insertionSort(arr, n) 
    Loop from i = 1 to n-1.
       a) Pick element arr[i] and insert
          it into sorted sequence arr[0..i-1] 

Ejemplo: 
 

insertion-sort

Consulte Clasificación por inserción para obtener más detalles.
¿Cómo implementarlo recursivamente?  
La ordenación por inserción recursiva no tiene ventajas de rendimiento/implementación, pero puede ser una buena pregunta para verificar la comprensión de la ordenación por inserción y la recursividad.
Si echamos un vistazo más de cerca al algoritmo de ordenación por inserción, mantenemos los elementos procesados ​​ordenados e insertamos nuevos elementos uno por uno en la array ordenada.
Idea de recursividad. 
 

  1. Caso base: si el tamaño de la array es 1 o menor, regrese.
  2. Ordenar recursivamente los primeros elementos n-1.
  3. Inserte el último elemento en su posición correcta en la array ordenada.

A continuación se muestra la implementación de la idea anterior.
 

C++

// Recursive C++ program for insertion sort
#include <iostream>
using namespace std;
 
// Recursive function to sort an array using
// insertion sort
void insertionSortRecursive(int arr[], int n)
{
    // Base case
    if (n <= 1)
        return;
 
    // Sort first n-1 elements
    insertionSortRecursive( arr, n-1 );
 
    // Insert last element at its correct position
    // in sorted array.
    int last = arr[n-1];
    int j = n-2;
 
    /* 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] > last)
    {
        arr[j+1] = arr[j];
        j--;
    }
    arr[j+1] = last;
}
 
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
    for (int i=0; i < n; i++)
        cout << arr[i] <<" ";
}
 
/* Driver program to test insertion sort */
int main()
{
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
 
    insertionSortRecursive(arr, n);
    printArray(arr, n);
 
    return 0;
}

C

#include <stdio.h>
 
// Recursive function to sort an array using
// insertion sort
void insertionSortRecursive(int arr[], int n)
{
    // Base case
    if (n <= 1)
        return;
 
    // Sort first n-1 elements
    insertionSortRecursive(arr, n - 1);
 
    // Insert last element at its correct position
    // in sorted array.
    int last = arr[n - 1];
    int j = n - 2;
 
    /* 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] > last) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = last;
}
 
// A utility function to print an array of size n
void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; 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]);
 
    insertionSortRecursive(arr, n);
    printArray(arr, n);
 
    return 0;
}
 
// This code is contributed by pariveshsrivastava1093

Java

// Recursive Java program for insertion sort
 
import java.util.Arrays;
 
public class GFG
{
    // Recursive function to sort an array using
    // insertion sort
    static void insertionSortRecursive(int arr[], int n)
    {
        // Base case
        if (n <= 1)
            return;
      
        // Sort first n-1 elements
        insertionSortRecursive( arr, n-1 );
      
        // Insert last element at its correct position
        // in sorted array.
        int last = arr[n-1];
        int j = n-2;
      
        /* 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] > last)
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = last;
    }
     
    // Driver Method
    public static void main(String[] args)
    {
        int arr[] = {12, 11, 13, 5, 6};
      
        insertionSortRecursive(arr, arr.length);
         
        System.out.println(Arrays.toString(arr));
    }
}

Python3

# Recursive Python program for insertion sort
# Recursive function to sort an array using insertion sort
 
def insertionSortRecursive(arr,n):
    # base case
    if n<=1:
        return
     
    # Sort first n-1 elements
    insertionSortRecursive(arr,n-1)
    '''Insert last element at its correct position
        in sorted array.'''
    last = arr[n-1]
    j = n-2
     
      # Move elements of arr[0..i-1], that are
      # greater than key, to one position ahead
      # of their current position
    while (j>=0 and arr[j]>last):
        arr[j+1] = arr[j]
        j = j-1
 
    arr[j+1]=last
     
# A utility function to print an array of size n
def printArray(arr,n):
    for i in range(n):
        print(arr[i],end=" ")
 
# Driver program to test insertion sort
arr = [12,11,13,5,6]
n = len(arr)
insertionSortRecursive(arr, n)
printArray(arr, n)
 
# Contributed by Harsh Valecha

C#

// Recursive C# program
// for insertion sort
using System;
 
class GFG
{
 
    // Recursive function to sort
    // an array using insertion sort
    static void insertionSortRecursive(int []arr,
                                       int n)
    {
        // Base case
        if (n <= 1)
            return;
     
        // Sort first n-1 elements
        insertionSortRecursive(arr, n - 1);
     
        // Insert last element at
        // its correct position
        // in sorted array.
        int last = arr[n - 1];
        int j = n - 2;
     
        /* 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] > last)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = last;
    }
     
    //Driver Code
    static void Main()
    {
        int []arr = {12, 11, 13, 5, 6};
     
        insertionSortRecursive(arr, arr.Length);
         
        for(int i = 0; i < arr.Length; i++)
        Console.Write(arr[i] + " ");
    }
}
 
// This code is contributed by Sam007

PHP

<?php
// Recursive PHP program for insertion sort
 
    // Recursive function to sort an
    // array using insertion sort
    function insertionSortRecursive(&$arr, $n)
    {
         
        // Base case
        if ($n <= 1)
            return;
     
        // Sort first n-1 elements
        insertionSortRecursive($arr, $n - 1);
     
        // Insert last element at its correct
        // position in sorted array.
        $last = $arr[$n - 1];
        $j = $n - 2;
     
        // 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] > $last)
        {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $last;
    }
     
    // A utility function to
    // print an array of size n
    function printArray(&$arr, $n)
    {
        for ($i = 0; $i < $n; $i++)
            echo $arr[$i]." ";
    }
 
// Driver Code
$arr = array(12, 11, 13, 5, 6);
$n = sizeof($arr);
 
insertionSortRecursive($arr, $n);
printArray($arr, $n);
 
// This code is contributed by ChitraNayal.
?>

Javascript

<script>
 
// Recursive Javascript program for
// insertion sort
 
    // Recursive function to sort an
    //array using insertion sort
    function insertionSortRecursive(arr,n)
    {
        // Base case
        if (n <= 1)
            return;
        
        // Sort first n-1 elements
        insertionSortRecursive( arr, n-1 );
        
        // Insert last element at its
        // correct position in sorted array.
        let last = arr[n-1];
        let j = n-2;
        
        /* 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] > last)
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = last;
    }
     
    // Driver Method
    let arr=[12, 11, 13, 5, 6];
    insertionSortRecursive(arr, arr.length);
     
    for(let i=0;i<arr.length;i++)
    {
        document.write(arr[i]+" ");
    }
     
     
    // This code is contributed by rag2127
 
</script>

Producción : 

5 6 11 12 13 

Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(n)

Echa un vistazo al curso de autoaprendizaje de DSA

Este artículo es una contribución de Sahil Chhabra (akku) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema discutido anteriormente. sobre el tema discutido anteriormente
 

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 *