sort an array, so that first and last element will form a "pair"

I have an array of objects which I want to sort by indices in the following order. I will always have an array size to the power of 2.

Example array size: 8. Indices: [0][1] [2][3] [4][5] [6][7]

After sort: [0][7] [1][6] [2][5] [3][4]

So basically alternating between first and last element which was not sorted yet.

I already thought of a way of doing it, and I can get the "pairs" but they are in the wrong order (and I think it would not work with any other to the power of 2 array?). Here I'm using an int array and their indices as values to make it simpler for myself.

int[] array = new int[]{0,1,2,3,4,5,6,7};
int[] sortedArray = new int[8];
for(int i = 0; i < array.length; i+=2){
    sortedArray[i] = array[i];
}
for(int i = 1; i < array.length; i+=2){
    sortedArray[i] = array[array.length - i];
}

Output: [0][7] [2][5] [4][3] [6][1]

Answers


You can do this with a single loop. Consider the following algorithm:

int[] array = new int[]{0,1,2,3,4,5,6,7};
int[] sortedArray = new int[8];
for(int i = 0; i < array.length; i+=2){
    sortedArray[i] = array[i/2];
    sortedArray[i + 1] = array[array.length - i/2 - 1];
}
System.out.println(Arrays.toString(sortedArray)); // prints [0, 7, 1, 6, 2, 5, 3, 4]

This creates the final array by setting two values at a time:

  • every even index of the result array is mapped with the first values of the initial array
  • every odd index of the result array is mapped with the last values of the initial array

Here's a recursive approach to it, and improvements exist.

Motivation: Work your way through the array until you're left with only two values to compare. Once you're done, simply print them. Otherwise, print the value and continue slicing the array. We use two index locations to help us walk through the array, as each one governs its end of the array. We cease recursion when the difference between our start and end index is 1.

Steps to guard against silly things, like a zero-length array, I leave as an exercise for the reader.

public static void arrangeArray(int[] array) {
    arrangeArray(array, 0, array.length - 1);
}

private static void arrangeArray(int[] array, int startIndex, int endIndex) {
    System.out.printf("[%d][%d]\t", array[startIndex], array[endIndex]);
    if(endIndex - startIndex > 1) {
        arrangeArray(array, startIndex + 1, endIndex - 1);
    }
}

You can extend a List and then Override the way this List works with indices so 0 remains 0 but 1 becomes physically a 2 in your internal array.

If you implement this object correctly, Collections.sort() won't see the difference. Then you can add your methods to get the internal Array for whatever you have to do.

The advantage of this approach is performance. You don't have to scramble the list yourself in a secondary step.


class swap
{
public static void main(String args[])
{
int arr[]={0,1,2,3,4,5,6,7};
int sorted[]=new int[8];
int end=7;
int i=1,j;
for(int k=0;k<8;k++)
{
sorted[k]=arr[k];
}
for(j=1;j<8;j=j+2)
{
sorted[j]=arr[end];
end--;
}
for(j=2;j<8;j=j+2)
{
sorted[j]=arr[i];
i++;
}
for(int k=0;k<8;k++)
System.out.println(sorted[k]);
}
}

Need Your Help

Disable mouse scrolling for the webpage

html flash web

I have a website using enjin.com website builder, and I have a page where you can go to play my game that is a .swf, but its html form, and the game requires mouse scrolling for some features and w...

Android studio having fun of me with Gradle version

gradle android-studio

I have just updated Android Studio to 0.4.2, and the first time I launched it I got an error saying: