Diferencia entre el ordenamiento por inserción y el ordenamiento por selección

Posted on by Rudeus Greyrat

En este artículo, discutiremos la diferencia entre la ordenación por inserción y la ordenación por selección:

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.

Algoritmo: 
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 imagen para ilustrar la ordenación por inserción: 
 

insertion-sort

A continuación se muestra el programa para el mismo:

C++

// C++ program for the 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;
    }
}
 
// Function to print an array of size N
void printArray(int arr[], int n)
{
    int i;
 
    // Print the array
    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]);
 
    // Function Call
    insertionSort(arr, N);
    printArray(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG
{
       
// Function to sort an array using
// insertion sort
static 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;
    }
}
 
// Function to print an array of size N
static void printArray(int arr[], int n)
{
    int i;
 
    // Print the array
    for (i = 0; i < n; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
}
   
// Driver code
public static void main(String[] args)
{
    int arr[] = { 12, 11, 13, 5, 6 };
    int N = arr.length;
 
    // Function Call
    insertionSort(arr, N);
    printArray(arr, N);
}
}
 
// This code is contributed by code_hunt.

Python3

# Python 3 program for the insertion sort
 
# Function to sort an array using
# insertion sort
def insertionSort(arr, n):
    i = 0
    key = 0
    j = 0
    for i in range(1,n,1):
        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 and arr[j] > key):
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = key
 
# Function to print an array of size N
def printArray(arr, n):
    i = 0
 
    # Print the array
    for i in range(n):
        print(arr[i],end = " ")
    print("\n",end = "")
 
# Driver Code
if __name__ == '__main__':
    arr =  [12, 11, 13, 5, 6]
    N =  len(arr)
 
    # Function Call
    insertionSort(arr, N)
    printArray(arr, N)
     
    # This code is contributed by bgangwar59.

C#

// C# program for the above approach
using System;
class GFG
{
 
    // Function to sort an array using
    // insertion sort
    static 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;
        }
    }
 
    // Function to print an array of size N
    static void printArray(int[] arr, int n)
    {
        int i;
 
        // Print the array
        for (i = 0; i < n; i++)
        {
            Console.Write(arr[i] + " ");
        }
        Console.WriteLine();
    }
 
    // Driver code
    static public void Main()
    {
        int[] arr = new int[] { 12, 11, 13, 5, 6 };
        int N = arr.Length;
 
        // Function Call
        insertionSort(arr, N);
        printArray(arr, N);
    }
}
 
// This code is contributed by Dharanendra L V

Javascript

<script>
 
// JavaScript program for the above approach
 
// 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;
    }
}
 
