Programa Javascript para convertir arrays en moda 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:

<script>
// JavaScript program to sort an array
// in Zig-Zag form
  
// Program for zig-zag conversion 
// of array
function zigZag(arr, n)
{    
    // Flag true indicates relation "<" 
    // is expected, else ">" is expected. 
    // The first expected relation is "<"
    let flag = true;
  
    for(let i = 0; i <= n - 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])
                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])
                 temp = arr[i]; 
                 arr[i] = arr[i + 1]; 
                 arr[i + 1] = temp; 
        }
          
        // Flip flag 
        flag = !flag; 
    }
}
  
// Driver code
let arr = [4, 3, 7, 
           8, 6, 2, 1];
let n = arr.length;
zigZag(arr, n);
  
for(let i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code is contributed by Surbhi Tyagi.
</script>

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!