Sorting odd in descending and even ascending order

Given an array of random numbers, sort the odd elements in descending order and the even numbers in ascending order.

Input Example: (1,4,5,2,3,6,7)
Output:(7,5,3,1,2,4,6)

Optimization for time complexity.

+3
source share
6 answers

What language is it in, C or C ++ (I see both tags)

In C ++, you can use std::sort()with the appropriate ordering function. In C, it qsort()works similarly:

#include <iostream>
#include <algorithm>
bool Order(int a, int b)
{
        if (a%2 != b%2) return a%2;
        else return a%2 ? b<a : a<b;
}
int main()
{
        int a[] = {1,4,5,2,3,6,7};
        size_t N = sizeof(a) / sizeof(a[0]);

        std::sort(a, a+N, Order);

        for(size_t i=0; i<N; ++i)
                std::cout << a[i] << ' ';
        std::cout << std::endl;

}
+2
source

Here C # is single-line:

int[] x = { 1,4,5,2,3,6,7 };
Array.Sort(x, (a, b) => a % 2 == 0 ? b % 2 == 0 ? a.CompareTo(b) : 1 : b % 2 == 0 ? -1 : -1 * a.CompareTo(b));

. , , , , , , .

() . , , # Array.Sort() .OrderBy() stl ++. , , , , , .

+1

:

#include <algorithm>
#include <functional>

bool is_odd(int x)
{
    return x & 1;
}

int* rushakoff(int* begin, int* end)
{
    int* middle = std::partition(begin, end, is_odd);
    std::sort(begin, middle, std::greater<int>());
    std::sort(middle, end, std::less<int>());
    return middle;
}

int main()
{
    int array[] = {1,4,5,2,3,6,7};
    rushakoff(array, array + 7);
}

, , . , -)

+1
// Sort with a custom comparison function
// returns -1 if a before b, 0 if a==b, 1 if a after b
int _cmp(a,b) {
  if (a % 2) == 0 {
    if (b % 2) == 0 {
      return (a>b) ? 1 : (a==b) 0 : -1; # Even(a) vs Even(b)
    } else {
      return 1; # Even(a) vs Odd(b) all evens are after all odds
    }
  } else {
    if (b % 2) == 0 {
      return -1; # Odd(a) vs Even(b) all odds are before all evens
    } else {
      return (b>a) ? 1 : (a==b) 0 : -1; # Odd(a) vs Odd(b) has reverse order
    }
  }
}
0

O (n), .

0

- SO. , . C.

:

  • ,
  • , .
  • Even an increase to an odd increase
  • Even a descent to a strange downward

In the code below, options 1-4 are shown - from them options 5-8 are easily created (do not do the final test for odd and even, select the correct upward or downward comparison):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* odd numbers in ascending order before even numbers in descending order */
static int oddasc_evendesc(const void *vp1, const void *vp2)
{
    int v1 = *(int *)vp1;
    int v2 = *(int *)vp2;
    if ((v1 & 1) != (v2 & 1))
    {
        /* One odd, one even */
        if (v1 & 1)
            return -1;      /* Odd is smaller */
        return +1;
    }
    /* Both odd or both even */
    if ((v1 & 1) == 1)
        return (v1 < v2) ? -1 : (v1 > v2) ? +1 : 0;     /* Ascending */
    return (v1 < v2) ? +1 : (v1 > v2) ? -1 : 0;         /* Descending */
}

/* even numbers descending before odd numbers ascending */
static int evendesc_oddasc(const void *vp1, const void *vp2)
{
    int v1 = *(int *)vp1;
    int v2 = *(int *)vp2;
    if ((v1 & 1) != (v2 & 1))
    {
        /* One odd, one even */
        if (v1 & 1)
            return +1;      /* Odd is larger */
        return -1;
    }
    /* Both odd or both even */
    if ((v1 & 1) == 1)
        return (v1 > v2) - (v1 < v2);     /* Ascending */
    return (v1 < v2) - (v1 > v2);         /* Descending */
}

/* odd numbers in descending order before even numbers in ascending order */
static int odddesc_evenasc(const void *vp1, const void *vp2)
{
    int v1 = *(int *)vp1;
    int v2 = *(int *)vp2;
    if ((v1 & 1) != (v2 & 1))
    {
        /* One odd, one even */
        if (v1 & 1)
            return -1;      /* Odd is smaller */
        return +1;
    }
    /* Both odd or both even */
    if ((v1 & 1) == 1)
        return (v1 < v2) ? +1 : (v1 > v2) ? -1 : 0;     /* Descending */
    return (v1 < v2) ? -1 : (v1 > v2) ? +1 : 0;         /* Ascending */
}

