A simple algorithm- iterate over the array and comparing consecutive elements as in bubble sort and swapping if the required condition is violated.
In case elements are repeated, swap the one with the next distinct number.
Should run in $O(n)$.
import java.io.*;
public class Zigzag{
int findg(Integer[] array, int el, int index){
int i = index;
while((i < array.length) && (array[i] == el))
i++;
if(i < array.length)
return i;
i = 0;
while(array[i] == el)
i++;
return i;
}
void rearrange(Integer[] array) {
for(int i = 0; i< array.length-1; i++)
{
if(array[i] == array[i+1])
{
int ind = findg(array, array[i], i+2);
if(array[ind] > array[i])
{
array[i%2 == 0? i: i+1] = array[ind];
array[ind] = array[i%2 == 0? i+1: i];
}
else{
array[i%2 == 1? i: i+1] = array[ind];
array[ind] = array[i%2 == 1? i+1: i];
}
}
else if(((array[i] < array[i+1]? 1: 0) ^ (i%2)) > 0)
{
int tmp = array[i];
array[i] = array[i+1];
array[i+1] = tmp;
}
}
}
void printArray(Integer[] array){
for(int i = 0; i < array.length; i++)
{
System.out.print(array[i]+" ");
}
}
public static void main(String args[]) {
Zigzag myArray = new Zigzag(); //Initialize class
Integer[] array = new Integer[args.length];
int i = 0;
for(String word:args)
array[i++]=Integer.parseInt(word);
myArray.rearrange(array);
myArray.printArray(array);
}
}