Школа программиста

1/20/2025, 12:06:02 PM 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Как уже было сказано ранее, в языке C++ имеется встроенная функция sort, которая позволяет нам сортировать массив a[0..n-1] по неубыванию с использованием следующего простого вызова:

sort(a, a+n);

Но этого может быть недостаточно. А что если нам нужно упорядочить только часть массива? Или нужно отсортировать его не по возрастанию, а по убыванию? Или же нам необходимо упорядочить массив, элементы которого несравнимы, например, мы хотим упорядочить массив структур по какому-либо ключу или по какому-либо иному нестандартному критерию. А может обычный целочисленный массив мы хотим отсортировать не по значению элементов а по сумме их цифр... Если вы еще не сталкивались с подобным, то для вас есть хорошая новость: всё это возможно реализовать с использованием все той же функции sort, и разумеется, без какой-либо самостоятельной реализации алгоритма сортировки.

Итак, сначала поймем, что за аргументы у функции sort. Это ничто иное как указатели на элементы массива. Первый аргумент - указатель на стартовый элемент, с которого следует начать сортировку, а второй - это указатель на следующий за последним элементом отрезка сортировки. Если понимать, что само имя массива a - это указатель на значение a[0], а (a+k) - это указатель на значение a[k], то становится ясно, что sort(a, a+n) - это сортировка всего массива, содержащего все элементы с 0-го до (n-1)-го. Если мы пожелаем упорядочить элементы массива a с 3-го по 7-й включительно, то нам следует написать sort(a+3, a+8).

Рассмотрим к ряду также примеры сортировки динамического массива (вектора):

#include <vector>
#include <algorithm>
...
  int n=10;
  vector<int> a(n);
...
  sort(a.begin(), a.end());        //сортировка массива по неубыванию
  sort(a.rbegin(), a.rend());      //сортировка массива по невозрастанию
  sort(a.begin()+3, a.begin()+8);  //сортировка подмассива a[3..7]
...

Функция sort может иметь 3 аргумента и в качестве третьего аргумента выступает имя функции-компаратора, которая описывает критерий сравнения элементов сортируемого массива. Данная функция должна иметь два параметра того же типа, что и элементы сортируемого массива, а сама должна возвращать значение логического типа: истину, если первый аргумент должен в результате сортировки иметь меньший индекс, и ложь - в противном случае. Если третий параметр у sort не указан, то используется сравнение по-умолчанию (если элементы массива сравнимы). В большинстве случаев в функцию-компаратор значения сравниваемых элементов следует передавать по ссылке, это может существенно ускорить процесс сортировки, особенно если элементы массива занимают значительный объем памяти.

Приведем пример программы, которая сортирует массив "несравнимых" структур - временных дат. Действительно, структуры в языке C++ несравнимы и без использования функции-компаратора упорядочить массив структур с помощью функции sort не представляется возможным. Реализация сортировки структур может выглядеть следующим образом:

#include <bits/stdc++.h>
 
using namespace std;
 
//структура "дата"
struct date{
  int day,   //день
      month, //месяц
      year;  //год
};
 
//массив, содержащий 9 дат
date a[]={
  {14,12,2005}, {28,2,2003}, {28,8,2007},
  {31,10,2001}, {26,9,2006}, {27,2,2011},
  {19,11,2007}, {16,3,2000}, {30,6,2002}
};
 
//функция-компаратор
bool cmp(date &a, date &b){
  if(a.year<b.year) return true;
  if(a.year>b.year) return false;
  if(a.month<b.month) return true;
  if(a.month>b.month) return false;
  return a.day<b.day;
}
int main(){
  sort(a, a+9, cmp);
  for(int i=0; i<9; i++)
    cout << a[i].day << '.' << a[i].month << '.' << a[i].year << endl;
  return 0;
}

Здесь мы имеем массив d из 9 элементов типа date, каждый из которых представляет собой структуру, в которой 3 поля: день, месяц и год. Для сортировки данного массива использована функция-компаратор cmp(a,b) (имя компаратора может быть произвольным), которая принимает по ссылке два элемента типа date и возвращает истину (true), если дата a меньше даты b (т.е. если элемент a должен иметь меньший индекс, чем b в результате сортировки). Используя данную функцию мы сортируем массив, указав её имя в качестве третьего параметра в sort.

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Введение
 Условный оператор
 Операторы цикла
 Строковые типы данных
 Массивы
 Функции
 Сортировка
 Двумерные массивы
 Рекурсия
 Квадратичная сортировка
 Быстрая сортировка
 Сортировка структур
 A. Экзамены
 B. Ученики
 C. Прыжки в длину

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru