Searching for a better method for zig-zag array

Question

A zig-zag method which takes an array as argument and returns a zig-zag array.

Example : Input 2,6,1,7,9,3 Output 9,1,7,2,6,3

The array returned must have alternative highest numbers and lowest numbers.

I can think of this method. //Pseudo code

public static int [] zig-zag(int arr[])
    {
         arr.sort();
         int returnArr[] = new int[arr.length];
         int begindex = 0, endindex = arr.length -1;
         int idx = 0;
         while(begindex<arr.length/2-1 && endindex>=arr.length/2)
         {
             returnArr[idx++] = arr[endindex];
             returnArr[idx++] = arr[begindex];
             begindex++;endindex--;
         }
         if(arr.length%2 == 1)
         reurnArr[idx] = arr[begindex];
         return returnArr;
     }

This method has a time complexity of O(nlogn) (because of the sort) and space complexity of O(n). Is there any other way/algorithm so that it can do better than O(nlogn) ? or with O(nlogn) and space complexity being O(1) ?

There's one more method with TC O(n^2) and SC O(1). But not interested in TC of O(n^2).

Answer 1

Here is an algorithm that can do it with time complexity O(nlogn) and space complexity O(1) using a linked list.

The method works for lists with duplicate values.

It is as follows:

• First, get your list, l, sorted in descending order, with the second half reversed. (Note that your sorting algorithm must work in place on a linked list, such as in place merge sort.)

  For example, with l = 2, 6, 1, 7, 9, 3, this form would be l = 9, 7, 6, 1, 2, 3. If your list was of odd length, the first half would be one element longer than the second.

  An easy way to do this would be to sort l in descending order, and then reverse the elements in the second half.

• Next, we create some temporary variables:

  Node upper = list.head; //Upper half of list pointer
  Node lower = list.get(l.length/2); //Lower half of list pointer
  Node temp = null; //Utility pointer to hold whatever we need
  
  //Let's set up our initial state
  list.get(l.length/2-1) = null; //Disconnect two halves of the list
  temp = upper.next; //Hold upper half minus head
  upper.next = lower; //First element of upper half stitched to bottom half
  
  //Note that lower would need to be at `l.length/2+1` for an odd length list
  //This also applies to list.get in the set up
  //The code could be generalized to both even and odd lenghts by using `Math.ceil`
  // or a similar function to round up instead of Java's default of rounding down
  
  zigZag(upper, lower, temp); //Call to algorithm
  

• Finally, the algorithm:

  public static void zigZag(Node upper, Node lower, Node temp){
      int i = 0; //Controls alternation
      while(temp != null){ //Until temp gets set to null by lower.next or upper.next
          if(i%2==0){ //On even iterations
              upper = temp;
              temp = lower.next;
              lower.next = upper;
          }
          else{ //On odd iterations
              lower = temp;
              temp = upper.next;
              upper.next = lower;
          }
          i++;
      }
  }
  

  Alternatively, here's the recursive version:

  public static void zigZag(Node upper, Node lower, Node temp){
      if(temp == null) // temp got set to null by lower.next or upper.next
          return;   // we're done
      upper = temp;
      temp = lower.next;
      lower.next = upper;
      zigZag(lower, upper, temp); //swap upper/lower for next cycle
  }
  

You now have a zig-zagged linked list, stored in l.

---

Finding time and space complexity:

• Sorting: time O(nlogn), space O(1)

  • Sorting takes your original time complexity and, as it sorts in place, constant space

• Reversing: time O(n), space O(1)

  • Reversing the second half of your list is O(n/2) => O(n)

• Temporaries: time O(1), space O(1)

  • Simple variable assignments of constant number and size take both constant time and space

• Algorithm: time O(n), space O(1)

  • The algorithm simply changes the next pointer of each node once, so it runs in O(n) time. It doesn't create any new variables, and thus has constant space complexity, O(1).

  • The recursive version is tail recursive, which means it can only use a single stack frame, giving it theoretically constant space complexity, O(1). (Though not in Java, as it does not support tail-recursion optimization.)

Adding it all up:

As you can see, space complexity is constant throughout, giving our overall program O(1) space usage.

Time complexity is O(nlogn)+O(n)+O(1)+O(n), which is clearly dominated by O(nlogn).

Extra reversing of your linked list because you used an ascending order sort will slow the program, but won't change the overall time complexity.

Similarly, you could come up with a sort that gives the desired form of half descending, half ascending to save some time, but it too would not change overall time complexity.

Potential for Speedup:

As mentioned by @flkes in his answer, you can reduce the time complexity of your whole program by reducing the time complexity of the sort, as it produces the dominating term.

If you found an implementation that sorted in place in O(n) time (such as this linked-list radix sort algorithm or a similar bucket sort algorithm), you could achieve total time complexity of O(n) with constant, O(1), space complexity, which is really incredibly good.

Answer 2

I would recommend implementing a radix sort first, which has a complexity of O(n). An example of that can be found here

Once you radix sort the list you can easily map it to the zigzag pattern using a container with a simple for loop. This should push the complexity to some O(n + kn) which still resolves to O(n)

Answer 3

After sorting, invert the second half of the array:
now the rest of the problem is to do a perfect shuffle of the array elements - a problem to come up time and again.
If you want to apply a permutation in-place and know how to transform indices, you can keep a "scoreboard" of indices handled - but even a single bit per item is O(n) storage. (Find the next index still needing handling and perform the cycle containing it, keeping scores, until all indices are handled.)

A pretty nice rendition of an in-place perfect shuffle in linear time and constant space in addition to the array is Aryabhata's over at CS. The method has been placed at arxiv.org by Peiyush Jain.
(The complexity of the sort as a first step may dominate the permutation/shuffle step(s).)

---

There is another interpretation of this task, or the sort step: sort into a folded array.
The sort lending itself most readily to this task got to be the double-ended selection sort:
In each pass over the data not yet placed, determine the min and max in 3/2n comparisons and swap into their positions, until one value or none at all is left.
Or take a standard sort method, and have the indexes mapped. For the hell of it:

/** Anything with accessors with int parameter */
interface Indexable<T> {
    T get(int index);
    T set(int index, T value);
//  int size(); // YAGNI?
}
/** The accessors have this folded in half,
 *   while iterator() is not overridden */
@SuppressWarnings("serial")
class FoldedList<T> extends ArrayList<T>
    implements Indexable<T> {
    public FoldedList(@SuppressWarnings("unchecked") T...elements) {
        super(Arrays.asList(elements));
    }
    int map(int index) {
        final int last = size()-1;
        index = 2*index;
        return last <= index ? 2*last-index : index+1;
    }
    @Override
    public T get(int index) { return super.get(map(index)); }
    @Override
    public T set(int index, T element) {
        return super.set(map(index), element);
    }
}

/** Sort an Indexable<T> */
public class Sort {
 // Hoare/Sedgewick using middle index for pivot
    private static <T extends Comparable<T>> 
    int split(Indexable<T> ixable, int lo, int hi) {
        int
            mid = lo + (hi-lo)/2,
            left = lo+1,
            right= hi-1;
        T pivot = ixable.get(mid),
            l = null, r = null;
        ixable.set(mid, ixable.get(lo));
    scan:
        while (true) {
            while ((l = ixable.get(left)).compareTo(pivot) < 0)
                if (right < ++left) {
                    left--;
                    break scan;
                }
            while (pivot.compareTo(r = ixable.get(right)) < 0)
                if (--right <= left) {
                    left -= 1;
                    l = ixable.get(left);
                    break scan;
                }
            ixable.set(left, r); // place misplaced items
            ixable.set(right, l);
            if (--right < ++left) {
                left = right;
                l = r;
                break;
            }
        }
        ixable.set(lo, l); // put last left value into first position 
        ixable.set(left, pivot); // place pivot at split index

        return left;
    }

    private static <T extends Comparable<T>>
    void sort(Indexable<T> ixable, int lo, int hi) {
        while (lo+2 < hi) { // more than 2 Ts
            int split = split(ixable, lo, hi);
            if (split - lo < hi - split) {
                sort(ixable, lo, split);    // left part smaller
                lo = split + 1;
            } else {
                sort(ixable, split+1, hi);  // right part smaller
                hi = split;
            }
        }
        T l, h;
        if (lo < --hi // 2 Ts
            && (l = ixable.get(lo)).compareTo(h = ixable.get(hi)) > 0) {
            ixable.set(lo, h); // exchange
            ixable.set(hi, l);
        }
    }

    public static <T extends Comparable<T>>
    void main(String[] args) {
        Indexable<Number> nums = new FoldedList<>( //2,6,1,7,9,3);
            7, 3, 9, 3, 0, 6, 1, 2, 8, 6, 5, 4, 7);
        sort((Indexable<T>) nums);
        System.out.println(nums);
    }
}