CODEWITHSUNDEEP
javasorting
VIRICH
VIRICH

Reputation: 177

How to sort a ArrayList so that the center has the largest element?

There is a need to sort the ArrayList in such a way that the center had the largest element and the tails on the sides.

For example:

0 2 3 1 0 4 5 3 0 2 4 1

I want:

0 1 2 3 4 5 4 3 2 1 0

How can this be achieved? My method looks like this, I sort by ascending, but needed as I described above.

public void generateSpeedFly(int timesec, double Speed){
        Random r = new Random();
        listSpeed = new ArrayList<>(timesec);
        listSpeed.add(0,0.);
        for (int i = 1; i <= timesec-4; i++) {
            listSpeed.add((double) r.nextInt((int) Speed));
        }
        Collections.sort(listSpeed);
        listSpeed.add(listSpeed.size(), Speed);
        minSpeed = listSpeed.get(0);
        maxSpeed = listSpeed.get(listSpeed.size() - 1);
        for (int i = 0; i < listSpeed.size(); i++){
            TotalSpeed += listSpeed.get(i);
        }
        average = TotalSpeed / listSpeed.size();
        TotalSpeed = 0;
    }

Upvotes: 0

Views: 302

Answers (3)

Oleg Cherednik
Oleg Cherednik

Reputation: 18245

I offer to use temporary array. It takes O(n) memory, but it works.

public static void sort(int[] arr) {
    int[] tmp = Arrays.stream(arr).sorted().toArray();

    for (int i = 0, l = 0, r = arr.length - 1; i < tmp.length; i++) {
        if (i % 2 == 0)
            arr[l++] = tmp[i];
        else
            arr[r--] = tmp[i];
    }
}

After think a while, I have found suitable solution without using O(n) memory, but a little bit slower:

public static void sort(int[] arr) {
    Arrays.sort(arr);

    for (int l = 1, r = arr.length - 1; l < r; l++, r--) {
        // shift 1 position left
        int tmp = arr[l];
        System.arraycopy(arr, l + 1, arr, l, r - l);
        arr[r] = tmp;
    }
}

Test: Both solutions provide same result:

Input: [ 0, 2, 3, 1, 0, 4, 5, 3, 0, 2, 4, 1 ]

Output: [ 0, 0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0 ]

Upvotes: 1

Slava Vedenin
Slava Vedenin

Reputation: 60094

// init
Integer[] result = new Integer[arr.length];
Integer[] arr = {0, 2, 3, 1, 0, 4, 5, 3, 0, 2, 4, 1};
List<Integer> listSorted = Arrays.asList(arr);

// simple sort, O(N*log(N))
Collections.sort(listSorted);

// fill result array O(n) 
int size = listSorted.size();
for(int i = 0; i < size / 2 ; i++) {
    result[size / 2 - i ] = listSorted.get(size - i * 2 - 1);
    if(size / 2 + i + 1 < size) {
        result[size / 2 + i + 1] = listSorted.get(size - i * 2 - 2);
    }
}

Result {0 1 2 3 4 5 4 3 2 1 0, O(N*log(N))

Upvotes: 0

QuentinC
QuentinC

Reputation: 14687

A simple idea that come into my mind would be so split the list into two parts, sort the left one ascending, and the right one descending.

If we take your example:

0 2 3 1 0 4 5 3 0 2 4 1

The two parts would be:

0 2 3 1 0 4
5 3 0 2 4 1

We sort the first one ascending and the second one descending:

0 0 1 2 3 4
5 4 3 2 1 0

And we finally obtain:

0 0 1 2 3 4 5 4 3 2 1 0

That's more or less what we want. I don't know if there exist cases where this algorithm would produce an undesired result. Probably if the array is badly balanced at start, the result would also bee a little unbalanced. Then come my second, perhaps more robust, idea:

  1. We sort the entire array
  2. Take each element in turn and alternatively push them in front and in back of the output
  3. Split the output into two parts left and right
  4. Assemble the two parts in reverse order

Taking again your example:

0 0 0 1 1 2 2 3 3 4 4 5

Step 1:

input: 0 1 1 2 2 3 3 4 4 5
output: 0 0

Step 2:

input: 1 2 2 3 3 4 4 5
output: 0 0 0 1

Step 3:

input: 2 3 3 4 4 5
output: 1 0 0 0 1 2

Step 4:

input: 3 4 4 5
output: 2 1 0 0 0 1 2 3

Finally we obtain:

5 4 3 2 1 0 0 0 1 2 3 4

At this stage, that's exactly the opposite of what we want. So we split:

Left: 5 4 3 2 1 0
Right: 0 0 1 2 3 4

And then finally we get:

0 0 1 2 3 4 5 4 3 2 1 0

In fact, you can avoid the final split and reassemble step if you initially sort the array descending instead of ascending. Sort your initial array so that the first element is the one that you would like to see in the center at the end.

There again, I don't know if there exist cases that would produce unexpected results. Do some math to prove or disprove it if you like. I don't think so though.

Upvotes: 2

Related Questions