Cuente los intercambios necesarios para ordenar una array mediante la ordenación por inserción

Dada una array A[] de tamaño N ( 1 ≤ N ≤ 10 ⁵ ), la tarea es calcular la cantidad de intercambios necesarios para clasificar la array mediante el algoritmo de clasificación por inserción .

Ejemplos:

Entrada: A[] = {2, 1, 3, 1, 2} 
Salida: 4 
Explicación:

Paso 1: arr[0] permanece en su posición inicial. 
Paso 2: arr[1] se desplaza 1 lugar a la izquierda. Count = 1. 
Paso 3: arr[2] permanece en su posición inicial. 
Paso 4: arr[3] se desplaza 2 lugares a la izquierda. Count = 2. 
Paso 5: arr[5] se desplaza 1 lugar a su derecha. Cuenta = 1.

Entrada: A[]={12, 15, 1, 5, 6, 14, 11} 
Salida: 10 

Enfoque: el problema se puede resolver utilizando el algoritmo Divide and Conquer ( Merge Sort ). Siga los pasos a continuación para resolver el problema:

• Divida la array en dos mitades y recorra recursivamente ambas mitades.
• Ordene cada mitad y calcule el número de intercambios necesarios.
• Finalmente, imprima el número total de intercambios requeridos.

A continuación se muestra la implementación del enfoque anterior:

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Stores the sorted
// array elements
int temp[100000];
 
// Function to count the number of
// swaps required to merge two sorted
// subarray in a sorted form
long int merge(int A[], int left,
               int mid, int right)
{
 
    // Stores the count of swaps
    long int swaps = 0;
 
    int i = left, j = mid, k = left;
 
    while (i < mid && j <= right) {
 
        if (A[i] <= A[j]) {
            temp[k] = A[i];
            k++, i++;
        }
        else {
            temp[k] = A[j];
            k++, j++;
            swaps += mid - i;
        }
    }
    while (i < mid) {
        temp[k] = A[i];
        k++, i++;
    }
 
    while (j <= right) {
        temp[k] = A[j];
        k++, j++;
    }
 
    while (left <= right) {
        A[left] = temp[left];
        left++;
    }
 
    return swaps;
}
 
// Function to count the total number
// of swaps required to sort the array
long int mergeInsertionSwap(int A[],
                            int left, int right)
{
    // Stores the total count
    // of swaps required
    long int swaps = 0;
    if (left < right) {
 
        // Find the middle index
        // splitting the two halves
        int mid = left + (right - left) / 2;
 
        // Count the number of swaps
        // required to sort the left subarray
        swaps += mergeInsertionSwap(A, left, mid);
 
        // Count the number of swaps
        // required to sort the right subarray
        swaps += mergeInsertionSwap(A, mid + 1, right);
 
        // Count the number of swaps required
        // to sort the two sorted subarrays
        swaps += merge(A, left, mid + 1, right);
    }
    return swaps;
}
 
// Driver Code
int main()
{
    int A[] = { 2, 1, 3, 1, 2 };
    int N = sizeof(A) / sizeof(A[0]);
    cout << mergeInsertionSwap(A, 0, N - 1);
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
  // Stores the sorted
  // array elements
  static int temp[] = new int[100000];
 
  // Function to count the number of
  // swaps required to merge two sorted
  // subarray in a sorted form
  static int merge(int A[], int left,
                   int mid, int right)
  {
 
    // Stores the count of swaps
    int swaps = 0;
    int i = left, j = mid, k = left;
    while (i < mid && j <= right)
    {
      if (A[i] <= A[j])
      {
        temp[k] = A[i];
        k++; i++;
      }
      else
      {
        temp[k] = A[j];
        k++; j++;
        swaps += mid - i;
      }
    }
    while (i < mid)
    {
      temp[k] = A[i];
      k++; i++;
    }
 
    while (j <= right)
    {
      temp[k] = A[j];
      k++; j++;
    }
 
    while (left <= right)
    {
      A[left] = temp[left];
      left++;
    }
    return swaps;
  }
 
  // Function to count the total number
  // of swaps required to sort the array
  static int mergeInsertionSwap(int A[],
                                int left, int right)
  {
    // Stores the total count
    // of swaps required
    int swaps = 0;
    if (left < right)
    {
 
      // Find the middle index
      // splitting the two halves
      int mid = left + (right - left) / 2;
 
      // Count the number of swaps
      // required to sort the left subarray
      swaps += mergeInsertionSwap(A, left, mid);
 
      // Count the number of swaps
      // required to sort the right subarray
      swaps += mergeInsertionSwap(A, mid + 1, right);
 
      // Count the number of swaps required
      // to sort the two sorted subarrays
      swaps += merge(A, left, mid + 1, right);
    }
    return swaps;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int A[] = { 2, 1, 3, 1, 2 };
    int N = A.length;
    System.out.println(mergeInsertionSwap(A, 0, N - 1));
  }
}
 
// This code is contributed by susmitakundugoaldanga.

# Python3 program to implement
# the above approach
 
# Stores the sorted
# array elements
temp = [0] * 100000
 
# Function to count the number of
# swaps required to merge two sorted
# subarray in a sorted form
def merge(A, left, mid, right):
     
    # Stores the count of swaps
    swaps = 0
 
    i, j, k = left, mid, left
     
    while (i < mid and j <= right):
         
        if (A[i] <= A[j]):
            temp[k] = A[i]
            k, i = k + 1, i + 1
        else:
            temp[k] = A[j]
            k, j = k + 1, j + 1
            swaps += mid - i
 
    while (i < mid):
        temp[k] = A[i]
        k, i = k + 1, i + 1
 
    while (j <= right):
        temp[k] = A[j]
        k, j = k + 1, j + 1
 
    while (left <= right):
        A[left] = temp[left]
        left += 1
 
    return swaps
 
# Function to count the total number
# of swaps required to sort the array
def mergeInsertionSwap(A, left, right):
     
    # Stores the total count
    # of swaps required
    swaps = 0
     
    if (left < right):
 
        # Find the middle index
        # splitting the two halves
        mid = left + (right - left) // 2
 
        # Count the number of swaps
        # required to sort the left subarray
        swaps += mergeInsertionSwap(A, left, mid)
 
        # Count the number of swaps
        # required to sort the right subarray
        swaps += mergeInsertionSwap(A, mid + 1, right)
 
        # Count the number of swaps required
        # to sort the two sorted subarrays
        swaps += merge(A, left, mid + 1, right)
 
    return swaps
 
# Driver Code
if __name__ == '__main__':
     
    A = [ 2, 1, 3, 1, 2 ]
    N = len(A)
     
    print (mergeInsertionSwap(A, 0, N - 1))
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
class GFG
{
 
 // Stores the sorted
  // array elements
  static int[] temp = new int[100000];
 
  // Function to count the number of
  // swaps required to merge two sorted
  // subarray in a sorted form
  static int merge(int[] A, int left,
                   int mid, int right)
  {
 
    // Stores the count of swaps
    int swaps = 0;
    int i = left, j = mid, k = left;
    while (i < mid && j <= right)
    {
      if (A[i] <= A[j])
      {
        temp[k] = A[i];
        k++; i++;
      }
      else
      {
        temp[k] = A[j];
        k++; j++;
        swaps += mid - i;
      }
    }
    while (i < mid)
    {
      temp[k] = A[i];
      k++; i++;
    }
 
    while (j <= right)
    {
      temp[k] = A[j];
      k++; j++;
    }
 
    while (left <= right)
    {
      A[left] = temp[left];
      left++;
    }
    return swaps;
  }
 
  // Function to count the total number
  // of swaps required to sort the array
  static int mergeInsertionSwap(int[] A,
                                int left, int right)
  {
     
    // Stores the total count
    // of swaps required
    int swaps = 0;
    if (left < right)
    {
 
      // Find the middle index
      // splitting the two halves
      int mid = left + (right - left) / 2;
 
      // Count the number of swaps
      // required to sort the left subarray
      swaps += mergeInsertionSwap(A, left, mid);
 
      // Count the number of swaps
      // required to sort the right subarray
      swaps += mergeInsertionSwap(A, mid + 1, right);
 
      // Count the number of swaps required
      // to sort the two sorted subarrays
      swaps += merge(A, left, mid + 1, right);
    }
    return swaps;
  }
 
  // Driver Code
  static public void Main()
  {
    int[] A = { 2, 1, 3, 1, 2 };
    int N = A.Length;
    Console.WriteLine(mergeInsertionSwap(A, 0, N - 1));
  }
}
 
// This code is contributed by code_hunt.

<script>
// javascript program of the above approach
 
  // Stores the sorted
  // array elements
  let temp = new Array(100000).fill(0);
  
  // Function to count the number of
  // swaps required to merge two sorted
  // subarray in a sorted form
  function merge(A, left,
                    mid, right)
  {
  
    // Stores the count of swaps
    let swaps = 0;
    let i = left, j = mid, k = left;
    while (i < mid && j <= right)
    {
      if (A[i] <= A[j])
      {
        temp[k] = A[i];
        k++; i++;
      }
      else
      {
        temp[k] = A[j];
        k++; j++;
        swaps += mid - i;
      }
    }
    while (i < mid)
    {
      temp[k] = A[i];
      k++; i++;
    }
  
    while (j <= right)
    {
      temp[k] = A[j];
      k++; j++;
    }
  
    while (left <= right)
    {
      A[left] = temp[left];
      left++;
    }
    return swaps;
  }
  
  // Function to count the total number
  // of swaps required to sort the array
  function mergeInsertionSwap(A, left, right)
  {
    // Stores the total count
    // of swaps required
    let swaps = 0;
    if (left < right)
    {
  
      // Find the middle index
      // splitting the two halves
      let mid = left + (right - left) / 2;
  
      // Count the number of swaps
      // required to sort the left subarray
      swaps += mergeInsertionSwap(A, left, mid);
  
      // Count the number of swaps
      // required to sort the right subarray
      swaps += mergeInsertionSwap(A, mid + 1, right);
  
      // Count the number of swaps required
      // to sort the two sorted subarrays
      swaps += merge(A, left, mid + 1, right);
    }
    return swaps;
  }
 
    // Driver Code
     
        let A = [ 2, 1, 3, 1, 2 ];
    let N = A.length;
    document.write(mergeInsertionSwap(A, 0, N - 1));
 
// This code is contributed by target_2.
</script>

4

Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)