La ordenación por inserción es adecuada para arreglos de tamaño pequeño. También logra la complejidad del mejor de los casos de O(n) si las arrays ya están ordenadas. Hemos discutido tanto la ordenación por inserción iterativa como la ordenación por inserción recursiva . En este artículo se analizan implementaciones ligeramente diferentes para las versiones iterativa y recursiva.
Clasificación por inserción iterativa
Veamos el algoritmo para la ordenación por inserción iterativa
function insertionSort(V)
i, j, k
for i from 1..length(V)
k = V[i]
j = i-1
while j > 0 and k < V[j]
V[j+1] = V[j]
j -= 1
V[j] = k
return V
Dentro del ciclo while, cambiamos todos los valores mayores que k en una posición y luego insertamos k en la primera posición donde k es mayor que el valor de la array. Se obtiene el mismo efecto si intercambiamos elementos de array consecutivos. Al intercambiar repetidamente, k viajará a su posición correcta.
Tomemos un ejemplo para ilustrar esto
Insert 3 in A = {1, 2, 4, 5, 6}
Put 3 at the end of list.
A = {1, 2, 4, 5, 6, 3}
3 < 6, swap 3 and 6
A = {1, 2, 4, 5, 3, 6}
3 < 5 swap 3 and 5
A = {1, 2, 4, 3, 5, 6}
3 < 4 swap 3 and 4
A = {1, 2, 3, 4, 5, 6}
3 > 2 so stop
By repeatedly swapping 3 travels to its proper position in the list
Por lo tanto, el algoritmo anterior se puede modificar como
function insertionSort(V)
for i in 1...length(V)
j = i
while ( j > 0 and V[j] < V[j-1])
Swap V[j] and V[j-1]
j -= 1
return V
El código CPP para este algoritmo se proporciona a continuación.
C++
// Iterative CPP program to sort
// an array by swapping elements
#include <iostream>
#include <vector>
using namespace std;
using Vector = vector<int>;
// Utility function to print a Vector
void printVector(const Vector& V)
{
for (auto e : V) {
cout << e << " ";
}
cout << endl;
}
// Function performs insertion sort on
// vector V
void insertionSort(Vector& V)
{
int N = V.size();
int i, j, key;
for (i = 1; i < N; i++) {
j = i;
// Insert V[i] into list 0..i-1
while (j > 0 and V[j] < V[j - 1]) {
// Swap V[j] and V[j-1]
swap(V[j], V[j - 1]);
// Decrement j by 1
j -= 1;
}
}
}
// Driver Code
int main()
{
Vector A = { 9, 8, 7, 5, 2, 1, 2, 3 };
cout << "Array: " << endl;
printVector(A);
cout << "After Sorting :" << endl;
insertionSort(A);
printVector(A);
return 0;
}
Java
// Iterative Java program to sort
// an array by swapping elements
import java.io.*;
import java.util.*;
class GFG
{
// Utility function to print a Vector
static void printVector( Vector<Integer> V)
{
for (int i = 0; i < V.size(); i++) {
System.out.print(V.get(i)+" ");
}
System.out.println();
}
// Function performs insertion sort on
// vector V
static void insertionSort(Vector<Integer> V)
{
int N = V.size();
int i, j, key;
for (i = 1; i < N; i++) {
j = i;
// Insert V[i] into list 0..i-1
while (j > 0 && V.get(j) < V.get(j - 1)) {
// Swap V[j] and V[j-1]
int temp= V.get(j);
V.set(j, V.get(j - 1));
V.set(j - 1, temp);
// Decrement j by 1
j -= 1;
}
}
}
public static void main (String[] args)
{
Vector<Integer> A = new Vector<Integer> ();
A.add(0, 9);
A.add(1, 8);
A.add(2, 7);
A.add(3, 5);
A.add(4, 2);
A.add(5, 1);
A.add(6, 2);
A.add(7, 3);
System.out.print("Array: ");
printVector(A);
System.out.print("After Sorting :");
insertionSort(A);
printVector(A);
}
}
//This code is contributed by Gitanjali.
Python3
# Iterative python program to sort
# an array by swapping elements
import math
# Utility function to print a Vector
def printVector( V):
for i in V:
print(i ,end= " ")
print (" ")
def insertionSort( V):
N = len(V)
for i in range(1,N):
j = i
# Insert V[i] into list 0..i-1
while (j > 0 and V[j] < V[j - 1]) :
# Swap V[j] and V[j-1]
temp = V[j];
V[j] = V[j - 1];
V[j-1] = temp;
# Decrement j
j -= 1
# Driver method
A = [ 9, 8, 7, 5, 2, 1, 2, 3 ]
n = len(A)
print("Array")
printVector(A)
print( "After Sorting :")
insertionSort(A)
printVector(A)
# This code is contributed by Gitanjali.
C#
// Iterative C# program to sort
// an array by swapping elements
using System;
using System.Collections.Generic;
class GFG
{
// Utility function to print a Vector
static void printVector(List<int> V)
{
for (int i = 0; i < V.Count; i++)
{
Console.Write(V[i] + " ");
}
Console.WriteLine();
}
// Function performs insertion sort on
// vector V
static void insertionSort(List<int> V)
{
int N = V.Count;
int i, j;
for (i = 1; i < N; i++)
{
j = i;
// Insert V[i] into list 0..i-1
while (j > 0 && V[j] < V[j - 1])
{
// Swap V[j] and V[j-1]
int temp= V[j];
V[j] = V[j - 1];
V[j - 1] = temp;
// Decrement j by 1
j -= 1;
}
}
}
// Driver Code
public static void Main (String[] args)
{
List<int> A = new List<int> ();
A.Insert(0, 9);
A.Insert(1, 8);
A.Insert(2, 7);
A.Insert(3, 5);
A.Insert(4, 2);
A.Insert(5, 1);
A.Insert(6, 2);
A.Insert(7, 3);
Console.Write("Array: \n");
printVector(A);
Console.Write("After Sorting :\n");
insertionSort(A);
printVector(A);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Iterative Javascript program to sort
// an array by swapping elements
// Utility function to print a Vector
function printVector(V) {
for (let e of V) {
document.write(e + " ");
}
document.write("<br>");
}
// Function performs insertion sort on
// vector V
function insertionSort(V) {
let N = V.length;
let i, j, key;
for (i = 1; i < N; i++) {
j = i;
// Insert V[i] into list 0..i-1
while (j > 0 && V[j] < V[j - 1]) {
// Swap V[j] and V[j-1]
let temp = V[j];
V[j] = V[j - 1];
V[j - 1] = temp;
// Decrement j by 1
j -= 1;
}
}
}
// Driver Code
let A = [9, 8, 7, 5, 2, 1, 2, 3];
document.write("Array: " + "<br>");
printVector(A);
document.write("After Sorting :" + "<br>");
insertionSort(A);
printVector(A);
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
Array: 9 8 7 5 2 1 2 3 After Sorting : 1 2 2 3 5 7 8 9
Clasificación por inserción recursiva
Considere una array A de tamaño N
- Primero ordene recursivamente la sublista de A que es de tamaño N-1
- Inserte el último elemento de A en la sublista ordenada.
Para realizar el paso de inserción, use el intercambio repetido como se explicó anteriormente.
Algoritmo
function insertionSortRecursive(A, N)
if N >= 1
insertionSortRecursive(A, N-1)
j = N-1
while j > 0 and A[j] < A[j-1]
Swap A[j] and A[j-1]
j = j-1
[end of while]
[end of if]
La siguiente es la implementación del enfoque anterior:
C++
// Recursive CPP program to sort an array
// by swapping elements
#include <iostream>
#include <vector>
using namespace std;
using Vector = vector<int>;
// Utility function to print a Vector
void printVector(const Vector& V)
{
for (auto e : V) {
cout << e << " ";
}
cout << endl;
}
// Function to perform Insertion Sort recursively
void insertionSortRecursive(Vector& V, int N)
{
if (N <= 1)
return;
// General Case
// Sort V till second last element and
// then insert last element into V
insertionSortRecursive(V, N - 1);
// Insertion step
int j = N - 1;
while (j > 0 and V[j] < V[j - 1]) {
// Swap V[j] and V[j-1]
swap(V[j], V[j - 1]);
// Decrement j
j -= 1;
}
}
// Driver Code
int main()
{
// Declare a vector of size 10
Vector A = { 9, 8, 7, 5, 2, 1, 2, 3 };
cout << "Array: " << endl;
printVector(A);
cout << "After Sorting :" << endl;
insertionSortRecursive(A, A.size());
printVector(A);
return 0;
}
Java
// Recursive Java program to sort
// an array by swapping elements
import java.io.*;
import java.util.*;
class GFG
{
// Utility function to print a Vector
static void printVector( Vector<Integer> V)
{
for (int i = 0; i < V.size(); i++) {
System.out.print(V.get(i) + " ");
}
System.out.println();
}
// Function performs insertion sort on
// vector V
static void insertionSortRecursive(Vector<Integer> V,int N)
{
if (N <= 1)
return;
// General Case
// Sort V till second last element and
// then insert last element into V
insertionSortRecursive(V, N - 1);
// Insertion step
int j = N - 1;
// Insert V[i] into list 0..i-1
while (j > 0 && V.get(j) < V.get(j - 1))
{
// Swap V[j] and V[j-1]
int temp= V.get(j);
V.set(j, V.get(j - 1));
V.set(j - 1, temp);
// Decrement j by 1
j -= 1;
}
}
// Driver code
public static void main (String[] args)
{
Vector<Integer> A = new Vector<Integer> ();
A.add(0, 9);
A.add(1, 8);
A.add(2, 7);
A.add(3, 5);
A.add(4, 2);
A.add(5, 1);
A.add(6, 2);
A.add(7, 3);
System.out.print("Array: ");
printVector(A);
System.out.print("After Sorting :");
insertionSortRecursive(A,A.size());
printVector(A);
}
}
// This code is contributed by Gitanjali.
Python3
# Recursive python program
# to sort an array
# by swapping elements
import math
# Utility function to print
# a Vector
def printVector( V):
for i in V:
print(i, end = " ")
print (" ")
# Function to perform Insertion
# Sort recursively
def insertionSortRecursive(V, N):
if (N <= 1):
return 0
# General Case
# Sort V till second
# last element and
# then insert last element
# into V
insertionSortRecursive(V, N - 1)
# Insertion step
j = N - 1
while (j > 0 and V[j] < V[j - 1]) :
# Swap V[j] and V[j-1]
temp = V[j];
V[j] = V[j - 1];
V[j-1] = temp;
# Decrement j
j -= 1
# Driver method
A = [ 9, 8, 7, 5, 2, 1, 2, 3 ]
n=len(A)
print("Array")
printVector(A)
print( "After Sorting :")
insertionSortRecursive(A,n)
printVector(A)
# This code is contributed
# by Gitanjali.
C#
// Recursive C# program to sort
// an array by swapping elements
using System;
using System.Collections.Generic;
class GFG
{
// Utility function to print a Vector
static void printVector(List<int> V)
{
for (int i = 0; i < V.Count; i++)
{
Console.Write(V[i] + " ");
}
Console.WriteLine();
}
// Function performs insertion sort on
// vector V
static void insertionSortRecursive(List<int> V,
int N)
{
if (N <= 1)
return;
// General Case
// Sort V till second last element and
// then insert last element into V
insertionSortRecursive(V, N - 1);
// Insertion step
int j = N - 1;
// Insert V[i] into list 0..i-1
while (j > 0 && V[j] < V[j - 1])
{
// Swap V[j] and V[j-1]
int temp = V[j];
V[j] = V[j - 1];
V[j - 1] = temp;
// Decrement j by 1
j -= 1;
}
}
// Driver code
public static void Main (String[] args)
{
List<int> A = new List<int> ();
A.Insert(0, 9);
A.Insert(1, 8);
A.Insert(2, 7);
A.Insert(3, 5);
A.Insert(4, 2);
A.Insert(5, 1);
A.Insert(6, 2);
A.Insert(7, 3);
Console.Write("Array: ");
printVector(A);
Console.Write("After Sorting :");
insertionSortRecursive(A, A.Count);
printVector(A);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Recursive Javascript program to sort an array
// by swapping elements
// Utility function to print a Vector
function printVector(V) {
for (let e of V) {
document.write(e + " ");
}
document.write("<br>");
}
// Function to perform Insertion Sort recursively
function insertionSortRecursive(V, N) {
if (N <= 1)
return;
// General Case
// Sort V till second last element and
// then insert last element into V
insertionSortRecursive(V, N - 1);
// Insertion step
let j = N - 1;
while (j > 0 && V[j] < V[j - 1]) {
// Swap V[j] and V[j-1]
let temp = V[j];
V[j] = V[j - 1];
V[j - 1] = temp;
// Decrement j
j -= 1;
}
}
// Driver Code
// Declare a vector of size 10
let A = [9, 8, 7, 5, 2, 1, 2, 3];
document.write("Array: <br>");
printVector(A);
document.write("After Sorting :<br>");
insertionSortRecursive(A, A.length);
printVector(A);
// This code is contributed by gfgking.
</script>
Producción:
Array: 9 8 7 5 2 1 2 3 After Sorting : 1 2 2 3 5 7 8 9
Nota
La Complejidad de tiempo del algoritmo sigue siendo O(N^2) en el peor de los casos. Además, estas versiones son potencialmente más lentas ya que el intercambio repetido requiere más operaciones. Sin embargo, estas versiones se discuten debido a su simplicidad de implementación y facilidad de comprensión. Desbordamiento de la pila de
referencias : clasificación de inserción por intercambio
Publicación traducida automáticamente
Artículo escrito por Sayan Mahapatra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA