Organice la array de manera que al realizar las operaciones dadas se obtenga un orden creciente

Dada una array arr[] de tamaño N , la tarea es imprimir la disposición de la array de modo que al realizar las siguientes operaciones en esta disposición, se obtenga un orden creciente como salida:  

1. Tome el primer elemento (índice 0 ), ^elimínelo de la array e imprímalo.
2. Si aún quedan elementos en la array, mueva el siguiente elemento superior al final de la array.
3. Repita los pasos anteriores hasta que la array no esté vacía.

Ejemplos: 

Entrada: arr = {1, 2, 3, 4, 5, 6, 7, 8} 
Salida: {1, 5, 2, 7, 3, 6, 4, 8} 
Explicación: 
Sea la array inicial {1, 5 , 2, 7, 3, 6, 4, 8}, donde 1 es la parte superior de la array. 
Se imprime 1 y se mueve 5 al final. La array ahora es {2, 7, 3, 6, 4, 8, 5}. 
Se imprime 2 y se mueve 7 al final. La array ahora es {3, 6, 4, 8, 5, 7}. 
Se imprime 3 y se mueve 6 al final. La array ahora es {4, 8, 5, 7, 6}. 
Se imprime 4 y se mueve 8 al final. La array ahora es {5, 7, 6, 8}. 
Se imprime 5 y se mueve 7 al final. La array ahora es {6, 8, 7}. 
Se imprime 6 y se mueve 8 al final. La array ahora es {7, 8}. 
Se imprime 7 y se mueve 8 al final. La array ahora es {8}. 
8 está impreso. 
El orden de impresión es 1, 2, 3, 4, 5, 6, 7, 8 que va en aumento.
Entrada: arr = {3, 2, 25, 2, 3, 1, 2, 6, 5, 45, 4, 89, 5} 
Salida: {1, 45, 2, 5, 2, 25, 2, 5, 3, 89, 3, 6, 4} 

Enfoque: 
La idea es simular el proceso dado. Para esto se utiliza   una estructura de datos de cola .

1. La array dada se ordena y la cola se prepara agregando índices de array.
2. Luego, se recorre la array dada y, para cada elemento, se extrae el índice del frente de la cola y se agrega el elemento de array actual en el índice emergente en la array resultante.
3. Si la cola aún no está vacía, el siguiente índice (en el frente de la cola) se mueve al final de la cola.

A continuación se muestra la implementación del enfoque anterior:  

#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
 
// Function to print the arrangement
vector<int> arrangement(vector<int> arr)
{
    // Sorting the list
    sort(arr.begin(), arr.end());
 
    // Finding Length of the List
    int length = arr.size();
 
    // Initializing the result array
    vector<int> ans(length, 0);
 
    // Initializing the Queue
    deque<int> Q;
    for (int i = 0; i < length; i++)
        Q.push_back(i);
 
    // Adding current array element to the
    // result at an index which is at the
    // front of the Q and then if still
    // elements are left then putting the next
    // top element the bottom of the array.
    for (int i = 0; i < length; i++)
    {
        int j = Q.front();
        Q.pop_front();
        ans[j] = arr[i];
 
        if (Q.size() != 0)
        {
            j = Q.front();
            Q.pop_front();
            Q.push_back(j);
        }
    }
    return ans;
}
 
// Driver code
int main()
{
    vector<int> arr = { 1, 2, 3, 4, 5, 6, 7, 8 };
 
    vector<int> answer = arrangement(arr);
 
    for (int i : answer)
        cout << i << " ";
}
 
// This code is contributed by mohit kumar 29

// Java implementation of the above approach
 
import java.util.*;
 
public class GfG
{
 
    // Function to find the array
    // arrangement
    static public int[] arrayIncreasing(int[] arr)
    {
 
        // Sorting the array
        Arrays.sort(arr);
 
        // Finding size of array
        int length = arr.length;
 
        // Empty array to store resultant order
        int answer[] = new int[length];
 
        // Doubly Ended Queue to
        // simulate the process
        Deque<Integer> dq = new LinkedList<>();
 
        // Loop to initialize queue with indexes
        for (int i = 0; i < length; i++) {
            dq.add(i);
        }
 
        // Adding current array element to the
        // result at an index which is at the
        // front of the queue and then if still
        // elements are left then putting the next
        // top element the bottom of the array.
        for (int i = 0; i < length; i++)
        {
 
            answer[dq.pollFirst()] = arr[i];
 
            if (!dq.isEmpty())
                dq.addLast(dq.pollFirst());
        }
 
        // Returning the resultant order
        return answer;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int A[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
 
        // Calling the function
        int ans[] = arrayIncreasing(A);
 
        // Printing the obtained pattern
        for (int i = 0; i < A.length; i++)
            System.out.print(ans[i] + " ");
    }
}

# Python3 Code for the approach
 
# Importing Queue from Collections Module
from collections import deque
 
# Function to print the arrangement
def arrangement(arr):
    # Sorting the list
    arr.sort()
     
    # Finding Length of the List
    length = len(arr)
     
