In-place tiene más de una definición. Una definición estricta es.
Un algoritmo in situ es un algoritmo que no necesita espacio extra y produce una salida en la misma memoria que contiene los datos transformando la entrada ‘in situ’. Sin embargo, se permite un pequeño espacio adicional constante utilizado para las variables.
Una definición más amplia es,
In situ significa que el algoritmo no utiliza espacio adicional para manipular la entrada, pero puede requerir un espacio adicional pequeño, aunque no constante, para su funcionamiento. Por lo general, este espacio es O (log n), aunque a veces se permite cualquier cosa en O (n) (menor que lineal).
Una implementación no local de invertir una array
C++
// An Not in-place C++ program to reverse an array
#include <bits/stdc++.h>
using namespace std;
/* Function to reverse arr[] from start to end*/
void reverseArray(int arr[], int n)
{
// Create a copy array and store reversed
// elements
int rev[n];
for (int i=0; i<n; i++)
rev[n-i-1] = arr[i];
// Now copy reversed elements back to arr[]
for (int i=0; i<n; i++)
arr[i] = rev[i];
}
/* Utility function to print an array */
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
/* Driver function to test above functions */
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
printArray(arr, n);
reverseArray(arr, n);
cout << "Reversed array is" << endl;
printArray(arr, n);
return 0;
}
Java
// An Not in-place Java program
// to reverse an array
import java.util.*;
class GFG
{
/* Function to reverse arr[]
from start to end*/
public static void reverseArray(int []arr,
int n)
{
// Create a copy array
// and store reversed
// elements
int []rev = new int[n];
for (int i = 0; i < n; i++)
rev[n - i - 1] = arr[i];
// Now copy reversed
// elements back to arr[]
for (int i = 0; i < n; i++)
arr[i] = rev[i];
}
/* Utility function to
print an array */
public static void printArray(int []arr,
int size)
{
for (int i = 0; i < size; i++)
System.out.print(arr[i] + " ");
System.out.println("");
}
// Driver code
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 4, 5, 6};
int n = arr.length;
printArray(arr, n);
reverseArray(arr, n);
System.out.println("Reversed array is");
printArray(arr, n);
}
}
// This code is contributed
// by Harshit Saini
Python3
# An Not in-place Python program
# to reverse an array
''' Function to reverse arr[]
from start to end '''
def reverseArray(arr, n):
# Create a copy array
# and store reversed
# elements
rev = n * [0]
for i in range(0, n):
rev[n - i - 1] = arr[i]
# Now copy reversed
# elements back to arr[]
for i in range(0, n):
arr[i] = rev[i]
# Driver code
if __name__ == "__main__":
arr = [1, 2, 3, 4, 5, 6]
n = len(arr)
print(*arr)
reverseArray(arr, n);
print("Reversed array is")
print(*arr)
# This code is contributed
# by Harshit Saini
C#
// An Not in-place C# program
// to reverse an array
using System;
class GFG
{
/* Function to reverse arr[]
from start to end*/
public static void reverseArray(int[] arr,
int n)
{
// Create a copy array
// and store reversed
// elements
int[] rev = new int[n];
for (int i = 0; i < n; i++)
rev[n - i - 1] = arr[i];
// Now copy reversed
// elements back to arr[]
for (int i = 0; i < n; i++)
arr[i] = rev[i];
}
/* Utility function to
print an array */
public static void printArray(int[] arr,
int size)
{
for (int i = 0; i < size; i++)
Console.Write(arr[i] + " ");
Console.Write("\n");
}
// Driver code
public static void Main()
{
int[] arr = {1, 2, 3, 4, 5, 6};
int n = arr.Length;
printArray(arr, n);
reverseArray(arr, n);
Console.WriteLine("Reversed array is");
printArray(arr, n);
}
}
// This code is contributed by Ita_c.
Javascript
<script>
// An Not in-place Javascript program
// to reverse an array
/* Function to reverse arr[]
from start to end*/
function reverseArray(arr,n)
{
// Create a copy array
// and store reversed
// elements
let rev = new Array(n);
for (let i = 0; i < n; i++)
rev[n - i - 1] = arr[i];
// Now copy reversed
// elements back to arr[]
for (let i = 0; i < n; i++)
arr[i] = rev[i];
}
/* Utility function to
print an array */
function printArray(arr,size)
{
for (let i = 0; i < size; i++)
document.write(arr[i] + " ");
document.write("<br>");
}
// Driver code
let arr=[1, 2, 3, 4, 5, 6];
let n = arr.length;
printArray(arr, n);
reverseArray(arr, n);
document.write("Reversed array is<br>");
printArray(arr, n);
// This code is contributed by rag2127
</script>
Producción:
1 2 3 4 5 6 Reversed array is 6 5 4 3 2 1
Complejidad de tiempo : O(n)
Esto necesita O(n) espacio adicional y es un ejemplo de un algoritmo no en el lugar.
Una implementación local de la inversión de una array.
C++
// An in-place C++ program to reverse an array
#include <bits/stdc++.h>
using namespace std;
/* Function to reverse arr[] from start to end*/
void reverseArray(int arr[], int n)
{
for (int i=0; i<n/2; i++)
swap(arr[i], arr[n-i-1]);
}
/* Utility function to print an array */
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
/* Driver function to test above functions */
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
printArray(arr, n);
reverseArray(arr, n);
cout << "Reversed array is" << endl;
printArray(arr, n);
return 0;
}
Java
// An in-place Java program
// to reverse an array
import java.util.*;
class GFG
{
public static int __(int x, int y) {return x;}
/* Function to reverse arr[]
from start to end*/
public static void reverseArray(int []arr,
int n)
{
for (int i = 0; i < n / 2; i++)
arr[i] = __(arr[n - i - 1],
arr[n - i - 1] = arr[i]);
}
/* Utility function to
print an array */
public static void printArray(int []arr,
int size)
{
for (int i = 0; i < size; i++)
System.out.print(Integer.toString(arr[i]) + " ");
System.out.println("");
}
// Driver code
public static void main(String[] args)
{
int []arr = new int[]{1, 2, 3, 4, 5, 6};
int n = arr.length;
printArray(arr, n);
reverseArray(arr, n);
System.out.println("Reversed array is");
printArray(arr, n);
}
}
// This code is contributed
// by Harshit Saini
Python3
# An in-place Python program
# to reverse an array
''' Function to reverse arr[]
from start to end'''
def reverseArray(arr, n):
for i in range(0, int(n / 2)):
arr[i], arr[n - i - 1] = arr[n - i - 1], arr[i]
# Driver code
if __name__ == "__main__":
arr = [1, 2, 3, 4, 5, 6]
n = len(arr)
print(*arr)
reverseArray(arr, n)
print("Reversed array is")
print(*arr)
# This code is contributed
# by Harshit Saini
C#
// An in-place C# program
// to reverse an array
using System;
class GFG
{
public static int __(int x, int y) {return x;}
/* Function to reverse arr[]
from start to end*/
public static void reverseArray(int []arr,
int n)
{
for (int i = 0; i < n / 2; i++)
arr[i] = __(arr[n - i - 1],
arr[n - i - 1] = arr[i]);
}
/* Utility function to
print an array */
public static void printArray(int []arr,
int size)
{
for (int i = 0; i < size; i++)
Console.Write(arr[i] + " ");
Console.WriteLine("");
}
// Driver code
public static void Main(String[] args)
{
int []arr = new int[]{1, 2, 3, 4, 5, 6};
int n = arr.Length;
printArray(arr, n);
reverseArray(arr, n);
Console.WriteLine("Reversed array is");
printArray(arr, n);
}
}
/* This code is contributed by PrinciRaj1992 */
Javascript
<script>
// An in-place Javascript program
// to reverse an array
function __(x,y)
{
return x;
}
/* Function to reverse arr[]
from start to end*/
function reverseArray(arr,n)
{
for (let i = 0; i < n / 2; i++)
arr[i] = __(arr[n - i - 1],
arr[n - i - 1] = arr[i]);
}
/* Utility function to
print an array */
function printArray(arr,size)
{
for (let i = 0; i < size; i++)
document.write(arr[i] + " ");
document.write("<br>");
}
// Driver code
let arr=[1, 2, 3, 4, 5, 6];
let n = arr.length;
printArray(arr, n);
reverseArray(arr, n);
document.write("Reversed array is<br>");
printArray(arr, n);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
1 2 3 4 5 6 Reversed array is 6 5 4 3 2 1
Complejidad de tiempo : O(n)
Esto necesita O(1) espacio adicional para intercambiar elementos y es un ejemplo de un algoritmo en el lugar.
¿Qué algoritmos de clasificación están en el lugar y cuáles no?
En el lugar: Ordenación de burbujas , Ordenación de selección , Ordenación de inserción , Ordenación de heapsort .
No en el lugar: ordenación por fusión . Tenga en cuenta que la ordenación por combinación requiere O(n) espacio adicional.
¿Qué pasa con QuickSort ? ¿Por qué se llama In-Place?
QuickSort usa espacio adicional para llamadas a funciones recursivas. Se llama en el lugar de acuerdo con una definición amplia, ya que el espacio adicional requerido no se usa para manipular la entrada, sino solo para llamadas recursivas.