alternate the order of elements of array

Question

Given an array [1, 2, 3, a, b, c], write a method to re-arrange the array such that every other elements change its place. The output should be [1, a, 2, b, 3, c].

1.Write an algorithm that works faster and uses O(1) space. 2. If you are allowed one extra-space, how much improvement to time-complexity could be achieved.

This is an interview question. There are couple of posts in SO, Interview test - rearrange the array, Reordering of array elements, Array movement from a1,..,an,b1,..,bn to a1,b1,..,an,bn and elsewhere, where various explanations are provided, but to me its not clear and concrete. I have a got a O(n^2) solution for the first question above. but it appears there is a possibility to improve it. but I really don't undersand the explanations from these posts, especially some referring to theoretical papers. It would be great if a simple pseudocode for improved time-complexity (better than O(n^2))for the first question would be great

For the second, question the time complexity could be reduced to O(n), by using one storage array. but I don't see any way to improve it further. If it is possible, I would be love to hear it.

The code for my first attempt (without using auxillary storage) is here:

import java.util.Arrays;

public class SwapHalfArrayElements {

    public static void main(String[] args){
        Object[] arr = {1,2,3,'a','b','c'};
        System.out.println("before sorting "+Arrays.toString(arr));
        rearrageArray(arr);
        System.out.println("After sorting "+ Arrays.toString(arr));
    }

    private static void swap(Object[] arr, int index1, int index2){
        Object temp=arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=temp;
    }

    private static void rearrageArray(Object[] arr){
        int n=arr.length/2;
        for (int i=1;i<n;i++){
            for (int j=-i;j<i;j+=2){
                swap(arr,n+j,n+j+1);

            }
        }
    }
}

Answer 1

I think I have something that might be faster than O(n²) without using more than O(1) memory. The idea is as follows: Start with element 2. Calculate where it needs to go. Store it there and calculate where the replaced element needs to go etc. until we reach 2 again.

Then look for an element that we have not swapped yet. We can find this out by checking whether the replacement sequence for the element touches an element with a lower index.

Problems:

• How do you prove that a replacement sequence will actually come back to the start element?
• Finding the next element looks O(n²)-ish but I think it should better on average.

The code (it should really count how many elements where swapped for a better termination condition):

public class Scratch {

  public static int newPos(int i, int len) {
    return i < len/2 ? i * 2 : (i - len/2) * 2 + 1;
  }

  public static int swapChain(int index0, String[] arr) {
    int i = index0;
    int nextStart = i + 1;
    int newPos = newPos(i, arr.length);
    String s = arr[newPos];
    arr[newPos] = arr[i];
    i = newPos;
    do {
      if (i == nextStart) {
        nextStart++;
      }
      newPos = newPos(i, arr.length);
      String t = arr[newPos];
      arr[newPos] = s;
      s = t;
      i = newPos;
    } while (i != index0);

    boolean valid;
    do {
      valid = true;
      i = nextStart;
      do {
        i = newPos(i, arr.length);
        if (i < nextStart) {
          nextStart++;
          if (nextStart >= arr.length / 2) {
            return nextStart;
          }
          valid = false;
          break;
        }
      } while (i != nextStart);
    } while (!valid);
    return nextStart;
  }

  public static void shuffle(String[] arr) {
    int start = 1;
    do {
      start = swapChain(start, arr);
    } while (start < arr.length / 2);
    System.out.println(Arrays.toString(arr));
  }

  public static void main(String[] args) {
    shuffle(new String[]{"1", "2", "3", "a", "b", "c"});
  }
}

Update:

I think the fact that newPos() is bijective over a finite set implies that the algorithm is correct.

Some worst case data (len is the array length, steps the number of calls to newPos(), factor is steps/len, average factor is sum(steps)/sum(len)):

len: 8 steps: 9 factor 1.125 average factor: 0.8333333333333334
len: 16 steps: 29 factor 1.8125 average factor: 1.0857142857142856
len: 22 steps: 43 factor 1.9545454545454546 average factor: 1.2384615384615385
len: 28 steps: 72 factor 2.5714285714285716 average factor: 1.4663461538461537
len: 34 steps: 89 factor 2.6176470588235294 average factor: 1.644736842105263
len: 36 steps: 113 factor 3.138888888888889 average factor: 1.8029411764705883
len: 50 steps: 189 factor 3.78 average factor: 2.0462962962962963
len: 76 steps: 315 factor 4.144736842105263 average factor: 2.2432432432432434
len: 78 steps: 349 factor 4.4743589743589745 average factor: 2.3549422336328627
len: 112 steps: 504 factor 4.5 average factor: 2.5752351097178683
len: 136 steps: 664 factor 4.882352941176471 average factor: 2.8520255863539448
len: 142 steps: 712 factor 5.014084507042254 average factor: 2.823874755381605
len: 148 steps: 757 factor 5.114864864864865 average factor: 2.915825522710887
len: 162 steps: 861 factor 5.314814814814815 average factor: 3.050753012048193
len: 176 steps: 1041 factor 5.9147727272727275 average factor: 3.058876117496807
len: 202 steps: 1195 factor 5.915841584158416 average factor: 3.1066019417475728
len: 204 steps: 1329 factor 6.514705882352941 average factor: 3.1727913175932976
len: 244 steps: 1628 factor 6.672131147540983 average factor: 3.391762196747534
len: 304 steps: 2075 factor 6.8256578947368425 average factor: 3.726240646770448
len: 344 steps: 2589 factor 7.526162790697675 average factor: 3.908449284129865
len: 372 steps: 2983 factor 8.018817204301076 average factor: 3.934933870040253
len: 414 steps: 3380 factor 8.16425120772947 average factor: 4.053607098062898
len: 582 steps: 4902 factor 8.422680412371134 average factor: 4.413604801694715
len: 634 steps: 5615 factor 8.85646687697161 average factor: 4.502837189000436
len: 730 steps: 6701 factor 9.17945205479452 average factor: 4.637317723148786
len: 750 steps: 7097 factor 9.462666666666667 average factor: 4.679881984141619
len: 918 steps: 8880 factor 9.673202614379084 average factor: 4.8680720666104635
len: 1044 steps: 10267 factor 9.834291187739463 average factor: 5.031746787592856
len: 1212 steps: 12529 factor 10.337458745874587 average factor: 5.264601457155285
len: 1380 steps: 14839 factor 10.752898550724638 average factor: 5.3897728130741545
len: 1884 steps: 20660 factor 10.966029723991507 average factor: 5.784626659341847
len: 2052 steps: 23829 factor 11.612573099415204 average factor: 5.873873018885831
len: 2430 steps: 28415 factor 11.693415637860083 average factor: 6.030116322986142
len: 2598 steps: 30610 factor 11.782140107775211 average factor: 6.180337159160489
len: 2724 steps: 32969 factor 12.103157121879589 average factor: 6.215429400065934
len: 3270 steps: 39688 factor 12.137003058103975 average factor: 6.467267421298626
len: 3438 steps: 42335 factor 12.313845258871437 average factor: 6.534241807866802
len: 3564 steps: 44661 factor 12.531144781144782 average factor: 6.560849072043468
len: 3900 steps: 50485 factor 12.944871794871794 average factor: 6.655069539654636
len: 5224 steps: 68497 factor 13.111983154670751 average factor: 7.054594665556264
len: 5244 steps: 69375 factor 13.229405034324943 average factor: 7.058061034933604
len: 5412 steps: 72399 factor 13.377494456762749 average factor: 7.109842815290902
len: 5580 steps: 75029 factor 13.446057347670251 average factor: 7.135766175139542
len: 6588 steps: 90712 factor 13.769277474195507 average factor: 7.350829503005787
len: 6630 steps: 91307 factor 13.771794871794873 average factor: 7.36897875631633
len: 7134 steps: 100175 factor 14.041911970843847 average factor: 7.445842926414864
len: 7428 steps: 105366 factor 14.184975767366721 average factor: 7.5209458113740535
len: 8310 steps: 120431 factor 14.492298435619736 average factor: 7.654482597990361
len: 8814 steps: 128257 factor 14.551508963013388 average factor: 7.747129962677958
len: 9612 steps: 142392 factor 14.81398252184769 average factor: 7.856045162329174
len: 11460 steps: 171110 factor 14.931064572425829 average factor: 8.085284774991209
len: 12784 steps: 196548 factor 15.374530663329162 average factor: 8.24557688280267
len: 13812 steps: 213424 factor 15.452070663191428 average factor: 8.34207247251243
len: 14358 steps: 225811 factor 15.727190416492547 average factor: 8.403979957946827
len: 14694 steps: 233376 factor 15.882400979991834 average factor: 8.431773037753628
len: 17844 steps: 285690 factor 16.010423671822462 average factor: 8.698396681443686
len: 19860 steps: 323874 factor 16.30785498489426 average factor: 8.856597387159667
len: 19902 steps: 326059 factor 16.38322781629987 average factor: 8.860489779349878
len: 20028 steps: 328974 factor 16.425704014379868 average factor: 8.862442462977043
len: 23094 steps: 382677 factor 16.570407898155366 average factor: 9.046465277516655
len: 24900 steps: 415401 factor 16.68277108433735 average factor: 9.154661149194464
len: 28638 steps: 478313 factor 16.702039248550875 average factor: 9.359179435956479
len: 28764 steps: 489089 factor 17.00351133361146 average factor: 9.363446080908416
len: 29772 steps: 509199 factor 17.103284965739622 average factor: 9.412757619449271
len: 29982 steps: 513747 factor 17.1351811086652 average factor: 9.428669816872958
len: 32460 steps: 557422 factor 17.172581638940233 average factor: 9.528070456961768
len: 34644 steps: 612173 factor 17.67039025516684 average factor: 9.614116225080016
len: 38340 steps: 687700 factor 17.936880542514345 average factor: 9.75928795391779
len: 43380 steps: 782907 factor 18.047648686030428 average factor: 9.931165436868616
len: 44094 steps: 818495 factor 18.562502834852815 average factor: 9.954259890345835
len: 55182 steps: 1030147 factor 18.668170780326918 average factor: 10.283520352739814
len: 55350 steps: 1048684 factor 18.946413730803975 average factor: 10.287452618361032
len: 69462 steps: 1333151 factor 19.192522530304338 average factor: 10.618773030829923
len: 83532 steps: 1607630 factor 19.245678302925825 average factor: 10.87596852886678
len: 87774 steps: 1700299 factor 19.371328639460433 average factor: 10.951728617842308
len: 90088 steps: 1762592 factor 19.565225113222628 average factor: 10.988007959921369
len: 95964 steps: 1888910 factor 19.68352715601684 average factor: 11.074210030942767
len: 96804 steps: 2002173 factor 20.682750712780464 average factor: 11.086712711809684

Answer 2

var a = [1, 2, 3, 4, 5, 6, 7];
var b = [];
var c = 0;
    // In Run time you can get any number of values and substitute it. 
    // I'm declaring the values since I'm not getting the values in run time.

if (a.length % 2 == 0) {
        var timesToIterate = a.length /
                2;

}
else {
        timesToIterate = (a.length - 1) /
                2;

}

for (i = (a.length - 1); i >=
        timesToIterate; i--) {
        b.push(a[i]);

        for (j = c; j < timesToIterate; j++) {
                b.push(a[j]);
                c++;
                break;
        }
}