Convierta la 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:

// C++ program to sort an array in Zig-Zag form
#include <iostream>
using namespace std;
 
// Program for zig-zag conversion of array
void zigZag(int arr[], int n)
{
    // Flag true indicates relation "<" is expected,
    // else ">" is expected. The first expected relation
    // is "<"
    bool flag = true;
 
    for (int i = 0; i <= n - 2; i++) {
        if (flag) /* "<" relation expected */
        {
            /* 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(arr[i], arr[i + 1]);
        }
        else /* ">" relation expected */
        {
            /* 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(arr[i], arr[i + 1]);
        }
        flag = !flag; /* flip flag */
    }
}
 
// Driver program
int main()
{
    int arr[] = { 4, 3, 7, 8, 6, 2, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    zigZag(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta (kriSania804)

// C program to sort an array in Zig-Zag form
#include <stdbool.h>
#include <stdio.h>
 
// This function swaps values pointed by xp and yp
void swap(int* xp, int* yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
 
// Program for zig-zag conversion of array
void zigZag(int arr[], int n)
{
    // Flag true indicates relation "<" is expected,
    // else ">" is expected. The first expected relation
    // is "<"
    bool flag = true;
 
    for (int i = 0; i <= n - 2; i++) {
        if (flag) /* "<" relation expected */
        {
            /* 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(&arr[i], &arr[i + 1]);
        }
        else /* ">" relation expected */
        {
            /* 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(&arr[i], &arr[i + 1]);
        }
        flag = !flag; /* flip flag */
    }
}
 
// Driver program
int main()
{
    int arr[] = { 4, 3, 7, 8, 6, 2, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    zigZag(arr, n);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta (kriSania804)

// 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++)
        {
            if (flag) /* "<" relation expected */
            {
                /* 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;
                }
                 
            }
            else /* ">" relation expected */
            {
                /* 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;
                }
            }
            flag = !flag; /* flip flag */
        }
    }
     
    // Driver method to test the above function
    public static void main(String[] args)
    {
        zigZag();
        System.out.println(Arrays.toString(arr));
    }
}

# 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 > C < B
            # 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 program
arr = [4, 3, 7, 8, 6, 2, 1]
n = len(arr)
zigZag(arr, n)
 
# This code is contributed by Pratik Chhajer
# This code was improved by Hardik Jain

// C# program to sort an array in Zig-Zag form
using System;
 
class GFG{
     
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 "<"
    bool 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 > 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;
            }
        }
         
        // ">" 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();
    foreach(int i in arr)
        Console.Write(i + " ");
}
}
 
// This code is contributed by amal kumar choubey

<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 > 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;
        }
         
        // ">" 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>

3 7 4 8 2 6 1 

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

Otro enfoque:
dado que la relación necesaria es a<b>c<d>e<f, significa que los elementos de posición impar tienen que ser mayores que sus adyacentes , es decir, los elementos de posición par. Simplemente recorra la array en las posiciones impares y verifique si es mayor que sus elementos adyacentes, si no lo es, cámbielos.

Siga los pasos a continuación para implementar la idea anterior:

// C++ program to sort an array in Zig-Zag form
#include <iostream>
using namespace std;
 
// Program for zig-zag conversion of array
void zigZag(int a[], int n)
{
    for (int i = 1; i < n; i += 2)
    {
       
        // Check if previous element
        // is greater than the current element
        // then swap them
        if (a[i - 1] > a[i])
            swap(a[i], a[i - 1]);
 
        // if next element is greater than
        // then the current element then
        // also swap them.
        if (i + 1 < n && (a[i + 1] > a[i]))
            swap(a[i], a[i + 1]);
    }
}
 
// Driver program
int main()
{
    int arr[] = { 4, 3, 7, 8, 6, 2, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    zigZag(arr, n);
    cout << "[ ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << "]";
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// C program to sort an array in Zig-Zag form
#include <stdio.h>
 
// This function swaps values pointed by xp and yp
void swap(int* xp, int* yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
 
// Program for zig-zag conversion of array
void zigZag(int a[], int n)
{
    for (int i = 1; i < n; i += 2) {
 
        // Check if previous element
        // is greater than the current element
        // then swap them
        if (a[i - 1] > a[i])
            swap(&a[i], &a[i - 1]);
 
        // if next element is greater than
        // then the current element then
        // also swap them.
        if (i + 1 < n && (a[i + 1] > a[i]))
            swap(&a[i], &a[i + 1]);
    }
}
 
// Driver program
int main()
{
    int arr[] = { 4, 3, 7, 8, 6, 2, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    zigZag(arr, n);
    printf("[ ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("]");
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.*;
class GFG {
 
    // Method for zig-zag conversion of array
    static void swap(int a[], int i, int j)
    {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
 
    static void zigZag(int a[], int n)
    {
        for (int i = 1; i < n; i += 2) {
            // Check if previous element
           // is greater than the current element
           // then swap them
            if (a[i - 1] > a[i])
                swap(a, i, i - 1);
           
            // if next element is greater than
            // then the current element then
            // also swap them.
            if (i + 1 < n && (a[i + 1] > a[i]))
                swap(a, i, i + 1);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int a[] = new int[] { 4, 3, 7, 8, 6, 2, 1 };
        zigZag(a, a.length);
        System.out.println(Arrays.toString(a));
    }
}

# Method for zig-zag conversion of array
def swap(a, i, j):
    temp = a[i]
    a[i] = a[j]
    a[j] = temp
 
 
def zigZag(a, n):
    for i in range(1, n, 2):
        # Check if previous element
        # is greater than the current element
        # then swap them
        if (a[i - 1] > a[i]):
            swap(a, i, i - 1)
 
        # if next element is greater than
        # then the current element then
        # also swap them.
        if (i + 1 < n and (a[i + 1] > a[i])):
            swap(a, i, i + 1)
 
 
# Driver Code
if __name__ == "__main__":
    a = [4, 3, 7, 8, 6, 2, 1]
    zigZag(a, len(a))
    print(a)

// C# program to sort an array in Zig-Zag form
using System;
using System.Linq;
 
using System.Collections;
 
public class GFG {
    // Method for zig-zag conversion of array
    public static void swap(int[] a, int i, int j)
    {
        var temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    public static void zigZag(int[] a, int n)
    {
        for (int i = 1; i < n; i += 2) {
            // Check if previous element
            // is greater than the current element
            // then swap them
            if (a[i - 1] > a[i]) {
                GFG.swap(a, i, i - 1);
            }
            // if next element is greater than
            // then the current element then
            // also swap them.
            if (i + 1 < n && (a[i + 1] > a[i])) {
                GFG.swap(a, i, i + 1);
            }
        }
    }
    // Driver Code
    public static void Main(String[] args)
    {
        int[] a = new int[] { 4, 3, 7, 8, 6, 2, 1 };
        GFG.zigZag(a, a.Length);
        Console.Write("[ ");
        for (int i = 0; i < a.Length; i++)
            Console.Write(a[i] + " ");
        Console.Write("]");
    }
}
 
// This code is contributed by Aarti_Rathi

[3, 7, 4, 8, 2, 6, 1]

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

Este artículo es una contribución de Siva Krishna Aleti . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.