Dada una array K-creciente-decreciente arr[] , la tarea es ordenar la array dada. Se dice que una array es K-creciente-decreciente si los elementos aumentan repetidamente hasta un cierto índice después del cual disminuyen y luego aumentan nuevamente, un total de K veces. El siguiente diagrama muestra una array de 4 crecientes y decrecientes.
Ejemplo:
Entrada: arr[] = {57, 131, 493, 294, 221, 339, 418, 458, 442, 190}
Salida: 57 131 190 221 294 339 418 442 458 493
Entrada: arr[] = {1, 2, 3, 4, 3, 2, 1}
Salida: 1 1 2 2 3 3 4
Enfoque: El enfoque de fuerza bruta consiste en ordenar la array sin aprovechar la propiedad k-creciente-decreciente. La complejidad temporal de este enfoque es O(n logn) donde n es la longitud de la array.
Si k es significativamente menor que n, se puede encontrar un mejor enfoque con menos complejidad de tiempo. Por ejemplo, si k=2, la array de entrada consta de dos subarreglos, uno creciente y otro decreciente. Al invertir el segundo subarreglo, se obtienen dos arreglos ordenados y el resultado se fusiona, lo que se puede hacer en tiempo O(n). Generalizando, primero podríamos invertir el orden de cada uno de los subarreglos decrecientes. Por ejemplo, en la figura anterior, la array podría descomponerse en cuatro arrays ordenadas como {57, 131, 493}, {221, 294}, {339, 418, 458} y {190, 442}. Ahora, la técnica del montón mínimo se puede utilizar para fusionar estas arrays ordenadas .
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// A pair of pairs, first element is going to
// store value, second element index of array
// and third element index in the array
typedef pair<int, pair<int, int> > ppi;
// This function takes an array of arrays as an
// argument and all arrays are assumed to be
// sorted
// It merges them together and returns the
// final sorted output
vector<int> mergeKArrays(vector<vector<int> > arr)
{
vector<int> output;
// Create a min heap with k heap nodes
// Every heap node has first element of an array
priority_queue<ppi, vector<ppi>, greater<ppi> > pq;
for (int i = 0; i < arr.size(); i++)
pq.push({ arr[i][0], { i, 0 } });
// Now one by one get the minimum element
// from min heap and replace it with next
// element of its array
while (pq.empty() == false) {
ppi curr = pq.top();
pq.pop();
// i ==> Array Number
// j ==> Index in the array number
int i = curr.second.first;
int j = curr.second.second;
output.push_back(curr.first);
// The next element belongs to same array as
// current
if (j + 1 < arr[i].size())
pq.push({ arr[i][j + 1], { i, j + 1 } });
}
return output;
}
// Function to sort the alternating
// increasing-decreasing array
vector<int> SortKIncDec(const vector<int>& A)
{
// Decompose the array into a
// set of sorted arrays
vector<vector<int> > sorted_subarrays;
typedef enum { INCREASING,
DECREASING } SubarrayType;
SubarrayType subarray_type = INCREASING;
int start_idx = 0;
for (int i = 0; i <= A.size(); i++) {
// If the current subarrays ends here
if (i == A.size()
|| (i>0 && A[i - 1] < A[i]
&& subarray_type == DECREASING)
|| (i>0 && A[i - 1] >= A[i]
&& subarray_type == INCREASING)) {
// If the subarray is increasing
// then add from the start
if (subarray_type == INCREASING) {
sorted_subarrays.emplace_back(A.cbegin() + start_idx,
A.cbegin() + i);
}
// If the subarray is decreasing
// then add from the end
else {
sorted_subarrays.emplace_back(A.crbegin()
+ A.size() - i,
A.crbegin()
+ A.size()
- start_idx);
}
start_idx = i;
subarray_type = (subarray_type == INCREASING
? DECREASING
: INCREASING);
}
}
// Merge the k sorted arrays`
return mergeKArrays(sorted_subarrays);
}
// Driver code
int main()
{
vector<int> arr = { 57, 131, 493, 294, 221,
339, 418, 458, 442, 190 };
// Get the sorted array
vector<int> ans = SortKIncDec(arr);
// Print the sorted array
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
return 0;
}
57 131 190 221 294 339 418 442 458 493
Complejidad de tiempo: O(n*logk), donde n es la longitud de la array.