Dada una array de longitud n + 1, que contiene elementos del 1 al n y un espacio, requiere el uso de una función de intercambio dada (índice i, índice j) para ordenar la array, solo puede intercambiar el espacio y un número, en el final, ponga la brecha al final.
Habrá un número 999 en la array como un hueco o espacio.
Ejemplos:
Input : arr = {1, 5, 4, 999, 3, 2}
Output : arr = {1, 2, 3, 4, 5, 999}
We need to sort only by moving
Input : arr = {1, 5, 4, 3, 2, 8, 7, 999, 6}
Output : arr = {1, 2, 3, 4, 5, 6, 7, 8, 999}
Seguimos un enfoque recursivo para resolver este problema. Como solo podemos intercambiar números con el espacio. En primer lugar, encontramos el índice del espacio. Si el índice es el comienzo de la array, mueva este espacio al penúltimo índice intercambiando con cada número a su derecha.
Si el espacio no es ni el comienzo de una array ni el último elemento de la array y el elemento anterior es mayor que el elemento al lado del espacio, haga lo siguiente.
Paso 1: Intercambiar espacio y elemento al lado del espacio
En el caso de {3, 999, 2} convertirlo en {3, 2, 999}
Paso 2: Intercambiar espacio y elemento mayor,
por ejemplo, convertir {3, 2, 999} a {999 , 2, 3}
De lo contrario, los elementos al lado del índice se ordenan y lo intercambian con el elemento anterior. Vuelva a llamar a la función de clasificación con el tamaño de una array disminuido en 1 y el índice del espacio – 1, ya que obtendremos un elemento ordenado cada vez.
C++
// CPP program to sort an array by moving one
// space around.
#include <bits/stdc++.h>
using namespace std;
// n is total number of elements.
// index is index of 999 or space.
// k is number of elements yet to be sorted.
void sortRec(int arr[], int index, int k, int n)
{
// print the sorted array when loop reaches
// the base case
if (k == 0) {
for (int i = 1; i < n; i++)
cout << arr[i] << " ";
cout << 999;
return;
}
// else if k>0 and space is at 0th index swap
// each number with space and store index at
// second last index
else if (k > 0 && index == 0) {
index = n - 2;
for (int i = 1; i <= index; i++) {
arr[i - 1] = arr[i];
}
arr[index] = 999;
}
// if space is neither start of array nor last
// element of array and element before it greater
// than/ the element next to space
if (index - 1 >= 0 && index + 1 < n &&
arr[index - 1] > arr[index + 1]) {
// first swap space and element next to space
// in case of {3, 999, 2} make it {3, 2, 999}
swap(arr[index], arr[index + 1]);
// than swap space and greater element
// convert {3, 2, 999} to {999, 2, 3}
swap(arr[index - 1], arr[index + 1]);
}
else
swap(arr[index], arr[index - 1]);
sortRec(arr, index - 1, k - 1, n);
}
// Wrapper over sortRec.
void sort(int arr[], int n)
{
// Find index of space (or 999)
int index = -1;
for (int i = 0; i < n; i++) {
if (arr[i] == 999) {
index = i;
break;
}
}
// Invalid input
if (index == -1)
return;
sortRec(arr, index, n, n);
}
// driver program
int main()
{
int arr[] = { 3, 2, 999, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, n);
return 0;
}
Java
// Java program to sort an array by moving one
// space around.
class GFG
{
// n is total number of elements.
// index is index of 999 or space.
// k is number of elements yet to be sorted.
static void sortRec(int arr[], int index, int k, int n)
{
// print the sorted array when loop reaches
// the base case
if (k == 0)
{
for (int i = 1; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println(999);
return;
}
// else if k>0 and space is at 0th index swap
// each number with space and store index at
// second last index
else if (k > 0 && index == 0)
{
index = n - 2;
for (int i = 1; i <= index; i++)
{
arr[i - 1] = arr[i];
}
arr[index] = 999;
}
// if space is neither start of array nor last
// element of array and element before it greater
// than/ the element next to space
if (index - 1 >= 0 && index + 1 < n &&
arr[index - 1] > arr[index + 1])
{
// first swap space and element next to space
// in case of {3, 999, 2} make it {3, 2, 999}
swap(arr,index, index + 1);
// than swap space and greater element
// convert {3, 2, 999} to {999, 2, 3}
swap(arr,index - 1, index + 1);
}
else
swap(arr,index, index - 1);
sortRec(arr, index - 1, k - 1, n);
}
static int[] swap(int []arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Wrapper over sortRec.
static void sort(int arr[], int n)
{
// Find index of space (or 999)
int index = -1;
for (int i = 0; i < n; i++)
{
if (arr[i] == 999)
{
index = i;
break;
}
}
// Invalid input
if (index == -1)
return;
sortRec(arr, index, n, n);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 3, 2, 999, 1 };
int n = arr.length;
sort(arr, n);
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 program to sort an array
# by moving one space around.
# n is total number of elements.
# index is index of 999 or space.
# k is number of elements yet to be sorted.
def sortRec(arr, index, k, n):
# Print the sorted array when loop reaches
# the base case
if (k == 0):
for i in range(1,n):
print(arr[i],end=" ")
print(999,end="")
# Else if k>0 and space is at 0th index swap
# each number with space and store index at
# second last index
elif(k > 0 and index == 0):
index = n - 2
for i in range(1,index+1):
arr[i - 1] = arr[i]
arr[index] = 999
# If space is neither start of array nor last
# element of array and element before it greater
# than/ the element next to space
if (index - 1 >= 0 and index + 1 < n and arr[index - 1] > arr[index + 1]):
# First swap space and element next to space
# in case of {3, 999, 2} make it {3, 2, 999}
arr[index],arr[index+1] = arr[index+1],arr[index]
# Than swap space and greater element
# convert {3, 2, 999} to {999, 2, 3}
arr[index-1],arr[index+1] = arr[index+1],arr[index-1]
else:
if(index-1<0):
return
arr[index],arr[index-1] = arr[index-1],arr[index]
sortRec(arr, index - 1, k - 1, n)
# Wrapper over sortRec.
def sort(arr, n):
# Find index of space (or 999)
index = -1
for i in range(n):
if (arr[i] == 999):
index = i
break
# Invalid input
if (index == -1):
return
sortRec(arr, index, n, n)
# Driver Code
arr = [ 3, 2, 999, 1 ]
n=len(arr)
sort(arr, n)
# This code is contributed by rag2127.
C#
// C# program to sort an array by moving one
// space around.
using System;
class GFG
{
// n is total number of elements.
// index is index of 999 or space.
// k is number of elements yet to be sorted.
static void sortRec(int []arr, int index, int k, int n)
{
// print the sorted array when loop reaches
// the base case
if (k == 0)
{
for (int i = 1; i < n; i++)
Console.Write(arr[i] + " ");
Console.WriteLine(999);
return;
}
// else if k>0 and space is at 0th index swap
// each number with space and store index at
// second last index
else if (k > 0 && index == 0)
{
index = n - 2;
for (int i = 1; i <= index; i++)
{
arr[i - 1] = arr[i];
}
arr[index] = 999;
}
// if space is neither start of array nor last
// element of array and element before it greater
// than/ the element next to space
if (index - 1 >= 0 && index + 1 < n &&
arr[index - 1] > arr[index + 1])
{
// first swap space and element next to space
// in case of {3, 999, 2} make it {3, 2, 999}
swap(arr,index, index + 1);
// than swap space and greater element
// convert {3, 2, 999} to {999, 2, 3}
swap(arr,index - 1, index + 1);
}
else
swap(arr,index, index - 1);
sortRec(arr, index - 1, k - 1, n);
}
static int[] swap(int []arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Wrapper over sortRec.
static void sort(int []arr, int n)
{
// Find index of space (or 999)
int index = -1;
for (int i = 0; i < n; i++)
{
if (arr[i] == 999)
{
index = i;
break;
}
}
// Invalid input
if (index == -1)
return;
sortRec(arr, index, n, n);
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 3, 2, 999, 1 };
int n = arr.Length;
sort(arr, n);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to sort an array
// by moving one space around.
// n is total number of elements.
// index is index of 999 or space.
// k is number of elements yet to be sorted.
function sortRec(arr, index, k, n)
{
// Print the sorted array when loop reaches
// the base case
if (k == 0)
{
for(let i = 1; i < n; i++)
document.write(arr[i] + " ");
document.write(999);
return;
}
// Else if k>0 and space is at 0th index swap
// each number with space and store index at
// second last index
else if (k > 0 && index == 0)
{
index = n - 2;
for(let i = 1; i <= index; i++)
{
arr[i - 1] = arr[i];
}
arr[index] = 999;
}
// If space is neither start of array nor last
// element of array and element before it greater
// than/ the element next to space
if (index - 1 >= 0 && index + 1 < n &&
arr[index - 1] > arr[index + 1])
{
// First swap space and element next to space
// in case of {3, 999, 2} make it {3, 2, 999}
swap(arr, index, index + 1);
// Than swap space and greater element
// convert {3, 2, 999} to {999, 2, 3}
swap(arr, index - 1, index + 1);
}
else
swap(arr,index, index - 1);
sortRec(arr, index - 1, k - 1, n);
}
function swap(arr, i, j)
{
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Wrapper over sortRec.
function sort(arr, n)
{
// Find index of space (or 999)
let index = -1;
for(let i = 0; i < n; i++)
{
if (arr[i] == 999)
{
index = i;
break;
}
}
// Invalid input
if (index == -1)
return;
sortRec(arr, index, n, n);
}
// Driver Code
let arr = [ 3, 2, 999, 1 ];
let n = arr.length;
sort(arr, n);
// This code is contributed by susmitakundugoaldanga
</script>
Producción:
1 2 3 999
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por niteesh_Kr y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA