Combine dos arrays ordenadas en O (1) espacio adicional usando la partición QuickSort

Dadas dos arrays ordenadas , arr[] , brr[] de tamaño N y M , la tarea es fusionar las dos arrays dadas de modo que formen una secuencia ordenada de enteros que combinen elementos de ambas arrays.

Ejemplos:

Entrada: arr[] = {10}, brr[] = {2, 3}
Salida : 2 3 10
Explicación: La array ordenada combinada obtenida al tomar todos los elementos de ambas arrays es {2, 3, 10}. 
Por lo tanto, la salida requerida es 2 3 10.

Entrada: arr[]= {1, 5, 9, 10, 15, 20}, brr[] = {2, 3, 8, 13}
Salida: 1 2 3 5 8 9 10 13 15 20

Enfoque ingenuo: Consulte Fusionar dos arrays ordenadas para obtener el enfoque más simple para fusionar las dos arrays dadas.
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(1)

Enfoque optimizado para el espacio: Consulte Fusionar dos arrays ordenadas con O(1) espacio adicional para fusionar las dos arrays dadas sin usar memoria adicional.
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(1)

Enfoque de optimización de espacio eficiente: consulte Fusionar de manera eficiente dos arrays ordenadas con O(1) espacio adicional para fusionar las dos arrays dadas sin usar memoria adicional.
Complejidad de tiempo: O((N + M) * log(N + M))
Espacio auxiliar: O(1)

Enfoque basado en partición : la idea es considerar el elemento (N + 1) de la array ordenada final como un elemento pivote y realizar la ^partición de clasificación rápida alrededor del elemento pivote. Finalmente, almacene los primeros N elementos más pequeños de la array ordenada final en la array, arr[] y los últimos M elementos más grandes de la array ordenada final en la array, brr[] en cualquier orden y clasifique ambas arrays por separado. Siga los pasos a continuación para resolver el problema:

1. Inicialice una variable, digamos índice para almacenar el índice de cada elemento de la array ordenada final.
2. Encuentre el (N + 1) ^elemento de la array ordenada final como un elemento pivote.
3. Realice la partición de clasificación rápida alrededor del elemento pivote.
4. Finalmente, ordene la array arr[] y brr[] por separado.

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;
 
// Function to perform the partition
// around the pivot element
void partition(int arr[], int N,
               int brr[], int M,
               int Pivot)
{
    // Stores index of each element
    // of the array, arr[]
    int l = N - 1;
 
    // Stores index of each element
    // of the array, brr[]
    int r = 0;
 
    // Traverse both the array
    while (l >= 0 && r < M) {
 
        // If pivot is
        // smaller than arr[l]
        if (arr[l] < Pivot)
            l--;
 
        // If Pivot is
        // greater than brr[r]
        else if (brr[r] > Pivot)
            r++;
 
        // If either arr[l] > Pivot
        // or brr[r] < Pivot
        else {
            swap(arr[l], brr[r]);
            l--;
            r++;
        }
    }
}
 