// Function to print an array of size N
function printArray(arr,n)
{
    let i;
  
    // Print the array
    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;
 
// Function Call
insertionSort(arr, N);
printArray(arr, N);
 
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>
Producción: 

5 6 11 12 13

 

El algoritmo de ordenación por selección ordena una array encontrando repetidamente el elemento mínimo (considerando el orden ascendente) de la parte no ordenada y colocándolo al principio. El algoritmo mantiene dos subarreglos en un arreglo dado. 

  • El subarreglo ya está ordenado.
  • El subarreglo restante no está ordenado.

En cada iteración del ordenamiento por selección, el elemento mínimo (considerando el orden ascendente) del subarreglo no ordenado se selecciona y se mueve al subarreglo ordenado. 

A continuación se muestra un ejemplo para explicar los pasos anteriores: 

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64

A continuación se muestra el programa para el mismo:

C++

// C++ program for implementation of
// selection sort
#include <bits/stdc++.h>
using namespace std;
 
// Function to swap two number
void swap(int* xp, int* yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
 
// Function to implement the selection
// sort
void selectionSort(int arr[], int n)
{
    int i, j, min_idx;
 
    // One by one move boundary of
    // unsorted subarray
    for (i = 0; i < n - 1; i++) {
 
        // Find the minimum element
        // in unsorted array
        min_idx = i;
        for (j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
 
        // Swap the found minimum element
        // with the first element
        swap(&arr[min_idx], &arr[i]);
    }
}
 
// Function to print an array
void printArray(int arr[], int size)
{
    int i;
 
    for (i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}
 
// Driver Code
int main()
{
    int arr[] = { 64, 25, 12, 22, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    selectionSort(arr, n);
    cout << "Sorted array: \n";
 
    // Print the array
    printArray(arr, n);
    return 0;
}

Java

// Java program for implementation of
// selection sort
import java.util.*;
class GFG
{
 
// Function to implement the selection
// sort
static void selectionSort(int arr[], int n)
{
    int i, j, min_idx;
 
    // One by one move boundary of
    // unsorted subarray
    for (i = 0; i < n - 1; i++)
    {
 
        // Find the minimum element
        // in unsorted array
        min_idx = i;
        for (j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
 
        // Swap the found minimum element
        // with the first element
        int temp = arr[min_idx];
        arr[min_idx]= arr[i];
        arr[i] = temp;
    }
}
 
// Function to print an array
static void printArray(int arr[], int size)
{
    int i;
 
    for (i = 0; i < size; i++) {
        System.out.print(arr[i]+ " ");
    }
    System.out.println();
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 64, 25, 12, 22, 11 };
    int n = arr.length;
 
    // Function Call
    selectionSort(arr, n);
    System.out.print("Sorted array: \n");
 
    // Print the array
    printArray(arr, n);
}
}
 
// This code is contributed by aashish1995

Python3

# Python3 program for implementation of
# selection sort
 
# Function to implement the selection
# sort
def selectionSort(arr, n):
 
    # One by one move boundary of
    # unsorted subarray
    for i in range(n - 1):
 
        # Find the minimum element
        # in unsorted array
        min_idx = i
        for j in range(i + 1, n):
            if (arr[j] < arr[min_idx]):
                min_idx = j
 
        # Swap the found minimum element
        # with the first element
        arr[min_idx], arr[i] = arr[i], arr[min_idx]
 
# Function to print an array
def printArray(arr, size):
 
    for i in range(size):
        print(arr[i], end = " ")
 
    print()
 
# Driver Code
if __name__ == "__main__":
 
    arr = [64, 25, 12, 22, 11]
    n = len(arr)
 
    # Function Call
    selectionSort(arr, n)
    print("Sorted array: ")
 
    # Print the array
    printArray(arr, n)
 
# This code is contributed by ukasp

C#

// C# program for implementation of
// selection sort
using System;
public class GFG
{
 
// Function to implement the selection
// sort
static void selectionSort(int []arr, int n)
{
    int i, j, min_idx;
 
    // One by one move boundary of
    // unsorted subarray
    for (i = 0; i < n - 1; i++)
    {
 
        // Find the minimum element
        // in unsorted array
        min_idx = i;
        for (j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
 
        // Swap the found minimum element
        // with the first element
        int temp = arr[min_idx];
        arr[min_idx]= arr[i];
        arr[i] = temp;
    }
}
 
// Function to print an array
static void printArray(int []arr, int size)
{
    int i;
 
    for (i = 0; i < size; i++) {
        Console.Write(arr[i]+ " ");
    }
    Console.WriteLine();
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 64, 25, 12, 22, 11 };
    int n = arr.Length;
 
    // Function Call
    selectionSort(arr, n);
    Console.Write("Sorted array: \n");
 
    // Print the array
    printArray(arr, n);
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// Javascript program for implementation of
// selection sort
 
// Function to implement the selection
// sort
function selectionSort(arr, n)
{
    let i, j, min_idx;
     
    // One by one move boundary of
    // unsorted subarray
    for(i = 0; i < n - 1; i++)
    {
         
        // Find the minimum element
        // in unsorted array
        min_idx = i;
         
        for(j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
  
        // Swap the found minimum element
        // with the first element
        let temp = arr[min_idx];
        arr[min_idx]= arr[i];
        arr[i] = temp;
    }
}
 
// Function to print an array
function printArray(arr, size)
{
    let i;
  
    for(i = 0; i < size; i++)
    {
        document.write(arr[i] + " ");
    }
    document.write("<br>");
}
 
// Driver Code
let arr = [ 64, 25, 12, 22, 11 ];
let n = arr.length;
 
// Function Call
selectionSort(arr, n);
document.write("Sorted array: <br>");
 
// Print the array
printArray(arr, n);
 
// This code is contributed by rag2127
 
</script>
Producción: 

Sorted array: 
11 12 22 25 64

 

Diferencia tabular entre la ordenación por inserción y la ordenación por selección:

 

 Tipo de inserción Clasificación de selección
1. Inserta el valor en la array preordenada para ordenar el conjunto de valores en la array. Encuentra el número mínimo/máximo de la lista y lo ordena en orden ascendente/descendente.
2. Es un algoritmo de clasificación estable. Es un algoritmo de clasificación inestable.
3.  La complejidad de tiempo en el mejor de los casos es Ω(N) cuando la array ya está en orden ascendente. Tiene Θ(N 2 ) en el peor de los casos y en el caso promedio. Para el mejor de los casos, el peor de los casos y el tipo de selección promedio tienen una complejidad Θ(N 2 ).
4. El número de operaciones de comparación realizadas en este algoritmo de clasificación es menor que el intercambio realizado. El número de operaciones de comparación realizadas en este algoritmo de clasificación es mayor que el intercambio realizado.
5.  Es más eficiente que el tipo Selección. Es menos eficiente que la ordenación por inserción.
6.  Aquí se conoce el elemento de antemano, y buscamos la posición correcta para colocarlos. La ubicación donde colocar el elemento se conoce previamente, buscamos el elemento para insertar en esa posición.
7.

El ordenamiento por inserción se utiliza cuando:

  • La array tiene una pequeña cantidad de elementos.
  • Solo quedan algunos elementos por ordenar

El ordenamiento por selección se utiliza cuando

  • Hay que ordenar una pequeña lista.
  • El costo del cambio no importa
  • La comprobación de todos los elementos es obligatoria.
  • El costo de escribir en la memoria importa como en la memoria flash (el número de intercambios es O (n) en comparación con O (n2) de tipo burbuja)
8. La ordenación por inserción es adaptativa, es decir, eficiente para conjuntos de datos que ya están sustancialmente ordenados: la complejidad del tiempo es O(kn) cuando cada elemento en la entrada no está a más de k lugares de distancia de su posición ordenada La clasificación por selección es un algoritmo de clasificación de comparación en el lugar

Publicación traducida automáticamente

Artículo escrito por CoderSaty 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 *