Ordene la array de manera que la diferencia absoluta de los elementos adyacentes esté en orden creciente

Dada una array no ordenada de longitud N. La tarea es ordenar la array, tal que abs(a[i]-a[i+1]) < = abs(a[i+1]-a[i+2]) para todo 0 < = i< N que es abs(a[0]-a[1]) < = abs(a[1]-a[2]) < = abs(a[2]-a[3]) y así.
Ejemplos:
 

Input:  arr[] = {7, 4, 9, 9, -1, 9}
Output:  {9, 7, 9, 4, 9, -1}
Explanation:
For first two elements the difference is abs(9-7)=2
For next two elements the difference is abs(7-9)=2
For next two elements the difference is abs(9-4)=5
For next two elements the difference is abs(7-4)=3
For next two elements the difference is abs(4-(-1))=5
Hence, difference array is 0, 0, 2, 3, 5.

Input: arr[] = {1, 4, 6, 7} 
Output: {6, 4, 7, 1} 
Explanation:
For first two elements the difference is abs(6-4)=2
For next two elements the difference is abs(4-7)=3
For next two elements the difference is abs(7-1)=6
Hence, difference array is 2, 3, 6.

Enfoque: 
para resolver el problema mencionado anteriormente, ordenamos la array no ordenada dada en orden ascendente. Luego ejecute un ciclo desde i = 1 a i < n/2 y empuje los elementos alternativamente en una pila desde la primera mitad y la segunda mitad respectivamente, es decir, presione a[i] una vez y a[ni-1] una vez hasta que todos los elementos de la array ser empujado a la pila. 
La observación principal del problema es verificar si la longitud de la array dada es impar, luego empujar el elemento en el índice n/2 adicionalmente para tener todos los elementos de la array en la pila. Luego recorra toda la pila hasta que la pila no esté vacía, extraiga los elementos de la pila e imprímalos como resultado.
A continuación se muestra la implementación del enfoque discutido: 
 

// C++ implementation to Sort a given
// unsorted array of length n
// according to the given condition
#include <bits/stdc++.h>
using namespace std;
 
// Function
void solve(int a[], int n)
{
 
    // sort the array in ascending order
    sort(a, a + n);
 
    // declare a stack data structure
    stack<int> st;
 
    // run a loop from i=0 to i<n/2 and
    // push elements alternatively to stack
    for (int i = 0; i < n / 2; i++) {
 
        // push elements from
        // first half of array
        st.push(a[i]);
 
        // push elements from
        // second half of the array
        st.push(a[n - i - 1]);
    }
 
    // check if array has odd length,
    // then push a[n/2] to the stack
    if (n % 2 == 1)
 
        st.push(a[n / 2]);
 
    // loop until stack is not empty)
    while (!st.empty()) {
 
        int x = st.top();
 
        printf("%d ", x);
 
        // pop the topmost
        // element from the stack
        st.pop();
    }
}
 
// Driver code
int main()
{
 
    // declaration of unsorted array
    int a[] = { 7, 4, 9, 9, -1, 9 };
 
    // given size of unsorted array
    int n = sizeof(a) / sizeof(a[0]);
 
    solve(a, n);
 
    return 0;
}

// Java implementation to Sort a given
// unsorted array of length n
// according to the given condition
import java.util.*;
class GFG{
 
// Function
static void solve(int a[], int n)
{
 
    // sort the array in ascending order
    Arrays.sort(a);
 
    // declare a stack data structure
    Stack<Integer> st = new Stack<Integer>();
 
    // run a loop from i=0 to i<n/2 and
    // push elements alternatively to stack
    for (int i = 0; i < n / 2; i++)
    {
 
        // push elements from
        // first half of array
        st.add(a[i]);
 
        // push elements from
        // second half of the array
        st.add(a[n - i - 1]);
    }
 
    // check if array has odd length,
    // then push a[n/2] to the stack
    if (n % 2 == 1)
 
        st.add(a[n / 2]);
 
    // loop until stack is not empty)
    while (!st.isEmpty())
    {
        int x = st.peek();
        System.out.printf("%d ", x);
 
        // pop the topmost
        // element from the stack
        st.pop();
    }
}
 
// Driver code
public static void main(String[] args)
{
 
    // declaration of unsorted array
    int a[] = { 7, 4, 9, 9, -1, 9 };
 
    // given size of unsorted array
    int n = a.length;
 
    solve(a, n);
}
}
 
