Hemos hablado de Merge sort . Cómo modificar el algoritmo para que la fusión funcione en O(1) espacio extra y el algoritmo aún funcione en O(n Log n) tiempo. Podemos suponer que los valores de entrada son solo números enteros.
Ejemplos:
Input : 5 4 3 2 1 Output : 1 2 3 4 5 Input : 999 612 589 856 56 945 243 Output : 56 243 589 612 856 945 999
Para los tipos enteros, la ordenación por combinación se puede hacer en el lugar usando algún truco matemático de módulo y división. Eso significa almacenar el valor de dos elementos en un índice y se puede extraer usando el módulo y la división.
Primero tenemos que encontrar un valor mayor que todos los elementos de la array. Ahora podemos almacenar el valor original como módulo y el segundo valor como división. Supongamos que queremos almacenar arr[i] y arr[j] en el índice i (significa en arr[i]). Primero tenemos que encontrar un ‘maxval’ mayor que arr[i] y arr[j]. Ahora podemos almacenar como arr[i] = arr[i] + arr[j]*maxval . Ahora arr[i]%maxval dará el valor original de arr[i] y arr[i]/maxval dará el valor de arr[j]. Entonces, a continuación se muestra la implementación en el ordenamiento por fusión.
Enfoque: (División Euclidiana)
dividendo = divisor * cociente + resto
ej: 5/3 = q:1, r:2 aplicando euclidiana: 3*1+2 =>5 (dividendo)
divisor = maxele (elemento máximo absoluto en la array) + 1 (para que siempre obtengamos un resto distinto de cero)
cociente = min (primero, segundo)
resto = elemento originalNota: (al obtener el elemento actual, suponga que el contenedor actual ya tiene un elemento codificado, por lo tanto, use % divisor)
primero = arr[i] % divisor
segundo = arr[j] % divisorelemento codificado = resto + cociente*divisor
Posibles problemas en la fusión:
1. Si el número actual es Integer.MAX, entonces el nuevo valor codificado, que generalmente es mayor que el elemento actual, causará un desbordamiento de números enteros y corrupción de datos (en python no hay límite para el tamaño del número, por lo que este problema no ocurrirá).
2. No maneja números negativos (es decir, al codificar un número -ve (actual) con otro número -ve (elegido más pequeño) el signo no se puede conservar ya que ambos números tienen el signo -ve. También se deben usar valores absolutos cuando se calcula dividendo = divisor*cociente+resto (divisor = maxele, cociente = menor, resto = original) y se debe restaurar el signo, es posible que no funcione debido a un problema de conservación del signo.
3. Solo aplicable a números enteros sin signo, como índices que normalmente no son negativos.
4. AUX = O(n) en el peor de los casos, asumiendo que en un lenguaje como python donde no hay límite para el tamaño de palabra/entero, cuando los elementos de la array de entrada están casi en Integer.MAX, entonces el valor codificado requerirá posiblemente un espacio de 2x bits para representan un nuevo número, el espacio de bits 2x en total puede convertirse en un tamaño de array +1x, que es casi como crear una array AUX pero de forma indirecta.
5. Las operaciones de modificación y división son las más costosas, por lo que reducen el rendimiento general (hasta cierto punto).
C++
// C++ program to sort an array using merge sort such
// that merge operation takes O(1) extra space.
#include <bits/stdc++.h>
using namespace std;
void merge(int arr[], int beg, int mid, int end, int maxele)
{
int i = beg;
int j = mid + 1;
int k = beg;
while (i <= mid && j <= end) {
if (arr[i] % maxele <= arr[j] % maxele) {
arr[k] = arr[k] + (arr[i] % maxele) * maxele;
k++;
i++;
}
else {
arr[k] = arr[k] + (arr[j] % maxele) * maxele;
k++;
j++;
}
}
while (i <= mid) {
arr[k] = arr[k] + (arr[i] % maxele) * maxele;
k++;
i++;
}
while (j <= end) {
arr[k] = arr[k] + (arr[j] % maxele) * maxele;
k++;
j++;
}
// Obtaining actual values
for (int i = beg; i <= end; i++)
arr[i] = arr[i] / maxele;
}
// Recursive merge sort with extra parameter, naxele
void mergeSortRec(int arr[], int beg, int end, int maxele)
{
if (beg < end) {
int mid = (beg + end) / 2;
mergeSortRec(arr, beg, mid, maxele);
mergeSortRec(arr, mid + 1, end, maxele);
merge(arr, beg, mid, end, maxele);
}
}
// This functions finds max element and calls recursive
// merge sort.
void mergeSort(int arr[], int n)
{
int maxele = *max_element(arr, arr+n) + 1;
mergeSortRec(arr, 0, n-1, maxele);
}
int main()
{
int arr[] = { 999, 612, 589, 856, 56, 945, 243 };
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, n);
cout << "Sorted array \n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Java
// Java program to sort an array
// using merge sort such that
// merge operation takes O(1)
// extra space.
import java.util.Arrays;
class GFG
{
static void merge(int[] arr, int beg,
int mid, int end,
int maxele)
{
int i = beg;
int j = mid + 1;
int k = beg;
while (i <= mid && j <= end)
{
if (arr[i] % maxele <=
arr[j] % maxele)
{
arr[k] = arr[k] + (arr[i]
% maxele) * maxele;
k++;
i++;
}
else
{
arr[k] = arr[k] +
(arr[j] % maxele)
* maxele;
k++;
j++;
}
}
while (i <= mid)
{
arr[k] = arr[k] + (arr[i]
% maxele) * maxele;
k++;
i++;
}
while (j <= end)
{
arr[k] = arr[k] + (arr[j]
% maxele) * maxele;
k++;
j++;
}
// Obtaining actual values
for (i = beg; i <= end; i++)
{
arr[i] = arr[i] / maxele;
}
}
// Recursive merge sort
// with extra parameter, naxele
static void mergeSortRec(int[] arr, int beg,
int end, int maxele)
{
if (beg < end)
{
int mid = (beg + end) / 2;
mergeSortRec(arr, beg,
mid, maxele);
mergeSortRec(arr, mid + 1,
end, maxele);
merge(arr, beg, mid,
end, maxele);
}
}
// This functions finds
// max element and calls
// recursive merge sort.
static void mergeSort(int[] arr, int n)
{
int maxele = Arrays.stream(arr).max().getAsInt() + 1;
mergeSortRec(arr, 0, n - 1, maxele);
}
// Driver code
public static void main(String[] args)
{
int[] arr = {999, 612, 589,
856, 56, 945, 243};
int n = arr.length;
mergeSort(arr, n);
System.out.println("Sorted array ");
for (int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to sort an array using
# merge sort such that merge operation
# takes O(1) extra space.
def merge(arr, beg, mid, end, maxele):
i = beg
j = mid + 1
k = beg
while (i <= mid and j <= end):
if (arr[i] % maxele <= arr[j] % maxele):
arr[k] = arr[k] + (arr[i] %
maxele) * maxele
k += 1
i += 1
else:
arr[k] = arr[k] + (arr[j] %
maxele) * maxele
k += 1
j += 1
while (i <= mid):
arr[k] = arr[k] + (arr[i] %
maxele) * maxele
k += 1
i += 1
while (j <= end):
arr[k] = arr[k] + (arr[j] %
maxele) * maxele
k += 1
j += 1
# Obtaining actual values
for i in range(beg, end + 1):
arr[i] = arr[i] // maxele
# Recursive merge sort with extra
# parameter, naxele
def mergeSortRec(arr, beg, end, maxele):
if (beg < end):
mid = (beg + end) // 2
mergeSortRec(arr, beg, mid, maxele)
mergeSortRec(arr, mid + 1, end, maxele)
merge(arr, beg, mid, end, maxele)
# This functions finds max element and
# calls recursive merge sort.
def mergeSort(arr, n):
maxele = max(arr) + 1
mergeSortRec(arr, 0, n - 1, maxele)
# Driver Code
if __name__ == '__main__':
arr = [ 999, 612, 589, 856, 56, 945, 243 ]
n = len(arr)
mergeSort(arr, n)
print("Sorted array")
for i in range(n):
print(arr[i], end = " ")
# This code is contributed by mohit kumar 29
C#
// C# program to sort an array
// using merge sort such that
// merge operation takes O(1)
// extra space.
using System;
using System.Linq;
class GFG
{
static void merge(int []arr, int beg,
int mid, int end,
int maxele)
{
int i = beg;
int j = mid + 1;
int k = beg;
while (i <= mid && j <= end)
{
if (arr[i] %
maxele <= arr[j] % maxele)
{
arr[k] = arr[k] + (arr[i] %
maxele) * maxele;
k++;
i++;
}
else
{
arr[k] = arr[k] +
(arr[j] % maxele) *
maxele;
k++;
j++;
}
}
while (i <= mid)
{
arr[k] = arr[k] + (arr[i] %
maxele) * maxele;
k++;
i++;
}
while (j <= end)
{
arr[k] = arr[k] + (arr[j] %
maxele) * maxele;
k++;
j++;
}
// Obtaining actual values
for ( i = beg; i <= end; i++)
arr[i] = arr[i] / maxele;
}
// Recursive merge sort
// with extra parameter, naxele
static void mergeSortRec(int []arr, int beg,
int end, int maxele)
{
if (beg < end)
{
int mid = (beg + end) / 2;
mergeSortRec(arr, beg,
mid, maxele);
mergeSortRec(arr, mid + 1,
end, maxele);
merge(arr, beg, mid,
end, maxele);
}
}
// This functions finds
// max element and calls
// recursive merge sort.
static void mergeSort(int []arr, int n)
{
int maxele = arr.Max() + 1;
mergeSortRec(arr, 0, n - 1, maxele);
}
//Driver code
public static void Main ()
{
int []arr = {999, 612, 589,
856, 56, 945, 243};
int n = arr.Length;
mergeSort(arr, n);
Console.WriteLine("Sorted array ");
for (int i = 0; i < n; i++)
Console.Write( arr[i] + " ");
}
}
// This code is contributed
// by inder_verma.
Javascript
<script>
// Javascript program to sort an array
// using merge sort such that
// merge operation takes O(1)
// extra space.
function merge(arr,beg,mid,end,maxele)
{
let i = beg;
let j = mid + 1;
let k = beg;
while (i <= mid && j <= end)
{
if (arr[i] % maxele <=
arr[j] % maxele)
{
arr[k] = arr[k] + (arr[i]
% maxele) * maxele;
k++;
i++;
}
else
{
arr[k] = arr[k] +
(arr[j] % maxele)
* maxele;
k++;
j++;
}
}
while (i <= mid)
{
arr[k] = arr[k] + (arr[i]
% maxele) * maxele;
k++;
i++;
}
while (j <= end)
{
arr[k] = arr[k] + (arr[j]
% maxele) * maxele;
k++;
j++;
}
// Obtaining actual values
for (i = beg; i <= end; i++)
{
arr[i] = Math.floor(arr[i] / maxele);
}
}
// Recursive merge sort
// with extra parameter, naxele
function mergeSortRec(arr,beg,end,maxele)
{
if (beg < end)
{
let mid = Math.floor((beg + end) / 2);
mergeSortRec(arr, beg,
mid, maxele);
mergeSortRec(arr, mid + 1,
end, maxele);
merge(arr, beg, mid,
end, maxele);
}
}
// This functions finds
// max element and calls
// recursive merge sort.
function mergeSort(arr,n)
{
let maxele = Math.max(...arr) + 1;
mergeSortRec(arr, 0, n - 1, maxele);
}
// Driver code
let arr=[999, 612, 589,
856, 56, 945, 243];
let n = arr.length;
mergeSort(arr, n);
document.write("Sorted array <br>");
for (let i = 0; i < n; i++)
{
document.write(arr[i] + " ");
}
// This code is contributed by patel2127
</script>
Sorted array 56 243 589 612 856 945 999
Publicación traducida automáticamente
Artículo escrito por Ankesh Kumar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA