Ordenar una array en función de la diferencia absoluta de elementos adyacentes

Dada una array arr[] que contiene N enteros, la tarea es reorganizar todos los elementos de la array de manera que la diferencia absoluta entre los elementos consecutivos de la array se clasifique en orden creciente.
Ejemplos 
 

Entrada: arr[] = { 5, -2, 4, 8, 6, 5 } 
Salida: 5 5 6 4 8 -2 
Explicación: 
|5 – 5| = 0 
|5 – 6| = 1 
|6 – 4| = 2 
|4 – 8| = 4 
|8 – (-2)| = 10 
Por lo tanto, se ordenan las diferencias entre elementos adyacentes.
Entrada: arr[] = { 8, 1, 4, 2 } 
Salida: 4 2 8 1 
Explicación: 
|2 – 4| = 2 
|8 – 2| = 6 
|1 – 8| = 7 
Por lo tanto, se ordenan las diferencias entre elementos adyacentes. 
 

Enfoque: el problema se puede resolver utilizando el enfoque codicioso . Sabemos que la diferencia máxima está entre los elementos mínimo y máximo de la array . Usando este hecho, si incluimos uno de los elementos mínimos en la respuesta, entonces el siguiente elemento incluido en la array de respuesta será el elemento máximo, luego el tercer elemento incluido será el segundo mínimo, luego el cuarto elemento incluido será el segundo máximo y así sucesivamente dará la array deseada. 
A continuación se muestran los pasos: 
 

1. Ordene la array dada arr[] en orden creciente.
2. Elija el primer elemento máximo (digamos a ) y mínimo (digamos b ) de la array ordenada e insértelo en la array de respuesta (digamos ans[] ) como {a, b}.
3. Repita los pasos anteriores eligiendo el segundo, tercero, cuarto… elemento máximo y mínimo de la array ordenada e insértelo al frente de la array de respuesta.
4. Después de todas las operaciones anteriores, la array de respuesta tiene el resultado deseado.

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

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that arrange the array such that
// all absolute difference between adjacent
// element are sorted
void sortedAdjacentDifferences(int arr[], int n)
{
    // To store the resultant array
    int ans[n];
 
    // Sorting the given array
    // in ascending order
    sort(arr + 0, arr + n);
 
    // Variable to represent left and right
    // ends of the given array
    int l = 0, r = n - 1;
 
    // Traversing the answer array in reverse
    // order and arrange the array elements from
    // arr[] in reverse order
    for (int i = n - 1; i >= 0; i--) {
 
        // Inserting elements in zig-zag manner
        if (i % 2) {
            ans[i] = arr[l];
            l++;
        }
        else {
            ans[i] = arr[r];
            r--;
        }
    }
 
    // Displaying the resultant array
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 5, -2, 4, 8, 6, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    sortedAdjacentDifferences(arr, n);
    return 0;
}

// Java implementation of the above approach
import java.util.*;
 
class GFG{
  
// Function that arrange the array such that
// all absolute difference between adjacent
// element are sorted
static void sortedAdjacentDifferences(int arr[], int n)
{
    // To store the resultant array
    int []ans = new int[n];
  
    // Sorting the given array
    // in ascending order
    Arrays.sort(arr);
  
    // Variable to represent left and right
    // ends of the given array
    int l = 0, r = n - 1;
  
    // Traversing the answer array in reverse
    // order and arrange the array elements from
    // arr[] in reverse order
    for (int i = n - 1; i >= 0; i--) {
  
        // Inserting elements in zig-zag manner
        if (i % 2 == 1) {
            ans[i] = arr[l];
            l++;
        }
        else {
            ans[i] = arr[r];
            r--;
        }
    }
  
    // Displaying the resultant array
    for (int i = 0; i < n; i++) {
        System.out.print(ans[i]+ " ");
    }
}
  
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 5, -2, 4, 8, 6, 4, 5 };
    int n = arr.length;
  
    // Function Call
    sortedAdjacentDifferences(arr, n);
}
}
 
// This code is contributed by Princi Singh

# Python3 implementation of the above approach
 
# Function that arrange the array such that
# all absolute difference between adjacent
# element are sorted
def sortedAdjacentDifferences(arr, n):
     
    # To store the resultant array
    ans = [0]*n
 
    # Sorting the given array
    # in ascending order
    arr = sorted(arr)
 
    # Variable to represent left and right
    # ends of the given array
    l = 0
    r = n - 1
 
    # Traversing the answer array in reverse
    # order and arrange the array elements from
    # arr[] in reverse order
    for i in range(n - 1, -1, -1):
 
        # Inserting elements in zig-zag manner
        if (i % 2):
            ans[i] = arr[l]
            l += 1
        else:
            ans[i] = arr[r]
            r -= 1
 
    # Displaying the resultant array
    for i in range(n):
        print(ans[i], end=" ")
 
# Driver Code
if __name__ == '__main__':
    arr=[5, -2, 4, 8, 6, 4, 5]
    n = len(arr)
 
    # Function Call
    sortedAdjacentDifferences(arr, n)
     
# This code is contributed by mohit kumar 29

// C# implementation of the above approach
using System;
 
class GFG
{
    // Function that arrange the array such that
    // all absolute difference between adjacent
    // element are sorted
    static void sortedAdjacentDifferences(int[] arr, int n)
    {
        // To store the resultant array
        int[] ans = new int[n];
      
        // Sorting the given array
        // in ascending order
        Array.Sort(arr);
      
        // Variable to represent left and right
        // ends of the given array
        int l = 0, r = n - 1;
      
        // Traversing the answer array in reverse
        // order and arrange the array elements from
        // arr[] in reverse order
        for (int i = n - 1; i >= 0; i--) {
      
            // Inserting elements in zig-zag manner
            if (i % 2 != 0) {
                ans[i] = arr[l];
                l++;
            }
            else {
                ans[i] = arr[r];
                r--;
            }
        }
      
        // Displaying the resultant array
        for (int i = 0; i < n; i++) {
            Console.Write(ans[i] + " ");
        }
    }
      
    // Driver Code
    public static void Main()
    {
        int[] arr = { 5, -2, 4, 8, 6, 4, 5 };
        int n = arr.Length;
      
        // Function Call
        sortedAdjacentDifferences(arr, n);
    }
}
 
// This code is contributed by chitranayal

<script>
 
// JavaScript implementation of the above approach
 
// Function that arrange the array such that
// all absolute difference between adjacent
// element are sorted
function sortedAdjacentDifferences(arr, n)
{
    // To store the resultant array
    let ans = new Array(n);
 
    // Sorting the given array
    // in ascending order
    arr.sort();
 
    // Variable to represent left and right
    // ends of the given array
    let l = 0, r = n - 1;
 
    // Traversing the answer array in reverse
    // order and arrange the array elements from
    // arr[] in reverse order
    for (let i = n - 1; i >= 0; i--) {
 
        // Inserting elements in zig-zag manner
        if (i % 2) {
            ans[i] = arr[l];
            l++;
        }
        else {
            ans[i] = arr[r];
            r--;
        }
    }
 
    // Displaying the resultant array
    for (let i = 0; i < n; i++) {
        document.write(ans[i] + " ");
    }
}
 
// Driver Code
    let arr = [ 5, -2, 4, 8, 6, 4, 5 ];
    let n = arr.length;
 
    // Function Call
    sortedAdjacentDifferences(arr, n);
 
</script>

5 4 5 4 6 -2 8

Complejidad de tiempo: O(N*log N), donde N es el número de elementos en la array dada.