// Function to merge
// the two sorted array
void Merge(int arr[], int N,
           int brr[], int M)
{
    // Stores index of each element
    // of the array arr[]
    int l = 0;
 
    // Stores index of each element
    // of the array brr[]
    int r = 0;
 
    // Stores index of each element
    // the final sorted array
    int index = -1;
 
    // Stores the pivot element
    int Pivot = 0;
 
    // Traverse both the array
    while (index < N && l < N && r < M) {
 
        if (arr[l] < brr[r]) {
            Pivot = arr[l++];
        }
        else {
            Pivot = brr[r++];
        }
        index++;
    }
 
    // If pivot element is not found
    // or index < N
    while (index < N && l < N) {
        Pivot = arr[l++];
        index++;
    }
 
    // If pivot element is not found
    // or index < N
    while (index < N && r < M) {
        Pivot = brr[r++];
        index++;
    }
 
    // Place the first N elements of
    // the sorted array into arr[]
    // and the last M elements of
    // the sorted array into brr[]
    partition(arr, N, brr,
              M, Pivot);
 
    // Sort both the arrays
    sort(arr, arr + N);
 
    sort(brr, brr + M);
 
    // Print the first N elements
    // in sorted order
    for (int i = 0; i < N; i++)
        cout << arr[i] << " ";
 
    // Print the last M elements
    // in sorted order
    for (int i = 0; i < M; i++)
        cout << brr[i] << " ";
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 5, 9 };
    int brr[] = { 2, 4, 7, 10 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int M = sizeof(brr) / sizeof(brr[0]);
    Merge(arr, N, brr, M);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
class GFG{
 
// Function to perform the partition
// around the pivot element
static void partition(int arr[], int N,
                      int brr[], int M,
                      int Pivot)
{
  // Stores index of each element
  // of the array, arr[]
  int l = N - 1;
 
  // Stores index of each element
  // of the array, brr[]
  int r = 0;
 
  // Traverse both the array
  while (l >= 0 && r < M)
  {
    // If pivot is
    // smaller than arr[l]
    if (arr[l] < Pivot)
      l--;
 
    // If Pivot is
    // greater than brr[r]
    else if (brr[r] > Pivot)
      r++;
 
    // If either arr[l] > Pivot
    // or brr[r] < Pivot
    else
    {
      int t = arr[l];
      arr[l] = brr[r];
      brr[r] = t;
      l--;
      r++;
    }
  }
}
 
// Function to merge
// the two sorted array
static void Merge(int arr[], int N,
                  int brr[], int M)
{
  // Stores index of each element
  // of the array arr[]
  int l = 0;
 
  // Stores index of each element
  // of the array brr[]
  int r = 0;
 
  // Stores index of each element
  // the final sorted array
  int index = -1;
 
  // Stores the pivot element
  int Pivot = 0;
 
  // Traverse both the array
  while (index < N && l < N &&
         r < M)
  {
    if (arr[l] < brr[r])
    {
      Pivot = arr[l++];
    }
    else
    {
      Pivot = brr[r++];
    }
    index++;
  }
 
  // If pivot element is not found
  // or index < N
  while (index < N && l < N)
  {
    Pivot = arr[l++];
    index++;
  }
 
  // If pivot element is not
  // found or index < N
  while (index < N && r < M)
  {
    Pivot = brr[r++];
    index++;
  }
 
  // Place the first N elements of
  // the sorted array into arr[]
  // and the last M elements of
  // the sorted array into brr[]
  partition(arr, N, brr,
            M, Pivot);
 
  // Sort both the arrays
  Arrays.sort(arr);
 
  Arrays.sort(brr);
 
  // Print the first N elements
  // in sorted order
  for (int i = 0; i < N; i++)
    System.out.print(arr[i] + " ");
 
  // Print the last M elements
  // in sorted order
  for (int i = 0; i < M; i++)
    System.out.print(brr[i] + " ");
}
 
// Driver Code
public static void main(String[] args)
{
  int arr[] = {1, 5, 9};
  int brr[] = {2, 4, 7, 10};
  int N = arr.length;
  int M = brr.length;
  Merge(arr, N, brr, M);
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to implement
# the above approach
 
# Function to perform the partition
# around the pivot element
def partition(arr, N, brr, M, Pivot):
     
    # Stores index of each element
    # of the array, arr[]
    l = N - 1
     
    # Stores index of each element
    # of the array, brr[]
    r = 0
     
    # Traverse both the array
    while (l >= 0 and r < M):
         
        # If pivot is smaller
        # than arr[l]
        if (arr[l] < Pivot):
            l -= 1
 
        # If Pivot is greater
        # than brr[r]
        elif (brr[r] > Pivot):
            r += 1
 
        # If either arr[l] > Pivot
        # or brr[r] < Pivot
        else:
            arr[l], brr[r] = brr[r], arr[l]
            l -= 1
            r += 1
 
# Function to merge
# the two sorted array
def Merge(arr, N, brr, M):
     
    # Stores index of each element
    # of the array arr[]
    l = 0
 
    # Stores index of each element
    # of the array brr[]
    r = 0
 
    # Stores index of each element
    # the final sorted array
    index = -1
 
    # Stores the pivot element
    Pivot = 0
 
    # Traverse both the array
    while (index < N and l < N and r < M):
        if (arr[l] < brr[r]):
            Pivot = arr[l]
            l += 1
        else:
            Pivot = brr[r]
            r += 1
 
        index += 1
 
    # If pivot element is not found
    # or index < N
    while (index < N and l < N):
        Pivot = arr[l]
        l += 1
        index += 1
 
    # If pivot element is not found
    # or index < N
    while (index < N and r < M):
        Pivot = brr[r]
        r += 1
        index += 1
 
    # Place the first N elements of
    # the sorted array into arr[]
    # and the last M elements of
    # the sorted array into brr[]
    partition(arr, N, brr, M, Pivot)
 
    # Sort both the arrays
    arr = sorted(arr)
 
    brr = sorted(brr)
 
    # Print the first N elements
    # in sorted order
    for i in range(N):
        print(arr[i], end = " ")
 
    # Print the last M elements
    # in sorted order
    for i in range(M):
        print(brr[i], end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 1, 5, 9 ]
    brr = [ 2, 4, 7, 10 ]
    N = len(arr)
    M = len(brr)
     
    Merge(arr, N, brr, M)
 
# This code is contributed by mohit kumar 29

// C# program to implement
// the above approach
using System;
class GFG{
 
// Function to perform the
// partition around the pivot
// element
static void partition(int []arr, int N,
                      int []brr, int M,
                      int Pivot)
{
  // Stores index of each element
  // of the array, []arr
  int l = N - 1;
 
  // Stores index of each element
  // of the array, brr[]
  int r = 0;
 
  // Traverse both the array
  while (l >= 0 && r < M)
  {
    // If pivot is
    // smaller than arr[l]
    if (arr[l] < Pivot)
      l--;
 
    // If Pivot is
    // greater than brr[r]
    else if (brr[r] > Pivot)
      r++;
 
    // If either arr[l] > Pivot
    // or brr[r] < Pivot
    else
    {
      int t = arr[l];
      arr[l] = brr[r];
      brr[r] = t;
      l--;
      r++;
    }
  }
}
 
// Function to merge
// the two sorted array
static void Merge(int []arr, int N,
                  int []brr, int M)
{
  // Stores index of each element
  // of the array []arr
  int l = 0;
 
  // Stores index of each element
  // of the array brr[]
  int r = 0;
 
  // Stores index of each element
  // the readonly sorted array
  int index = -1;
 
  // Stores the pivot element
  int Pivot = 0;
 
  // Traverse both the array
  while (index < N && l < N &&
         r < M)
  {
    if (arr[l] < brr[r])
    {
      Pivot = arr[l++];
    }
    else
    {
      Pivot = brr[r++];
    }
    index++;
  }
 
  // If pivot element is not found
  // or index < N
  while (index < N && l < N)
  {
    Pivot = arr[l++];
    index++;
  }
 
  // If pivot element is not
  // found or index < N
  while (index < N && r < M)
  {
    Pivot = brr[r++];
    index++;
  }
 
  // Place the first N elements of
  // the sorted array into []arr
  // and the last M elements of
  // the sorted array into brr[]
  partition(arr, N, brr,
            M, Pivot);
 
  // Sort both the arrays
    Array.Sort(arr);
    Array.Sort(brr);
 
 
  // Print the first N elements
  // in sorted order
  for (int i = 0; i < N; i++)
    Console.Write(arr[i] + " ");
 
  // Print the last M elements
  // in sorted order
  for (int i = 0; i < M; i++)
    Console.Write(brr[i] + " ");
}
 
// Driver Code
public static void Main(String[] args)
{
  int []arr = {1, 5, 9};
  int []brr= {2, 4, 7, 10};
  int N = arr.Length;
  int M = brr.Length;
  Merge(arr, N, brr, M);
}
}
 
// This code is contributed by shikhasingrajput

1 2 4 5 7 9 10 

Complejidad de tiempo: O((N + M)log(N + M))
Espacio auxiliar: O(1)

Enfoque eficiente: Consulte fusionar dos arrays ordenadas para fusionar de manera eficiente las dos arrays dadas.
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N + M)