Programa de Python 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:

# Python program to sort an array 
# in Zig-Zag form 
  
# Program for zig-zag conversion 
# of array 
def zigZag(arr, n): 
  
    # Flag true indicates relation "<" 
    # is expected, else ">" is expected. 
    # The first expected relation is "<" 
    flag = True
  
    for i in range(n - 1): 
  
        # "<" relation expected 
        if flag is True: 
  
            # 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]: 
                arr[i], arr[i + 1] = arr[i + 1], arr[i] 
  
            # ">" 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]: 
                arr[i], arr[i + 1] = arr[i + 1], arr[i] 
        flag = bool(1 - flag) 
    print(arr) 
  
# Driver code
arr = [4, 3, 7, 8, 6, 2, 1] 
n = len(arr) 
zigZag(arr, n) 
# This code is contributed by Pratik Chhajer 

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!