    # Initializing the result array
    answer = [0 for x in range(len(arr))]
     
    # Initializing the Queue
    queue = deque()
    for i in range(length):
        queue.append(i)
     
    # Adding current array element to the
    # result at an index which is at the
    # front of the queue and then if still
    # elements are left then putting the next
    # top element the bottom of the array.
    for i in range(length):
     
        answer[queue.popleft()] = arr[i]
     
        if len(queue) != 0:
            queue.append(queue.popleft())
    return answer
 
# Driver code
arr = [1, 2, 3, 4, 5, 6, 7, 8]
answer = arrangement(arr)
# Printing the obtained result
print(*answer, sep = ' ')

// C# implementation of the above approach
using System;
using System.Collections.Generic;
 
class GfG
{
 
    // Function to find the array
    // arrangement
    static public int[] arrayIncreasing(int[] arr)
    {
 
        // Sorting the array
        Array.Sort(arr);
 
        // Finding size of array
        int length = arr.Length;
 
        // Empty array to store resultant order
        int []answer = new int[length];
 
        // Doubly Ended Queue to
        // simulate the process
        List<int> dq = new List<int>();
 
        // Loop to initialize queue with indexes
        for (int i = 0; i < length; i++)
        {
            dq.Add(i);
        }
 
        // Adding current array element to the
        // result at an index which is at the
        // front of the queue and then if still
        // elements are left then putting the next
        // top element the bottom of the array.
        for (int i = 0; i < length; i++)
        {
 
            answer[dq[0]] = arr[i];
            dq.RemoveAt(0);
            if (dq.Count != 0)
            {
                dq.Add(dq[0]);
                dq.RemoveAt(0);
            }
        }
 
        // Returning the resultant order
        return answer;
    }
 
    // Driver code
    public static void Main(String []args)
    {
        int []A = { 1, 2, 3, 4, 5, 6, 7, 8 };
 
        // Calling the function
        int []ans = arrayIncreasing(A);
 
        // Printing the obtained pattern
        for (int i = 0; i < A.Length; i++)
            Console.Write(ans[i] + " ");
    }
}
 
// This code is contributed by 29AjayKumar

<script>
    // Javascript implementation of the above approach
     
    // Function to find the array
    // arrangement
    function arrayIncreasing(arr)
    {
  
        // Sorting the array
        arr.sort(function(a, b){return a - b});
  
        // Finding size of array
        let length = arr.length;
  
        // Empty array to store resultant order
        let answer = new Array(length);
  
        // Doubly Ended Queue to
        // simulate the process
        let dq = [];
  
        // Loop to initialize queue with indexes
        for (let i = 0; i < length; i++)
        {
            dq.push(i);
        }
  
        // Adding current array element to the
        // result at an index which is at the
        // front of the queue and then if still
        // elements are left then putting the next
        // top element the bottom of the array.
        for (let i = 0; i < length; i++)
        {
  
            answer[dq[0]] = arr[i];
            dq.shift();
            if (dq.length != 0)
            {
                dq.push(dq[0]);
                dq.shift(0);
            }
        }
  
        // Returning the resultant order
        return answer;
    }
     
    let A = [ 1, 2, 3, 4, 5, 6, 7, 8 ];
  
    // Calling the function
    let ans = arrayIncreasing(A);
 
    // Printing the obtained pattern
    for (let i = 0; i < A.length; i++)
      document.write(ans[i] + " ");
       