/* even numbers ascending before odd numbers descending */
static int evenasc_odddesc(const void *vp1, const void *vp2)
{
    int v1 = *(int *)vp1;
    int v2 = *(int *)vp2;
    if ((v1 & 1) != (v2 & 1))
    {
        /* One odd, one even */
        if (v1 & 1)
            return +1;      /* Odd is larger */
        return -1;
    }
    /* Both odd or both even */
    if ((v1 & 1) == 1)
        return (v1 < v2) - (v1 > v2);     /* Descending */
    return (v1 > v2) - (v1 < v2);         /* Ascending */
}

static void dump_array(const char *tag, int num, int *data)
{
    printf("%s:\n", tag);
    int i;
    const char *pad = "";
    for (i = 0; i < num; i++)
    {
        printf("%s%+3d", pad, data[i]);
        pad = " ";
        if (i % 10 == 9)
        {
            putchar('\n');
            pad = "";
        }
    }
    if (i % 10 != 0)
        putchar('\n');      /* End partial line */
    putchar('\n');          /* Blank line */
}

int main(void)
{
    int data1[] =
    {
        /* random -n 80 -- -99 99 | commalist -b '        ' -n 10 */
        +39, +36, +78, -92, +63, -21, -51, +49,   0, -77,
        -10, -49, -98, -17, +60, +83, +30, -97, -68, +86,
        +70, +84, -56,  +3, +33, -34, +14, -40, -72, -86,
        -95, -87, -73, -20, -72, -86,  -3, -71, -55, -80,
        -60,  -4, -26, -64, -31, -84, -79, +25, +41, +80,
        -54, -51, +24, -48, +13, +61, -99, +60,  -2, +16,
        -66, -30, +24, +88,  +5, -77, +13,  +3, +16, -69,
        -60, +26, +51, +16, -13, +71,  -9,  -2, +51, +72,
    };
    enum { NUM_DATA = sizeof(data1) / sizeof(data1[0]) };
    int data2[NUM_DATA];
    int data3[NUM_DATA];
    int data4[NUM_DATA];

    memmove(data2, data1, sizeof(data1));
    memmove(data3, data1, sizeof(data1));
    memmove(data4, data1, sizeof(data1));

    printf("Sort odd numbers ascending before even numbers descending\n");
    dump_array("Before", NUM_DATA, data1);
    qsort(data1, NUM_DATA, sizeof(data1[0]), oddasc_evendesc);
    dump_array("After", NUM_DATA, data1);

    printf("Sort even numbers descending before odd numbers ascending\n");
    dump_array("Before", NUM_DATA, data2);
    qsort(data2, NUM_DATA, sizeof(data2[0]), evendesc_oddasc);
    dump_array("After", NUM_DATA, data2);

    printf("Sort odd numbers descending before even numbers ascending\n");
    dump_array("Before", NUM_DATA, data3);
    qsort(data3, NUM_DATA, sizeof(data3[0]), odddesc_evenasc);
    dump_array("After", NUM_DATA, data3);

    printf("Sort even numbers ascending before odd numbers descending\n");
    dump_array("Before", NUM_DATA, data4);
    qsort(data4, NUM_DATA, sizeof(data4[0]), evenasc_odddesc);
    dump_array("After", NUM_DATA, data4);

    return 0;
}

Conclusion:

Sort odd numbers ascending before even numbers descending
Before:
+39 +36 +78 -92 +63 -21 -51 +49  +0 -77
-10 -49 -98 -17 +60 +83 +30 -97 -68 +86
+70 +84 -56  +3 +33 -34 +14 -40 -72 -86
-95 -87 -73 -20 -72 -86  -3 -71 -55 -80
-60  -4 -26 -64 -31 -84 -79 +25 +41 +80
-54 -51 +24 -48 +13 +61 -99 +60  -2 +16
-66 -30 +24 +88  +5 -77 +13  +3 +16 -69
-60 +26 +51 +16 -13 +71  -9  -2 +51 +72

After:
-99 -97 -95 -87 -79 -77 -77 -73 -71 -69
-55 -51 -51 -49 -31 -21 -17 -13  -9  -3
 +3  +3  +5 +13 +13 +25 +33 +39 +41 +49
