Sequence of integers is given. Sort the given sequence so that first the
odd numbers are arranged in ascending order, and then the even numbers are
arranged in descending order.
Input. First line contains amount of numbers n (1 ≤ n ≤ 1000).
Second line contains n integer, each
no more than 2 * 109 by absolute value.
Output. Print in one line a sequence of numbers ordered according to the given
condition.
|
Sample input |
Sample output |
|
7 9 2 3 -6 -5 4 7 |
-5 3 7 9 4 2 -6 |
sort
Sort the numbers according to the following comparator f(int a, int b):
·
if a and b have different parity, then even numbers must come after odd
numbers;
·
if a and b are even, then sort them in in decreasing order;
·
if a and b are odd, then sort them in in increasing order;
Note that the input numbers can be positive and
negative.
Function abs computes
the absolute value of a number.
int abs(int n)
{
return (n > 0) ? n
: -n;
}
Declare the comparator f.
int f(int a, int b)
{
If a and b have different parity, then even numbers must come after odd
numbers.
if (abs(a % 2) !=
abs(b % 2)) return abs(a % 2) > abs(b % 2);
If a and b are even, then sort them in in decreasing order.
if (a % 2 == 0) return a > b;
If a and b are odd, then sort them in in increasing order.
if (abs(a % 2) ==
1) return a < b;
}
The main part of the program. Read the input sequence of numbers.
scanf("%d", &n);
v.resize(n);
for (i = 0; i < n; i++)
scanf("%d", &v[i]);
Sort the array.
sort(v.begin(), v.end(), f);
Print the ordered
sequence of numbers.
for (i = 0; i < n; i++)
printf("%d
", v[i]);
printf("\n");
#include <stdio.h>
#define MAX 1001
int i, n;
int m[MAX];
int abs(int n)
{
return (n > 0) ? n : -n;
}
int f(int a, int b)
{
if (abs(a % 2) != abs(b % 2)) return abs(a % 2) > abs(b % 2);
if (a % 2 == 0) return a > b;
if (abs(a % 2) == 1) return a < b;
}
int left(int i)
{
return 2 * i;
}
int right(int i)
{
return 2 * i + 1;
}
void swap(int &i, int &j)
{
int temp = i; i = j; j = temp;
}
// max - heap
void heapify(int a[], int i, int n, int f(int a, int b))
{
int largest = 0;
int l = left(i);
int r = right(i);
if (l <= n && f(a[i], a[l])) largest =
l;
else largest = i;
if (r <= n && f(a[largest], a[r])) largest = r;
if (largest != i)
{
swap(a[i], a[largest]);
heapify(a, largest, n, f);
}
}
void BuildHeap(int a[], int n, int f(int a, int b))
{
for (int i = n / 2; i > 0; i--)
heapify(a, i, n, f);
}
void HeapSort(int a[], int n, int f(int a, int b))
{
BuildHeap(a, n, f);
for (int i = n; i >= 2; i--)
{
swap(a[1], a[i]);
heapify(a, 1, i - 1, f);
}
}
int main(void)
{
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &m[i]);
HeapSort(m, n, f);
for (i = 1; i <= n; i++)
printf("%d ", m[i]);
printf("\n");
return 0;
}
Java realization
import java.util.*;
class Main
{
public static class MyFun implements
Comparator<Integer>
{
public int compare(Integer
a, Integer b)
{
if (Math.abs(a % 2) != Math.abs(b % 2))
return Math.abs(b % 2) - Math.abs(a % 2);
if (a % 2 == 0) return b - a;
return a - b;
}
}
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
int n = con.nextInt();
Vector<Integer> m = new
Vector<Integer>();
for (int i = 0; i < n; i++)
{
int val = con.nextInt();
m.add(new Integer(val));
}
Collections.sort(m, new MyFun());
for (int i = 0; i < n; i++)
System.out.print(m.get(i) + " ");
System.out.println();
con.close();
}
}
Python realization
from functools import cmp_to_key
def compare(a, b):
if abs(a % 2) != abs(b % 2): return abs(b % 2) - abs(a % 2)
if a % 2 == 0: return b - a;
return a - b;
n = int(input())
lst = map(int, input().split())
res = sorted(lst, key = cmp_to_key(compare))
print(*res)