      // This code is contributed by decode2207.
</script>

1 5 2 7 3 6 4 8

Complejidad de tiempo: O(NlogN)
Otro enfoque: 

Si lo observa de cerca , encontrará que aquí está siguiendo un patrón.

Solo piensa al revés.

• Ordene la array de entrada e intente llegar a la etapa anterior de los pasos dados.
• Iterar de i=N-1 a 1, disminuyendo i en 1 en cada paso.
• Elimine el último elemento de una array e insértelo en la i-ésima posición.
• Repita los dos pasos anteriores hasta llegar a i = 1
• Después de llegar a i=1, obtendrá la array resultante final.

A continuación se muestra la implementación del enfoque anterior:

// C++ program to find the desired output
// after performing given operations
 
#include <bits/stdc++.h>
using namespace std;
// Function to arrange array in such a way
// that after performing given operation
// We get increasing sorted array
 
void Desired_Array(vector<int>& v)
{
    // Size of given array
    int n = v.size();
 
    // Sort the given array
    sort(v.begin(), v.end());
 
    // Start erasing last element and place it at
    // ith index
    int i = n - 1;
    // While we reach at starting
 
    while (i > 0) {
        // Store last element
        int p = v[n - 1];
 
        // Shift all elements by 1 position in right
        for (int j = n - 1; j >= i; j--)
        {
            v[j + 1] = v[j];
        }
 
        // insert last element at ith position
        v[i] = p;
        i--;
    }
 
    // print desired Array
    for (auto x : v)
        cout << x << " ";
    cout << "\n";
}
 
// Driver Code
int main()
{
 
    // Given Array
    vector<int> v = { 1, 2, 3, 4, 5 };
    Desired_Array(v);
 
    vector<int> v1 = { 1, 12, 2, 10, 4, 16, 6 };
    Desired_Array(v1);
    return 0;
}
 
// Contributed by ajaykr00kj

// Java program to find the
// desired output after
// performing given operations
import java.util.Arrays;
class Main{
     
// Function to arrange array in
// such a way that after performing
// given operation We get increasing
// sorted array
public static void Desired_Array(int v[])
{
  // Size of given array
  int n = v.length;
 
  // Sort the given array
  Arrays.sort(v);
 
  // Start erasing last element
  // and place it at ith index
  int i = n - 1;
   
  // While we reach at starting
  while (i > 0)
  {
    // Store last element
    int p = v[n - 1];
 
    // Shift all elements by
    // 1 position in right
    for (int j = n - 1;
             j >= i; j--)
    {
      v[j] = v[j - 1];
    }
 
    // insert last element at
    // ith position
    v[i] = p;
    i--;
  }
 
  // Print desired Array
  for(int x = 0; x < v.length; x++)
  {
    System.out.print(v[x] + " ");
  }
 
  System.out.println();
}
 
// Driver code   
public static void main(String[] args)
{
  // Given Array
  int v[] = {1, 2, 3, 4, 5};
  Desired_Array(v);
 
  int v1[] = {1, 12, 2, 10, 4, 16, 6};
  Desired_Array(v1);
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program to find the desired output
# after performing given operations
 
# Function to arrange array in such a way
# that after performing given operation
# We get increasing sorted array
def Desired_Array(v):
 
    # Size of given array
    n = len(v)
 
    # Sort the given array
    v.sort()
 
    # Start erasing last element and place it at
    # ith index
    i = n - 1
    # While we reach at starting
 
    while (i > 0) :
        # Store last element
        p = v[n - 1]
 
        # Shift all elements by 1 position in right
        for j in range(n-1, i - 1, -1) :
         
            v[j] = v[j - 1]
 
        # insert last element at ith position
        v[i] = p
        i -= 1
     
    # print desired Array
    for x in v :
        print(x, end = " ")
    print()
 
 
# Given Array
v = [ 1, 2, 3, 4, 5 ]
Desired_Array(v)
 
v1 = [ 1, 12, 2, 10, 4, 16, 6 ]
Desired_Array(v1)
 
# This code is contributed by divyesh072019

// C# program to find the desired
// output after performing given
// operations
using System;
  
class GFG{
     
// Function to arrange array in
// such a way that after performing
// given operation We get increasing
// sorted array
public static void Desired_Array(int[] v)
{
     
    // Size of given array
    int n = v.Length;
     
    // Sort the given array
    Array.Sort(v);
     
    // Start erasing last element
    // and place it at ith index
    int i = n - 1;
     
    // While we reach at starting
    while (i > 0)
    {
         
        // Store last element
        int p = v[n - 1];
         
        // Shift all elements by
        // 1 position in right
        for(int j = n - 1;
                j >= i; j--)
        {
            v[j] = v[j - 1];
        }
         
        // Insert last element at
        // ith position
        v[i] = p;
        i--;
    }
     
    // Print desired Array
    for(int x = 0; x < v.Length; x++)
    {
        Console.Write(v[x] + " ");
    }
     
    Console.WriteLine();
}
  
// Driver code       
static public void Main()
{
     
    // Given Array
    int[] v = { 1, 2, 3, 4, 5 };
    Desired_Array(v);
     
    int[] v1 = { 1, 12, 2, 10, 4, 16, 6 };
    Desired_Array(v1);
}
}
 
// This code is contributed by offbeat

<script>
 
    // Javascript program to find the desired
    // output after performing given
    // operations
     
    // Function to arrange array in
    // such a way that after performing
    // given operation We get increasing
    // sorted array
    function Desired_Array(v)
    {
 
        // Size of given array
        let n = v.length;
 
        // Sort the given array
        v.sort(function(a, b){return a - b});
 
        // Start erasing last element
        // and place it at ith index
        let i = n - 1;
 
        // While we reach at starting
        while (i > 0)
        {
 
            // Store last element
            let p = v[n - 1];
 
            // Shift all elements by
            // 1 position in right
            for(let j = n - 1; j >= i; j--)
            {
                v[j] = v[j - 1];
            }
 
            // Insert last element at
            // ith position
            v[i] = p;
            i--;
        }
 
        // Print desired Array
        for(let x = 0; x < v.length; x++)
        {
            document.write(v[x] + " ");
        }
 
        document.write("</br>");
    }
       
    // Given Array
    let v = [ 1, 2, 3, 4, 5 ];
    Desired_Array(v);
      
    let v1 = [ 1, 12, 2, 10, 4, 16, 6 ];
    Desired_Array(v1);
         
</script>

1 5 2 4 3 
1 12 2 10 4 16 6

Tiempo Complejidad: O(n ² )
Espacio Auxiliar: O(1)