+51 +51 +61 +63 +71 +83 +88 +86 +84 +80
+78 +72 +70 +60 +60 +36 +30 +26 +24 +24
+16 +16 +16 +14  +0  -2  -2  -4 -10 -20
-26 -30 -34 -40 -48 -54 -56 -60 -60 -64
-66 -68 -72 -72 -80 -84 -86 -86 -92 -98

Sort even numbers descending before odd numbers ascending
Before:
+39 +36 +78 -92 +63 -21 -51 +49  +0 -77
-10 -49 -98 -17 +60 +83 +30 -97 -68 +86
+70 +84 -56  +3 +33 -34 +14 -40 -72 -86
-95 -87 -73 -20 -72 -86  -3 -71 -55 -80
-60  -4 -26 -64 -31 -84 -79 +25 +41 +80
-54 -51 +24 -48 +13 +61 -99 +60  -2 +16
-66 -30 +24 +88  +5 -77 +13  +3 +16 -69
-60 +26 +51 +16 -13 +71  -9  -2 +51 +72

After:
+88 +86 +84 +80 +78 +72 +70 +60 +60 +36
+30 +26 +24 +24 +16 +16 +16 +14  +0  -2
 -2  -4 -10 -20 -26 -30 -34 -40 -48 -54
-56 -60 -60 -64 -66 -68 -72 -72 -80 -84
-86 -86 -92 -98 -99 -97 -95 -87 -79 -77
-77 -73 -71 -69 -55 -51 -51 -49 -31 -21
-17 -13  -9  -3  +3  +3  +5 +13 +13 +25
+33 +39 +41 +49 +51 +51 +61 +63 +71 +83

Sort odd numbers descending before even numbers ascending
Before:
+39 +36 +78 -92 +63 -21 -51 +49  +0 -77
-10 -49 -98 -17 +60 +83 +30 -97 -68 +86
+70 +84 -56  +3 +33 -34 +14 -40 -72 -86
-95 -87 -73 -20 -72 -86  -3 -71 -55 -80
-60  -4 -26 -64 -31 -84 -79 +25 +41 +80
-54 -51 +24 -48 +13 +61 -99 +60  -2 +16
-66 -30 +24 +88  +5 -77 +13  +3 +16 -69
-60 +26 +51 +16 -13 +71  -9  -2 +51 +72

After:
+83 +71 +63 +61 +51 +51 +49 +41 +39 +33
+25 +13 +13  +5  +3  +3  -3  -9 -13 -17
-21 -31 -49 -51 -51 -55 -69 -71 -73 -77
-77 -79 -87 -95 -97 -99 -98 -92 -86 -86
-84 -80 -72 -72 -68 -66 -64 -60 -60 -56
-54 -48 -40 -34 -30 -26 -20 -10  -4  -2
 -2  +0 +14 +16 +16 +16 +24 +24 +26 +30
+36 +60 +60 +70 +72 +78 +80 +84 +86 +88

Sort even numbers ascending before odd numbers descending
Before:
+39 +36 +78 -92 +63 -21 -51 +49  +0 -77
-10 -49 -98 -17 +60 +83 +30 -97 -68 +86
+70 +84 -56  +3 +33 -34 +14 -40 -72 -86
-95 -87 -73 -20 -72 -86  -3 -71 -55 -80
-60  -4 -26 -64 -31 -84 -79 +25 +41 +80
-54 -51 +24 -48 +13 +61 -99 +60  -2 +16
-66 -30 +24 +88  +5 -77 +13  +3 +16 -69
-60 +26 +51 +16 -13 +71  -9  -2 +51 +72

After:
-98 -92 -86 -86 -84 -80 -72 -72 -68 -66
-64 -60 -60 -56 -54 -48 -40 -34 -30 -26
-20 -10  -4  -2  -2  +0 +14 +16 +16 +16
+24 +24 +26 +30 +36 +60 +60 +70 +72 +78
+80 +84 +86 +88 +83 +71 +63 +61 +51 +51
+49 +41 +39 +33 +25 +13 +13  +5  +3  +3
 -3  -9 -13 -17 -21 -31 -49 -51 -51 -55
-69 -71 -73 -77 -77 -79 -87 -95 -97 -99

This code is available on GitHub in my SOQ (Stack Storage) as a file oddascevendesc.c(now incorrectly) in the doc / qsort subdirectory.

0
source

Source: https://habr.com/ru/post/1746720/


All Articles