Dada una array arr[] que contiene N enteros, con duplicados. La tarea es ordenar la array en orden creciente utilizando como máximo N desplazamiento cíclico en cualquier sub-array.
El cambio cíclico en cualquier subarreglo significa eliminar cualquier subarreglo del arreglo dado, usar el cambio cíclico (rotar) en él por cualquier desplazamiento y volver a colocarlo en el mismo lugar del arreglo.
Imprime el número de cambios necesarios para ordenar la array. Puede haber múltiples posibilidades.
Ejemplos:
Entrada: arr[] = [1, 3, 2, 8, 5]
Salida: 2
Explicación: Considere el segmento desde index = 1 hasta index = 2 . [1, 3, 2 , 8, 5]. Ahora gire este segmento por 1 desplazamiento. La nueva array se convierte en [1, 2, 3 , 8, 5].
Luego considere el segmento del índice = 3 al índice = 4, [1, 2, 3, 8, 5 ]. Gírelo por 1 desplazamiento, la nueva array se convierte en [1, 2, 3, 5, 8].Entrada: arr[] = [2, 4, 1, 3]
Salida: 2
Explicación: De índice = 0 a índice = 2, [ 2, 4, 1 , 3]. Gire este segmento en 2 desplazamientos a la izquierda, la nueva array se convierte en [ 1, 2, 4, 3].
Tomando el segundo segmento del índice = 2 al índice = 3 del desplazamiento 1, gírelo, la nueva array se convierte en [1, 2, 4, 3 ].
Planteamiento: Puede haber dos casos:
- Caso cuando la array ya está ordenada: Entonces no necesitamos realizar ninguna operación de cambio
- Caso cuando la array no está ordenada: para eso, siga los pasos que se mencionan a continuación:
- Cree una variable conteo = 0 para almacenar el número total de conteos.
- Iterar de i = 0 a i = N-2 . Y para cada iteración hacer las siguientes operaciones:
- Cree una variable minVal para almacenar el valor mínimo encontrado en esta iteración e inícielo con el valor de arr[i] .
- Comience a iterar de i+1 a N-1 . Si el valor actual es menor que minVal, actualice minVal .
- Marque esa posición a la derecha para realizar un cambio cíclico de i a la derecha con el desplazamiento 1.
- Si no existe tal valor correcto, simplemente pase a la siguiente iteración .
- De lo contrario, gire la array de i a la derecha en 1 posición e incremente la cuenta en 1.
- Devuelve el valor de count como tu respuesta.
A continuación se muestra la implementación de C++ para el enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to Sort given Array using
// at most N cyclic shift on any subarray
int ShiftingSort(vector<int>& arr, int n)
{
vector<int> temp(arr.begin(), arr.end());
sort(temp.begin(), temp.end());
// Variable to store count of
// shifting operations
int count = 0;
// If the vector arr is already sorted
// the 0 operations shift required
if (arr == temp) {
return 0;
}
else {
// Run a loop from 0 to n-2 index
for (int index1 = 0; index1 < n - 1; index1++) {
int minval = arr[index1];
int left = index1;
int right = -1;
// Loop from i+1 to n-1
// to find the minimum value
for (int index2 = index1 + 1; index2 < n;
index2++) {
if (minval > arr[index2]) {
minval = arr[index2];
right = index2;
}
}
// Check if the shifting is required
if (right != -1) {
// Increment count operations
count++;
int index = right;
int tempval = arr[right];
// Loop for shifting the array arr
// from index = left to index = right
while (index > left) {
arr[index] = arr[index - 1];
index--;
}
arr[index] = tempval;
}
}
}
// Return the total operations
return count;
}
// Driver code
int main()
{
vector<int> arr{ 1, 3, 2, 8, 5 };
int N = 5;
cout << ShiftingSort(arr, N) << "\n";
return 0;
}
Java
// Java code to implement the above approach
import java.util.*;
public class GFG
{
// Function to Sort given Array using
// at most N cyclic shift on any subarray
static int ShiftingSort(ArrayList<Integer> arr, int n)
{
ArrayList<Integer> temp = new ArrayList<Integer>();
for(int i = 0; i < arr.size(); i++) {
temp.add(arr.get(i));
}
Collections.sort(temp);
// Variable to store count of
// shifting operations
int count = 0;
// If the vector arr is already sorted
// the 0 operations shift required
if (arr.equals(temp)) {
return 0;
}
else {
// Run a loop from 0 to n-2 index
for (int index1 = 0; index1 < n - 1; index1++) {
int minval = arr.get(index1);
int left = index1;
int right = -1;
// Loop from i+1 to n-1
// to find the minimum value
for (int index2 = index1 + 1; index2 < n;
index2++) {
if (minval > arr.get(index2)) {
minval = arr.get(index2);
right = index2;
}
}
// Check if the shifting is required
if (right != -1) {
// Increment count operations
count++;
int index = right;
int tempval = arr.get(right);
// Loop for shifting the array arr
// from index = left to index = right
while (index > left) {
arr.set(index, arr.get(index - 1));
index--;
}
arr.set(index, tempval);
}
}
}
// Return the total operations
return count;
}
// Driver code
public static void main(String args[])
{
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(1);
arr.add(3);
arr.add(2);
arr.add(8);
arr.add(5);
int N = 5;
System.out.println(ShiftingSort(arr, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python Program to implement # the above approach # Function to Sort given Array using # at most N cyclic shift on any subarray def ShiftingSort(arr, n): temp = arr.copy() temp.sort() # Variable to store count of # shifting operations count = 0 # If the vector arr is already sorted # the 0 operations shift required if (arr == temp): return 0 else: # Run a loop from 0 to n-2 index for index1 in range(n - 1): minval = arr[index1] left = index1 right = -1 # Loop from i+1 to n-1 # to find the minimum value for index2 in range(index1 + 1, n): if (minval > arr[index2]): minval = arr[index2] right = index2 # Check if the shifting is required if (right != -1): # Increment count operations count += 1 index = right tempval = arr[right] # Loop for shifting the array arr # from index = left to index = right while (index > left): arr[index] = arr[index - 1] index -= 1 arr[index] = tempval # Return the total operations return count # Driver code arr = [1, 3, 2, 8, 5] N = 5 print(ShiftingSort(arr, N)) # This code is contributed by gfgking
C#
// C# code to implement the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Function to Sort given Array using
// at most N cyclic shift on any subarray
static int ShiftingSort(ArrayList arr, int n)
{
ArrayList temp = new ArrayList();
for(int i = 0; i < arr.Count; i++) {
temp.Add(arr[i]);
}
temp.Sort();
// Variable to store count of
// shifting operations
int count = 0;
// If the vector arr is already sorted
// the 0 operations shift required
if (arr.Equals(temp)) {
return 0;
}
else
{
// Run a loop from 0 to n-2 index
for (int index1 = 0; index1 < n - 1; index1++) {
int minval = (int)arr[index1];
int left = index1;
int right = -1;
// Loop from i+1 to n-1
// to find the minimum value
for (int index2 = index1 + 1; index2 < n;
index2++) {
if (minval > (int)arr[index2]) {
minval = (int)arr[index2];
right = index2;
}
}
// Check if the shifting is required
if (right != -1)
{
// Increment count operations
count++;
int index = right;
int tempval = (int)arr[right];
// Loop for shifting the array arr
// from index = left to index = right
while (index > left) {
arr[index] = arr[index - 1];
index--;
}
arr[index] = tempval;
}
}
}
// Return the total operations
return count;
}
// Driver code
public static void Main()
{
ArrayList arr = new ArrayList();
arr.Add(1);
arr.Add(3);
arr.Add(2);
arr.Add(8);
arr.Add(5);
int N = 5;
Console.Write(ShiftingSort(arr, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to Sort given Array using
// at most N cyclic shift on any subarray
function ShiftingSort(arr, n) {
let temp = [...arr];
temp.sort(function (a, b) { return a - b })
// Variable to store count of
// shifting operations
let count = 0;
// If the vector arr is already sorted
// the 0 operations shift required
if (arr == temp) {
return 0;
}
else {
// Run a loop from 0 to n-2 index
for (let index1 = 0; index1 < n - 1; index1++) {
let minval = arr[index1];
let left = index1;
let right = -1;
// Loop from i+1 to n-1
// to find the minimum value
for (let index2 = index1 + 1; index2 < n;
index2++) {
if (minval > arr[index2]) {
minval = arr[index2];
right = index2;
}
}
// Check if the shifting is required
if (right != -1)
{
// Increment count operations
count++;
let index = right;
let tempval = arr[right];
// Loop for shifting the array arr
// from index = left to index = right
while (index > left) {
arr[index] = arr[index - 1];
index--;
}
arr[index] = tempval;
}
}
}
// Return the total operations
return count;
}
// Driver code
let arr = [1, 3, 2, 8, 5];
let N = 5;
document.write(ShiftingSort(arr, N) + '<br>');
// This code is contributed by Potta Lokesh
</script>
Producción
2
Complejidad de tiempo: O(N 2 )
Complejidad de espacio: O(1)