4738. Сортировка

Отсортируйте массив целых чисел в порядке невозрастания.

Вход. Первая строка содержит размер массива n (1 ≤ n ≤ 1000). Вторая строка содержит n целых чисел, по модулю не превышающих 2 *10⁹.

Выход. Выведите заданные числа в порядке невозрастания.

Пример входа	Пример выхода
5 9 2 7 1 2	9 7 2 2 1

РЕШЕНИЕ

сортировка

Анализ алгоритма

Для сортировки целых чисел в невозрастающем порядке достаточно воспользоваться любым алгоритмом сортировки.

Например, можно воспользоваться функцией sort из библиотеки шаблонов STL. Для указания направления сортировки можно воспользоваться компараторами:

· less<int>() – для сортировки по возрастанию;

· greater<int>() – для сортировки по убыванию;

Эти компараторы определены в библиотеке <set>.

Реализация алгоритма

Объявим рабочий массив.

#define MAX 1010

int m[MAX];

Читаем входные данные.

scanf("%d",&n);

for(i = 0; i < n; i++)

scanf("%d",&m[i]);

Сортируем массив по невозрастанию.

sort(m,m+n,greater<int>());

Выводим результирующий массив.

for(i = 0; i < n; i++)

printf("%d ",m[i]);

printf("\n");

Реализация алгоритма – вектор

Объявим вектор для хранения входной последовательности чисел.

vector<int> v;

Читаем входные данные.

scanf("%d",&n);

v.resize(n);

for(i = 0; i < n; i++)

scanf("%d",&v[i]);

Сортируем массив по невозрастанию.

sort(v.begin(),v.end(),greater<int>());

Выводим результирующий массив.

for(i = 0; i < v.size(); i++)

printf("%d ",v[i]);

printf("\n");

Реализация алгоритма – компаратор

Объявим рабочий массив.

#define MAX 1001

int m[MAX];

Объявим функцию - компаратор f для сортировки целых чисел по убыванию.

int f(int a, int b)

{

return a > b;

}

Основная часть программы. Читаем входные данные.

scanf("%d", &n);

for (i = 0; i < n; i++)

scanf("%d", &m[i]);

Сортируем массив по убыванию с использованием компаратора.

sort(m, m + n, f);

Выводим результирующий массив.

for (i = 0; i < n; i++)

printf("%d ", m[i]);

printf("\n");

Java реализация – comparator

import java.util.*;

public class Main

{

public static class MyFun implements Comparator<Integer>

{

public int compare(Integer a, Integer b)

{

return b - a;

}

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

Integer m[] = new Integer[n];

for(int i = 0; i < n; i++)

m[i] = con.nextInt();

Arrays.sort(m, new MyFun());

for(int i = 0; i < n; i++)

System.out.print(m[i] + " ");

System.out.println();

con.close();

}

}

Java реализация – reverse order

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

Integer m[] = new Integer[n];

for(int i = 0; i < n; i++)

m[i] = con.nextInt();

Arrays.sort(m,Collections.reverseOrder());

for(int i = 0; i < n; i++)

System.out.print(m[i] + " ");

System.out.println();

con.close();

}

}

Python реализация

Читаем входные данные.

n = int(input())

lst = list(map(int,input().split()))

Сортируем список по невозрастанию.

lst.sort(reverse = True)

Выводим числа в порядке невозрастания.

print(*lst)