// This code is contributed by sapnasingh4991

# Python3 implementation to sort a
# given unsorted array of length n
# according to the given condition
 
# Function
def solve(a, n):
 
    # Sort the array in ascending
    # order
    a.sort()
     
    # Declare a list used as a
    # stack data structure
    st = []
 
    # Run a loop from i=0 to i<n/2 and
    # push elements alternatively to stack
    for i in range(n // 2):
 
        # Push elements from
        # first half of array
        st.append(a[i])
 
        # Push elements from
        # second half of the array
        st.append(a[n - i - 1])
 
    # Check if array has odd length,
    # then push a[n/2] to the stack
    if(n % 2 == 1):
 
        st.append(a[n // 2])
 
    # Loop until stack is not empty
    while(st != []):
        x = st[-1]
        print(x, end = " ")
 
        # Pop the topmost element
        # from the stack
        st.pop()
 
# Driver code
if __name__ == '__main__':
 
    # Declaration of unsorted array
    a = [ 7, 4, 9, 9, -1, 9 ]
 
    # Given size of unsorted array
    n = len(a)
 
    solve(a, n)
     
# This code is contributed by Shivam Singh

// C# implementation to Sort a given
// unsorted array of length n
// according to the given condition
using System;
using System.Collections;
 
class GFG{
 
// Function
static void solve(int[] a, int n)
{
     
    // Sort the array in ascending order
    Array.Sort(a);
 
    // Declare a stack data structure
    Stack st = new Stack();
 
    // Run a loop from i=0 to i<n/2 and
    // push elements alternatively to stack
    for(int i = 0; i < n / 2; i++)
    {
         
        // Push elements from
        // first half of array
        st.Push(a[i]);
 
        // Push elements from
        // second half of the array
        st.Push(a[n - i - 1]);
    }
 
    // Check if array has odd length,
    // then push a[n/2] to the stack
    if (n % 2 == 1)
        st.Push(a[n / 2]);
 
    // Loop until stack is not empty)
    while (st.Count != 0)
    {
        Console.Write(st.Peek() + " ");
 
        // Pop the topmost
        // element from the stack
        st.Pop();
    }
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Declaration of unsorted array
    int[] a = { 7, 4, 9, 9, -1, 9 };
 
    // Given size of unsorted array
    int n = a.Length;
 
    solve(a, n);
}
}
 
// This code is contributed by jrishabh99

<script>
    // Javascript implementation to Sort a given
    // unsorted array of length n
    // according to the given condition
     
    // Function
    function solve(a, n)
    {
 
        // Sort the array in ascending order
        a.sort(function(a, b){return a - b});
 
        // Declare a stack data structure
        let st = [];
 
        // Run a loop from i=0 to i<n/2 and
        // push elements alternatively to stack
        for(let i = 0; i < parseInt(n / 2, 10); i++)
        {
 
            // Push elements from
            // first half of array
            st.push(a[i]);
 
            // Push elements from
            // second half of the array
            st.push(a[n - i - 1]);
        }
 
        // Check if array has odd length,
        // then push a[n/2] to the stack
        if (n % 2 == 1)
            st.push(a[parseInt(n / 2, 10)]);
 
        // Loop until stack is not empty)
        while (st.length != 0)
        {
            document.write(st[st.length - 1] + " ");
 
            // Pop the topmost
            // element from the stack
            st.pop();
        }
    }
     
    // Declaration of unsorted array
    let a = [ 7, 4, 9, 9, -1, 9 ];
   
    // Given size of unsorted array
    let n = a.length;
   
    solve(a, n);
 
// This code is contributed by vaibhavrabadiya117.
</script>

9 7 9 4 9 -1