Programa Java para convertir array en forma de zig-zag

Dada una array de elementos DISTINTOS , reorganice los elementos de la array en forma de zigzag en tiempo O(n). La array convertida debe tener la forma a < b > c < d > e < f . 

Ejemplo :

Entrada : arr[] = {4, 3, 7, 8, 6, 2, 1} 
Salida : arr[] = {3, 7, 4, 8, 2, 6, 1}

Entrada : arr[] = {1, 4, 3, 2} 
Salida : arr[] = {1, 4, 2, 3}

Una solución simple es ordenar primero la array. Después de ordenar, excluya el primer elemento, intercambie los elementos restantes en pares. (es decir, mantenga arr[0] como está, intercambie arr[1] y arr[2], intercambie arr[3] y arr[4], y así sucesivamente). 
Complejidad de tiempo : O (N log N) ya que primero debemos ordenar la array.

Podemos convertir en tiempo O(n) usando un enfoque eficiente . La idea es usar una pasada modificada de tipo burbuja.

• Mantenga una bandera para representar qué orden (es decir, < o >) necesitamos actualmente.
• Si los dos elementos actuales no están en ese orden, intercambie esos elementos, de lo contrario no.

Veamos la lógica principal usando tres elementos consecutivos A, B, C.

Supongamos que estamos procesando B y C actualmente y la relación actual es ‘<‘, pero tenemos B > C. Dado que la relación actual es ‘<‘, la relación anterior debe ser ‘>’, es decir, A debe ser mayor que B. Entonces, el la relación es A > B y B > C. Podemos deducir A > C. Entonces, si intercambiamos B y C, entonces la relación es A > C y C < B. Finalmente obtenemos el orden deseado ACB 
Consulte esto para obtener más explicaciones.

La imagen de abajo es una ejecución en seco del enfoque anterior:

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

// Java program to sort an array 
// in Zig-Zag form 
import java.util.Arrays; 
  
class Test 
{ 
    static int arr[] = new int[]{4, 3, 7, 
                                 8, 6, 2, 1}; 
      
    // Method for zig-zag conversion 
    // of array 
    static void zigZag() 
    { 
        // Flag true indicates relation "<" 
        // is expected, else ">" is expected. 
        // The first expected relation is "<" 
        boolean flag = true; 
          
        int temp =0; 
      
        for (int i=0; i<=arr.length-2; i++) 
        { 
            // "<" relation expected 
            if (flag) 
            { 
                /* If we have a situation like 
                   A > B > C, we get A > B < C 
                   by swapping B and C */
                if (arr[i] > arr[i+1]) 
                { 
                    // swap 
                    temp = arr[i]; 
                    arr[i] = arr[i+1]; 
                    arr[i+1] = temp; 
                } 
                  
            } 
  
            // ">" relation expected 
            else 
            { 
                /* If we have a situation like 
                   A < B < C, we get A < C > B 
                   by swapping B and C */
                if (arr[i] < arr[i+1]) 
                { 
                    // swap 
                    temp = arr[i]; 
                    arr[i] = arr[i+1]; 
                    arr[i+1] = temp; 
                } 
            } 
  
            // flip flag 
            flag = !flag; 
        } 
    } 
      
    // Driver code
    public static void main(String[] args) 
    { 
        zigZag(); 
        System.out.println(Arrays.toString(arr)); 
    } 
} 

Producción: 

3  7  4  8  2  6  1 

Complejidad temporal: O(n) 
Espacio auxiliar: O(1) 
 

¡ Consulte el artículo completo sobre Convertir array en modo Zig-Zag para obtener más detalles!