Escriba una función SortedMerge() que tome dos listas, cada una de las cuales no está ordenada, y fusione las dos en una nueva lista que esté en orden ordenado (creciente). SortedMerge() debería devolver la nueva lista.
Ejemplos:
Input : a[] = {10, 5, 15}
b[] = {20, 3, 2}
Output : Merge List :
{2, 3, 5, 10, 15, 20}
Input : a[] = {1, 10, 5, 15}
b[] = {20, 0, 2}
Output : Merge List :
{0, 1, 2, 5, 10, 15, 20}
Hay muchos casos con los que lidiar: ‘a’ o ‘b’ pueden estar vacíos, durante el procesamiento, ‘a’ o ‘b’ pueden agotarse primero y, finalmente, está el problema de comenzar la lista de resultados vacía y construirla. hacia arriba mientras pasa por ‘a’ y ‘b’.
Método 1 (primero Concatenar y luego Ordenar): En este caso, primero agregamos las dos listas sin ordenar. Luego simplemente ordenamos la lista concatenada.
Implementación:
C++
// CPP program to merge two unsorted lists
// in sorted order
#include <bits/stdc++.h>
using namespace std;
// Function to merge array in sorted order
void sortedMerge(int a[], int b[], int res[],
int n, int m)
{
// Concatenate two arrays
int i = 0, j = 0, k = 0;
while (i < n) {
res[k] = a[i];
i += 1;
k += 1;
}
while (j < m) {
res[k] = b[j];
j += 1;
k += 1;
}
// sorting the res array
sort(res, res + n + m);
}
// Driver code
int main()
{
int a[] = { 10, 5, 15 };
int b[] = { 20, 3, 2, 12 };
int n = sizeof(a) / sizeof(a[0]);
int m = sizeof(b) / sizeof(b[0]);
// Final merge list
int res[n + m];
sortedMerge(a, b, res, n, m);
cout << "Sorted merged list :";
for (int i = 0; i < n + m; i++)
cout << " " << res[i];
cout << "n";
return 0;
}
Java
// Java Code for Merging two unsorted
// arrays in sorted order
import java.util.*;
class GFG {
// Function to merge array in sorted order
public static void sortedMerge(int a[], int b[],
int res[], int n,
int m)
{
// Concatenate two arrays
int i = 0, j = 0, k = 0;
while (i < n) {
res[k] = a[i];
i++;
k++;
}
while (j < m) {
res[k] = b[j];
j++;
k++;
}
// sorting the res array
Arrays.sort(res);
}
/* Driver program to test above function */
public static void main(String[] args)
{
int a[] = { 10, 5, 15 };
int b[] = { 20, 3, 2, 12 };
int n = a.length;
int m = b.length;
// Final merge list
int res[]=new int[n + m];
sortedMerge(a, b, res, n, m);
System.out.print("Sorted merged list :");
for (int i = 0; i < n + m; i++)
System.out.print(" " + res[i]);
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python program to merge two unsorted lists
# in sorted order
# Function to merge array in sorted order
def sortedMerge(a, b, res, n, m):
# Concatenate two arrays
i, j, k = 0, 0, 0
while (i < n):
res[k] = a[i]
i += 1
k += 1
while (j < m):
res[k] = b[j]
j += 1
k += 1
# sorting the res array
res.sort()
# Driver code
a = [ 10, 5, 15 ]
b = [ 20, 3, 2, 12 ]
n = len(a)
m = len(b)
# Final merge list
res = [0 for i in range(n + m)]
sortedMerge(a, b, res, n, m)
print ("Sorted merged list :")
for i in range(n + m):
print(res[i],end=" ")
# This code is contributed by Sachin Bisht
C#
// C# Code for Merging two
// unsorted arrays in sorted order
using System;
class GFG {
// Function to merge array in sorted order
public static void sortedMerge(int []a, int []b,
int []res, int n,
int m)
{
// Concatenate two arrays
int i = 0, j = 0, k = 0;
while (i < n) {
res[k] = a[i];
i++;
k++;
}
while (j < m) {
res[k] = b[j];
j++;
k++;
}
// sorting the res array
Array.Sort(res);
}
/* Driver program to test above function */
public static void Main()
{
int []a = {10, 5, 15};
int []b = {20, 3, 2, 12};
int n = a.Length;
int m = b.Length;
// Final merge list
int []res=new int[n + m];
sortedMerge(a, b, res, n, m);
Console.Write("Sorted merged list :");
for (int i = 0; i < n + m; i++)
Console.Write(" " + res[i]);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to merge two unsorted lists
// in sorted order
// Function to merge array in sorted order
function sortedMerge($a, $b, $n, $m)
{
// Concatenate two arrays
$res = array();
$i = 0; $j = 0; $k = 0;
while ($i < $n)
{
$res[$k] = $a[$i];
$i += 1;
$k += 1;
}
while ($j < $m)
{
$res[$k] = $b[$j];
$j += 1;
$k += 1;
}
// sorting the res array
sort($res);
echo "Sorted merged list :";
for ($i = 0; $i < count($res); $i++)
echo $res[$i] . " ";
}
// Driver code
$a = array( 10, 5, 15 );
$b = array( 20, 3, 2, 12 );
$n = count($a);
$m = count($b);
// Final merge list
sortedMerge($a, $b, $n, $m);
// This code is contributed by Rajput-Ji.
?>
Javascript
<script>
// Javascript program to merge two unsorted lists
// in sorted order
// Function to merge array in sorted order
function sortedMerge(a, b, res,
n, m)
{
// Sorting a[] and b[]
a.sort((a,b) => a-b);
b.sort((a,b) => a-b);
// Merge two sorted arrays into res[]
let i = 0, j = 0, k = 0;
while (i < n && j < m) {
if (a[i] <= b[j]) {
res[k] = a[i];
i += 1;
k += 1;
} else {
res[k] = b[j];
j += 1;
k += 1;
}
}
while (i < n) { // Merging remaining
// elements of a[] (if any)
res[k] = a[i];
i += 1;
k += 1;
}
while (j < m) { // Merging remaining
// elements of b[] (if any)
res[k] = b[j];
j += 1;
k += 1;
}
}
// Driver code
let a = [ 10, 5, 15 ];
let b = [ 20, 3, 2, 12 ];
let n = a.length;
let m = b.length;
// Final merge list
let res = new Array(n + m);
sortedMerge(a, b, res, n, m);
document.write("Sorted merge list :");
for (let i = 0; i < n + m; i++)
document.write(" " + res[i]);
//This code is contributed by Mayank Tyagi
</script>
Producción
Sorted merged list : 2 3 5 10 12 15 20n
Complejidad de Tiempo: O ( (n + m) (log(n + m)) )
Espacio Auxiliar: O ( (n + m) )
Método 2 (primero ordenar y luego fusionar): primero ordenamos ambas arrays por separado. Luego simplemente fusionamos dos arrays ordenadas.
Implementación:
C++
// CPP program to merge two unsorted lists
// in sorted order
#include <bits/stdc++.h>
using namespace std;
// Function to merge array in sorted order
void sortedMerge(int a[], int b[], int res[],
int n, int m)
{
// Sorting a[] and b[]
sort(a, a + n);
sort(b, b + m);
// Merge two sorted arrays into res[]
int i = 0, j = 0, k = 0;
while (i < n && j < m) {
if (a[i] <= b[j]) {
res[k] = a[i];
i += 1;
k += 1;
} else {
res[k] = b[j];
j += 1;
k += 1;
}
}
while (i < n) { // Merging remaining
// elements of a[] (if any)
res[k] = a[i];
i += 1;
k += 1;
}
while (j < m) { // Merging remaining
// elements of b[] (if any)
res[k] = b[j];
j += 1;
k += 1;
}
}
// Driver code
int main()
{
int a[] = { 10, 5, 15 };
int b[] = { 20, 3, 2, 12 };
int n = sizeof(a) / sizeof(a[0]);
int m = sizeof(b) / sizeof(b[0]);
// Final merge list
int res[n + m];
sortedMerge(a, b, res, n, m);
cout << "Sorted merge list :";
for (int i = 0; i < n + m; i++)
cout << " " << res[i];
cout << "n";
return 0;
}
Java
// JAVA Code for Merging two unsorted
// arrays in sorted order
import java.util.*;
class GFG {
// Function to merge array in sorted order
public static void sortedMerge(int a[], int b[],
int res[], int n,
int m)
{
// Sorting a[] and b[]
Arrays.sort(a);
Arrays.sort(b);
// Merge two sorted arrays into res[]
int i = 0, j = 0, k = 0;
while (i < n && j < m) {
if (a[i] <= b[j]) {
res[k] = a[i];
i += 1;
k += 1;
} else {
res[k] = b[j];
j += 1;
k += 1;
}
}
while (i < n) { // Merging remaining
// elements of a[] (if any)
res[k] = a[i];
i += 1;
k += 1;
}
while (j < m) { // Merging remaining
// elements of b[] (if any)
res[k] = b[j];
j += 1;
k += 1;
}
}
/* Driver program to test above function */
public static void main(String[] args)
{
int a[] = { 10, 5, 15 };
int b[] = { 20, 3, 2, 12 };
int n = a.length;
int m = b.length;
// Final merge list
int res[] = new int[n + m];
sortedMerge(a, b, res, n, m);
System.out.print( "Sorted merged list :");
for (int i = 0; i < n + m; i++)
System.out.print(" " + res[i]);
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python program to merge two unsorted lists
# in sorted order
# Function to merge array in sorted order
def sortedMerge(a, b, res, n, m):
# Sorting a[] and b[]
a.sort()
b.sort()
# Merge two sorted arrays into res[]
i, j, k = 0, 0, 0
while (i < n and j < m):
if (a[i] <= b[j]):
res[k] = a[i]
i += 1
k += 1
else:
res[k] = b[j]
j += 1
k += 1
while (i < n): # Merging remaining
# elements of a[] (if any)
res[k] = a[i]
i += 1
k += 1
while (j < m): # Merging remaining
# elements of b[] (if any)
res[k] = b[j]
j += 1
k += 1
# Driver code
a = [ 10, 5, 15 ]
b = [ 20, 3, 2, 12 ]
n = len(a)
m = len(b)
# Final merge list
res = [0 for i in range(n + m)]
sortedMerge(a, b, res, n, m)
print ("Sorted merged list :")
for i in range(n + m):
print(res[i],end=" ")
# This code is contributed by Sachin Bisht
C#
// C# Code for Merging two unsorted
// arrays in sorted order
using System;
class GFG {
// Function to merge array in
// sorted order
static void sortedMerge(int []a, int []b,
int []res, int n, int m)
{
// Sorting a[] and b[]
Array.Sort(a);
Array.Sort(b);
// Merge two sorted arrays into res[]
int i = 0, j = 0, k = 0;
while (i < n && j < m)
{
if (a[i] <= b[j])
{
res[k] = a[i];
i += 1;
k += 1;
}
else
{
res[k] = b[j];
j += 1;
k += 1;
}
}
while (i < n)
{
// Merging remaining
// elements of a[] (if any)
res[k] = a[i];
i += 1;
k += 1;
}
while (j < m)
{
// Merging remaining
// elements of b[] (if any)
res[k] = b[j];
j += 1;
k += 1;
}
}
/* Driver program to test
above function */
public static void Main()
{
int []a = { 10, 5, 15 };
int []b = { 20, 3, 2, 12 };
int n = a.Length;
int m = b.Length;
// Final merge list
int []res = new int[n + m];
sortedMerge(a, b, res, n, m);
Console.Write( "Sorted merged list :");
for (int i = 0; i < n + m; i++)
Console.Write(" " + res[i]);
}
}
// This code is contributed by nitin mittal.
Javascript
<script>
// JavaScript program to merge two unsorted
// lists in sorted order
// Function to merge array in sorted order
function sortedMerge(a, b, res, n, m)
{
// Sorting a[] and b[]
a.sort((a, b) => a - b);
b.sort((a, b) => a - b);
// Merge two sorted arrays into res[]
let i = 0, j = 0, k = 0;
while (i < n && j < m)
{
if (a[i] <= b[j])
{
res[k] = a[i];
i += 1;
k += 1;
}
else
{
res[k] = b[j];
j += 1;
k += 1;
}
}
// Merging remaining
// elements of a[] (if any)
while (i < n)
{
res[k] = a[i];
i += 1;
k += 1;
}
// Merging remaining
// elements of b[] (if any)
while (j < m)
{
res[k] = b[j];
j += 1;
k += 1;
}
}
// Driver code
let a = [ 10, 5, 15 ];
let b = [ 20, 3, 2, 12 ];
let n = a.length;
let m = b.length;
// Final merge list
let res = new Array(n + m);
sortedMerge(a, b, res, n, m);
document.write("Sorted merge list :");
for(let i = 0; i < n + m; i++)
document.write(" " + res[i]);
// This code is contributed by Surbhi Tyagi.
</script>
Producción
Sorted merge list : 2 3 5 10 12 15 20n
Complejidad de tiempo: O (nlogn + mlogm + (n + m))
Complejidad de espacio: O ( (n + m) )
Es obvio por las complejidades de tiempo anteriores que el método 2 es mejor que el método 1 .
Este artículo es una contribución de Sachin Bisht . 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.
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