Dada una array arr[] de tamaño N que consta de elementos únicos en el rango [0, N-1] , la tarea es encontrar K , que es el número de pasos necesarios para ordenar la array dada seleccionando tres elementos distintos y reorganizándolos . Y también, imprimir los índices seleccionados en esos K pasos en K líneas.
Por ejemplo, en la array {5, 4, 3, 2, 1, 0}, una forma posible de ordenar la array dada seleccionando tres elementos distintos es seleccionar los números {2, 1, 0} y ordenarlos como { 0, 1, 2} haciendo así la array {5, 4, 3, 0, 1, 2}. De manera similar, se realizan las operaciones restantes y los índices seleccionados ({3, 4, 5} en el caso anterior) se imprimen en líneas separadas.
Ejemplos:
Entrada: arr[] = {0, 5, 4, 3, 2, 1}
Salida:
2
1 2 5
2 5 4
Explicación:
La array anterior se puede ordenar en 2 pasos:
Paso I: Cambiamos el orden de los elementos en índices 1, 2, 5 entonces la array se convierte en {0, 1, 5, 3, 2, 4}.
Paso II: Nuevamente cambiamos el orden de los elementos en los índices 2, 5, 4, luego la array se convierte en {0, 1, 2, 3, 4, 5} que se ordena.
Entrada: arr[] = {0, 3, 1, 6, 5, 2, 4}
Salida: -1
Explicación:
La array anterior no se puede ordenar en ningún número de pasos.
Supongamos que elegimos los índices 1, 3, 2 y luego la array se convierte en {0, 1, 6, 3, 5, 2, 4}
Después de eso, elegimos los índices 2, 6, 4 y luego la array se convierte en {0, 1, 5, 3, 4, 2, 6}.
Ahora solo quedan dos elementos sin ordenar, por lo que no podemos elegir 3 elementos, por lo que la array anterior no se puede ordenar. Podemos probar con cualquier orden de índices y siempre nos quedarán 2 elementos sin clasificar.
Enfoque: La idea es primero contar los elementos que no están ordenados e insertarlos en un conjunto desordenado . Si el conteo es 0, entonces no necesitamos ningún número de pasos para ordenar la array, así que imprimimos 0 y salimos. De lo contrario, primero borramos todos los elementos del conjunto para los cuales i = A[A[i]] y luego realizamos la siguiente operación hasta que el conjunto se vacía:
- Seleccionamos todas las combinaciones posibles de índices (si están disponibles) de modo que se ordenen un mínimo de dos elementos.
- Ahora, cambia el orden de los elementos y bórralos del conjunto si i = A[i].
- Entonces, nos quedan solo aquellos elementos tales que i = A[A[i]] y la cuenta de ellos debe ser un múltiplo de 4, de lo contrario no es posible ordenar los elementos.
- Luego, elegimos dos pares cualquiera y cambiamos el orden de los elementos dos veces. Luego, los cuatro elementos elegidos se ordenarán.
- Almacenamos todos los índices que están involucrados en el cambio de orden de los elementos en un vector y lo imprimimos como respuesta.
Entendamos el enfoque anterior con un ejemplo. Sea el arreglo arr[] = {0, 8, 9, 10, 1, 7, 12, 4, 3, 2, 6, 5, 11}. Después:
- Inicialmente, el conjunto contendrá los 12 elementos y no hay elementos tales que i = A[A[i]].
- Ahora, se eligen {11, 5, 7} y se cambia el orden de los elementos. Entonces, arr[] = {0, 8, 9, 10, 1, 5, 12, 7, 3, 2, 6, 4, 11}.
- Ahora, se eligen {11, 4, 1} y se cambia el orden de los elementos. Entonces, arr[] = {0, 1, 9, 10, 4, 5, 12, 7, 3, 2, 6, 8, 11}.
- Ahora, se eligen {11, 8, 3} y se cambia el orden de los elementos. Entonces, arr[] = {0, 1, 9, 3, 4, 5, 12, 7, 8, 2, 6, 10, 11}.
- Ahora, se eligen {11, 10, 6} y se cambia el orden de los elementos. Entonces, arr[] = {0, 1, 9, 3, 4, 5, 6, 7, 8, 2, 10, 12, 11}.
- Después del paso anterior, nos quedan dos pares de elementos desordenados tales que i = A[A[i]].
- Finalmente, se eligen y reordenan {2, 11, 9} y {11, 9, 5}. Luego, arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} que se ordena.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to sort the array
// by changing the order of
// three elements
#include <bits/stdc++.h>
using namespace std;
// Function to change the order of
// the elements having a temporary
// vector and the required indices
// as the arguments
void cngorder(vector<int>& v, int i,
int j, int k)
{
int temp = v[k];
v[k] = v[j];
v[j] = v[i];
v[i] = temp;
}
// Function to sort the elements having
// the given array and its size.
void sortbyorder3(vector<int>& A, int n)
{
// Flag to check whether the sorting
// is possible or not
bool flag = 0;
int count = 0;
// Set that will contains unsorted
// elements
unordered_set<int> s;
// Iterating through the elements
for (int i = 0; i < n; i++) {
// Inserting the required elements
// in the set
if (i != A[i])
count++, s.insert(i);
}
// When the given array is
// already sorted
if (count == 0)
cout << "0" << endl;
else {
// Vector that will contain
// the answer
vector<vector<int> > ans;
// Temporary vector to store
// the indices
vector<int> vv;
int x, y, z;
count = 0;
// Loop that will execute till the
// set becomes empty
while (!s.empty()) {
auto it = s.begin();
int i = *it;
// Check for the condition
if (i == A[A[i]]) {
s.erase(i);
s.erase(A[i]);
continue;
}
// Case when the minimum two
// elements will get sorted
else {
x = A[i], y = A[A[i]], z = A[A[A[i]]];
vv.push_back(x), vv.push_back(y),
vv.push_back(z);
// Changing the order of elements
cngorder(A, x, y, z);
// Pushing the indices to the
// answer vector
ans.push_back(vv);
// If the third element also
// gets sorted
if (vv[0] == A[vv[0]])
s.erase(vv[0]);
// Erasing the two sorted elements
// from the set
s.erase(vv[1]), s.erase(vv[2]);
vv.clear();
}
}
count = 0;
// The count of the remaining
// unsorted elements
for (int i = 0; i < n; i++) {
if (i != A[i])
count++;
}
// If the count of the left
// unsorted elements is not
// a multiple of 4, then
// sorting is not possible
if (count % 4 != 0)
flag = 1;
// Only the elements such that
// i = A[A[i]] are left
// for sorting
else {
// Indices of any one element
// from the two pairs that
// will be sorted in 2 steps
int i1 = -1, i2 = -1;
for (int i = 0; i < n; i++) {
// Index of any element of
// the pair
if (A[i] != i && i1 == -1) {
i1 = i;
}
// When we find the second
// pair and the index of
// any one element is stored
else if (A[i] != i && i1 != -1
&& i2 == -1) {
if (i1 == A[i])
continue;
else
i2 = i;
}
// When we got both the pair
// of elements
if (i1 != -1 && i2 != -1) {
// Remaining two indices
// of the elements
int i3 = A[i1], i4 = A[i2];
// The first order of indices
vv.push_back(i1),
vv.push_back(i2),
vv.push_back(A[i1]);
// Pushing the indices to the
// answer vector
ans.push_back(vv);
vv.clear();
// The second order of indices
vv.push_back(i2),
vv.push_back(A[i1]),
vv.push_back(A[i2]);
// Pushing the indices to the
// answer vector
ans.push_back(vv);
vv.clear();
// Changing the order of the
// first combination of
// the indices
cngorder(A, i1, i2, i3);
// Changing the order of the
// second combination of
// the indices after which all
// the 4 elements will be sorted
cngorder(A, i2, i3, i4);
i1 = -1, i2 = -1;
}
}
}
// If the flag value is 1
// the sorting is not possible
if (flag == 1)
cout << "-1" << endl;
else {
// Printing the required number
// of steps
cout << ans.size() << endl;
// Printing the indices involved
// in the shifting
for (int i = 0; i < ans.size(); i++) {
cout << ans[i][0]
<< " " << ans[i][1]
<< " " << ans[i][2]
<< endl;
}
}
}
}
// Driver code
int main()
{
int n;
vector<int> A{ 0, 8, 9, 10, 1, 7, 12,
4, 3, 2, 6, 5, 11 };
n = A.size();
// Calling the sorting function
sortbyorder3(A, n);
return 0;
}
6 11 5 7 11 4 1 11 8 3 11 10 6 2 11 9 11 9 12
Complejidad de tiempo: O(N) , donde N es el tamaño de la array.
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sanskarseth y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA