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:
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.
- Caso base: si el tamaño de la array es 1 o menor, regrese.
- Ordenar recursivamente los primeros elementos n-1.
- 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