Geek asks and answers

Sorting an array by difference in pairs

For example, we have an array. X[n] = {X0, X1, X2, ... Xn} The goal is to sort this array so that the difference between each pair is ascending.

for instance X[] = {10, 2, 7, 4}

Answers:

2 7 10 4
4 10 7 2

I have a code, but it's brute force :)

#include <stdio.h>

int main(int argc, char **argv)
{
    int array[] = { 10, 2, 7, 4 };
    int a[4];

    for(int i = 0; i < 4; i++){
        a[0] = array[i];

        for(int j = 0; j < 4; j++){
            a[1] = array[j];
            if(a[0] == a[1])
               continue;

            for(int k = 0; k < 4; k++){
                a[2] = array[k];
                if(a[0] == a[2] || a[1] == a[2])
                    continue;

            for(int l = 0; l < 4; l++){
                a[3] = array[l];
                if(a[0] == a[3] || a[1] == a[3] || a[2] == a[3])
                    continue;
                if(a[0] - a[1] < a[1] - a[2] && a[1] - a[2] < a[2] - a[3])  
                    printf("%d %d %d %d\n", a[0], a[1], a[2], a[3]);
             }
         }
     }
   }
    return 0;
 }

Any idea for a “pretty” algorithm? :)

+5
source share
3 answers

A solution to this problem is not always possible. For example, an array X[] = {0, 0, 0}cannot be “sorted” as needed, since both differences are always equal.

, , "", : , . "" .

enter image description here

: , , ( ) .

() : , , , , , . , .

( ), : , (AB, BC), . , X : (A, B, C) X ; X .

  • .
  • , "" ( Graham), , , "" . , "" "". , , .
  • "" "" , "" . , , "" . "" "" 2 ( , 3).

, , , , . , . , , - , . - , - "" , .

"" , "" . . , 2 3 O (N). , 1.

+1

. . to @Wess Ness

the difference between every pair is in ascending order.

O (n) * log (n), . :

[n/2, n/2+1, n/2-1, n/2+2, n/2-2, n/2+3 ...] +1 , (n/2) -

[n/2, n/2-1, n/2+1, n/2-2, n/2+2, n/2-3 ...] -1 .

.

!!! , , , .

: {1, 2, 10, 15, 40, 50, 60, 61, 100, 101}

50 ( 10/2 = 5), 60 (10/2 + 1 = 6), 40 ...

: {40, 50, 15, 60, 10, 61, 2, 100, 1, 101}

: 10, 35, 45, 50, 51, 59, 88, 99, 100

+2

. {10,2,7,4} , :

2 7 10 4         
 5 3  -6     differences,  a[i+1] - a[i]

4 10 7 2
 6 -3 -5

, .

, , a[i+1] - a[i] . , , . , - . , - .

: {4,8,20,15,16,1,3}. :

1 3 4 8 15 16 20
 2 1 4 7  1  4      differences,  a[i+1] - a[i]

Now, 20 goes in the middle, and after it to the right the values ​​should go gradually further . Since the differences to the left of 20 in the solution are positive, the values ​​themselves increase, i.e. Sorted. So, no matter what remains after we select some of them to go to the right of the maximum element, it will remain as it is, and the (positive) differences should be in descending order. If they are, a solution has been found.

There are no solutions. The following options are possible:

...  20 16 8    (no more)  left:  1 3 4 15    (diffs: 2 1 11 5) 
...  20 16 4    (no more)  left:  1 3 8 15    (diffs: 2 5 7 5)
...  20 16 3    (no more)  left:  1 4 8 15    (diffs: 3 4 7 5)
...  20 16 1    (no more)  left:  3 4 8 15  ....................
...  20 15 8    (no more)  left:  1 3 4 16
...  20 15 4    (no more)  left:  1 3 8 16
...  20 15 3    (no more)  left:  1 4 8 16
...  20 15 1    (no more)  left:  3 4 8 16
...  20 8       (no more)  left:  1 3 4 15 16
...  20 4       (no more)  left:  1 3 8 15 16
...  20 3       (no more)  left:  1 4 8 15 16
...  20 1       (no more)  left:  3 4 8 15 16
...  20         (no more)  left:  1 3 4 8  15 16

Without 1 and 3, several solutions are possible.

+2
source

More articles:


All Articles