Не могу понять на что способен sort, и что делает его компаратор

@Daniil__ · Регистрация: 17.01.2019

Author24 — интернет-сервис помощи студентам

Недавно мой знакомый рассказывал что-то про sort,говорил что с помощью него можно сортировать как хочешь и что хочешь,с сортировкой qSort и так понятно,но так же он упоминал что и сортировка по алфавитному порядку и т.п тоже есть,но сколько бы я не сёрфил интернет,я так и не смог выяснить пару нужных вещей для меня,а именно:
1.Как работает сама функция Sort?
2.Что из себя представляет компаратор и как он работает?
3.Возможно ли сделать с помощью этой функции сортировку по лексикографическому порядку(алфавитному),и другие,по типу по длине строк и так далее и нужно ли для этого писать массивный код ?
Очень надеюсь на помощь тех кто разбирается в этом,так же был бы очень благодарен если бы к ответам прилагались примеры в виде кода.
Заранее спасибо!

@ReDoX · 18.01.2019, 00:10

Сообщение от Daniil__

1.Как работает сама функция Sort?

quick sort с различнами фиксами

Сообщение от Daniil__

2.Что из себя представляет компаратор и как он работает?

Компаратор - функция, возвращающая bool; судя по вики, должна принимать два параметра соответствующего типа и не изменять их

C++

1 2	sort(a, a + n); // по возрастанию sort(a, a + n, [](const auto& a, const auto& b) { return a > b; }); // по убыванию

a, b - два любых числа, которые программа берет в процессе сравнения. То есть quick sort - сортировка сравнения, в коде которой есть:

C++

1 2	if (Comparator(a[i], a[j])) swap(a[i], a[j]);

Сообщение от Daniil__

другие,по типу по длине строк

C++

vector<string> a(n);
 
for (auto& i : a)
  cin >> i;
 
sort(a.begin(), a.end(), [](const auto& a, const auto& b) { return a.length() < b.length(); });

Сообщение от Daniil__

нужно ли для этого писать массивный код

Чем сложнее сравнение, тем больше код

Сообщение от Daniil__

лексикографическому порядку(алфавитному)

sort это и так сделает без каких-либо параметров, потому что a < b < c < d < e < f и т.д.

@DrOffset · 18.01.2019, 00:16

Сообщение от Daniil__

сколько бы я не сёрфил интернет

Читайте лучше книги.

Сообщение от Daniil__

Как работает сама функция Sort?

Классически, это Quick sort, но может быть и вот такой вариант-модификация: https://en.wikipedia.org/wiki/Introsort
Читайте выше приведенную книгу. Там все есть.

Сообщение от Daniil__

.Что из себя представляет компаратор и как он работает?

Это функция или функциональный объект, которые задают механизм сравнения порядка двух элементов.
Требования к этой функции можно прочитать здесь: https://en.cppreference.com/w/... eq/Compare
Также об этом есть в вышеприведенной книге.

Сообщение от Daniil__

Возможно ли сделать с помощью этой функции сортировку по лексикографическому порядку(алфавитному)

Да.

Сообщение от Daniil__

по типу по длине строк

Да.

Сообщение от Daniil__

нужно ли для этого писать массивный код

Нет.

@Daniil__ · 18.01.2019, 00:24 **[ТС]**

Сообщение от ReDoX

sort это и так сделает без каких-либо параметров, потому что a < b < c < d < e < f и т.д.

Если я не ошибаюсь,не сработает,грубо говоря если оно отсортирует 3 строки,такие как :abvce,c,aaaaaaa-то оно отсортирует их в таком порядке-c,abvce,aaaaaaa,хотя правильный ответ будет-aaaaaaa,abvce,c(т.к символ "а" стоит раньше по алфавиту,то он будет по лекс. <символа c,например).

Байт · 18.01.2019, 00:24

Daniil__, Что есть сортировка? Это процедура, состоящая из двух вещей: Сравнения и перестановки. Переставлять-то она умеет. И ЧТО сравнивать - тоже. (В этом-то все ее искусство!) А вот КАК именно сравнивать, что ты считаешь больше, а что меньше - это она не в курсах. И вот она вызывает твой "компаратор" (впервые слышу этот термин, но он понятен), то есть функцию твою, где ты ей и объясняешь свои приоритеты.

@Daniil__ · 18.01.2019, 00:25 **[ТС]**

Спасибо за информацию!

@ReDoX · 18.01.2019, 00:29

Сообщение от Daniil__

Если я не ошибаюсь,не сработает,грубо говоря если оно отсортирует 3 строки,такие как :abvce,c,aaaaaaa-то оно отсортирует их в таком порядке-c,abvce,aaaaaaa,хотя правильный ответ будет-aaaaaaa,abvce,c(т.к символ "а" стоит раньше по алфавиту,то он будет по лекс. <символа c,например).

C++

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <string>
 
using namespace std;
 
int main() {
  int n;
  cin >> n;
 
  vector<string> a(n);
  for (auto& i : a)
    cin >> i;
 
  sort(a.begin(), a.end());
 
  copy(a.cbegin(), a.cend(), ostream_iterator<string>(cout, " "));
}

input:

3
abvce
c
aaaaaaa

output:

aaaaaaa abvce c

@Daniil__ · 18.01.2019, 00:29 **[ТС]**

Сообщение от DrOffset

Читайте лучше книги.

Вы дали мне ссылку на книгу "Стандартная библиотека c++.Справочное руководство" там 2 издание,стоит ли читать перое и третье?С какого начать?Какие есть ещё хорошие книги?

Байт · 18.01.2019, 00:32

Сообщение от Daniil__

я не сёрфил интернет

Ну, иногда и синапсы в собственно мозге неплохо бы поразмять

Вот сам подумай. Пишешь ты сортировку. Простейший пузырек. Писал? Если нет - попробуй. И тут тебе надо выяснить, кто больше - кто меньше. И тебе придется на каждую разную писать свое сравнение. Скушно это. Скоро тебе это надоест. Хочется универсальную сделать. Опа! Спрошу-ка я у того, кто в теме. У компаратора

@Daniil__ · 18.01.2019, 00:34 **[ТС]**

Сообщение от ReDoX

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <string>
using namespace std;
int main() {
* int n;
* cin >> n;
vector<string> a(n);
* for (auto& i : a)
* * cin >> i;
sort(a.begin(), a.end());
copy(a.cbegin(), a.cend(), ostream_iterator<string>(cout, " "));
}

Огромное Спасибо!!!!Можно спросить,ostream_iterator<string>(cout, " "),это что?

Байт · 18.01.2019, 00:36

Сообщение от Daniil__

там 2 издание,стоит ли читать первое и третье?С какого начать?

Сортировка, это тема, появившаяся еще до царствия царя Гороха. Читай любое.

Добавлено через 1 минуту

Сообщение от Daniil__

Можно спросить,ostream_iterator<string>(cout, " "),это что?

Законы Форума строги, но справедливы. Новый вопрос - новая тема!

@DrOffset · 18.01.2019, 09:29

Сообщение от Daniil__

"Стандартная библиотека c++.Справочное руководство" там 2 издание,стоит ли читать перое и третье?

Читайте второе. Первое устарело. Третьего нет в природе, где вы его нашли?

Добавлено через 19 минут

Сообщение от Daniil__

Какие есть ещё хорошие книги?

Литература C++

Новые блоги и статьи
Интеграция Arduino и ChatGPT: Практическое руководство InfoMaster 16.01.2025 В современную эпоху технологических инноваций интеграция искусственного интеллекта с микроконтроллерами открывает принципиально новые возможности для создания умных устройств и автоматизированных. . .	Как создать робота, управляемого ChatGPT InfoMaster 16.01.2025 Концепция проекта В современную эпоху искусственный интеллект и робототехника становятся все более доступными для энтузиастов и разработчиков. Создание роботизированной руки, управляемой ChatGPT,. . .	Как создать ChatGPT бота в Telegram на Python InfoMaster 16.01.2025 В современном мире технологии искусственного интеллекта становятся все более доступными для разработчиков, открывая новые возможности для создания умных и интерактивных приложений. Одним из самых. . .	Машинное обучение с помощью Python InfoMaster 16.01.2025 Машинное обучение стало неотъемлемой частью современных технологий, позволяя компьютерам учиться на основе данных и принимать решения без явного программирования. В сочетании с языком. . .	Использование связки C# и PHP в корпоративной разработке и микросервисной архитектуре InfoMaster 16.01.2025 Введение в интеграцию C# и PHP В современной корпоративной разработке все чаще возникает потребность в создании гибких и масштабируемых решений, способных эффективно решать широкий спектр. . .	Как использовать Kerio дома для управления сетью и пользователями InfoMaster 16.01.2025 Использование технологий для улучшения повседневной жизни стало неотъемлемой частью современного быта. Одной из таких технологий является Kerio — мощный инструмент для управления сетью и. . .
Есть ли будущее у DVD и Blu-ray? InfoMaster 16.01.2025 В эпоху стремительного развития цифровых технологий и повсеместного распространения потоковых сервисов вопрос о будущем физических носителей информации становится все более актуальным. Особенно остро. . .	Как проводить научные вычисления на Python InfoMaster 15.01.2025 Python стал одним из наиболее востребованных языков программирования в области научных вычислений благодаря своей простоте, гибкости и обширной экосистеме специализированных библиотек. Научные. . .	Создание игры типа Minecraft на PyGame/Python: пошаговое руководство InfoMaster 15.01.2025 В данном руководстве мы рассмотрим процесс создания игры в стиле Minecraft с использованием библиотеки PyGame на языке программирования Python. Этот проект идеально подходит как для начинающих. . .	Как создать свою первую игру в стиле Doom на Unreal Engine InfoMaster 15.01.2025 Разработка шутера от первого лица в стиле классического Doom представляет собой увлекательное путешествие в мир игрового программирования, где сочетаются творческий подход и технические навыки. . . .	Параллельное программирование: основные технологии и принципы InfoMaster 15.01.2025 Введение в параллельное программирование Параллельное программирование представляет собой фундаментальный подход к разработке программного обеспечения, который позволяет одновременно выполнять. . .	Как написать микросервис на C# с Kafka, MediatR, Redis и GitLab CI/CD InfoMaster 15.01.2025 В современной разработке программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот подход позволяет разделить сложную систему. . .

@Daniil__ 0 / 0 / 0 Регистрация: 17.01.2019 Сообщений: 7
		1
	Не могу понять на что способен sort, и что делает его компаратор 17.01.2019, 23:44. Показов 5227. Ответов 11 Метки нет (Все метки) Недавно мой знакомый рассказывал что-то про sort,говорил что с помощью него можно сортировать как хочешь и что хочешь,с сортировкой qSort и так понятно,но так же он упоминал что и сортировка по алфавитному порядку и т.п тоже есть,но сколько бы я не сёрфил интернет,я так и не смог выяснить пару нужных вещей для меня,а именно: 1.Как работает сама функция Sort? 2.Что из себя представляет компаратор и как он работает? 3.Возможно ли сделать с помощью этой функции сортировку по лексикографическому порядку(алфавитному),и другие,по типу по длине строк и так далее и нужно ли для этого писать массивный код ? Очень надеюсь на помощь тех кто разбирается в этом,так же был бы очень благодарен если бы к ответам прилагались примеры в виде кода. Заранее спасибо! 0

@DrOffset 19409 / 10028 / 2443 Регистрация: 30.01.2014 Сообщений: 17,678
	18.01.2019, 00:16	3
	Сообщение от Daniil__ сколько бы я не сёрфил интернет Читайте лучше книги. Сообщение от Daniil__ Как работает сама функция Sort? Классически, это Quick sort, но может быть и вот такой вариант-модификация: https://en.wikipedia.org/wiki/Introsort Читайте выше приведенную книгу. Там все есть. Сообщение от Daniil__ .Что из себя представляет компаратор и как он работает? Это функция или функциональный объект, которые задают механизм сравнения порядка двух элементов. Требования к этой функции можно прочитать здесь: https://en.cppreference.com/w/... eq/Compare Также об этом есть в вышеприведенной книге. Сообщение от Daniil__ Возможно ли сделать с помощью этой функции сортировку по лексикографическому порядку(алфавитному) Да. Сообщение от Daniil__ по типу по длине строк Да. Сообщение от Daniil__ нужно ли для этого писать массивный код Нет. 1

@Daniil__ 0 / 0 / 0 Регистрация: 17.01.2019 Сообщений: 7
	18.01.2019, 00:24 [ТС]	4
	Сообщение от ReDoX sort это и так сделает без каких-либо параметров, потому что a < b < c < d < e < f и т.д. Если я не ошибаюсь,не сработает,грубо говоря если оно отсортирует 3 строки,такие как :abvce,c,aaaaaaa-то оно отсортирует их в таком порядке-c,abvce,aaaaaaa,хотя правильный ответ будет-aaaaaaa,abvce,c(т.к символ "а" стоит раньше по алфавиту,то он будет по лекс. <символа c,например). 0

Байт Диссидент 27709 / 17327 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	18.01.2019, 00:24	5
	Daniil__, Что есть сортировка? Это процедура, состоящая из двух вещей: Сравнения и перестановки. Переставлять-то она умеет. И ЧТО сравнивать - тоже. (В этом-то все ее искусство!) А вот КАК именно сравнивать, что ты считаешь больше, а что меньше - это она не в курсах. И вот она вызывает твой "компаратор" (впервые слышу этот термин, но он понятен), то есть функцию твою, где ты ей и объясняешь свои приоритеты. 1

@Daniil__ 0 / 0 / 0 Регистрация: 17.01.2019 Сообщений: 7
	18.01.2019, 00:25 [ТС]	6
	Спасибо за информацию! 0

@Daniil__ 0 / 0 / 0 Регистрация: 17.01.2019 Сообщений: 7
	18.01.2019, 00:29 [ТС]	8
	Сообщение от DrOffset Читайте лучше книги. Вы дали мне ссылку на книгу "Стандартная библиотека c++.Справочное руководство" там 2 издание,стоит ли читать перое и третье?С какого начать?Какие есть ещё хорошие книги? 0

Байт Диссидент 27709 / 17327 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	18.01.2019, 00:32	9
	Сообщение от Daniil__ я не сёрфил интернет Ну, иногда и синапсы в собственно мозге неплохо бы поразмять Вот сам подумай. Пишешь ты сортировку. Простейший пузырек. Писал? Если нет - попробуй. И тут тебе надо выяснить, кто больше - кто меньше. И тебе придется на каждую разную писать свое сравнение. Скушно это. Скоро тебе это надоест. Хочется универсальную сделать. Опа! Спрошу-ка я у того, кто в теме. У компаратора 0

@Daniil__ 0 / 0 / 0 Регистрация: 17.01.2019 Сообщений: 7
	18.01.2019, 00:34 [ТС]	10
	Сообщение от ReDoX 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <algorithm> #include <iostream> #include <iterator> #include <vector> #include <string> using namespace std; int main() { * int n; * cin >> n; vector<string> a(n); * for (auto& i : a) * * cin >> i; sort(a.begin(), a.end()); copy(a.cbegin(), a.cend(), ostream_iterator<string>(cout, " ")); } Огромное Спасибо!!!!Можно спросить,ostream_iterator<string>(cout, " "),это что? 0

Байт Диссидент 27709 / 17327 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	18.01.2019, 00:36	11
	Сообщение от Daniil__ там 2 издание,стоит ли читать первое и третье?С какого начать? Сортировка, это тема, появившаяся еще до царствия царя Гороха. Читай любое. Добавлено через 1 минуту Сообщение от Daniil__ Можно спросить,ostream_iterator<string>(cout, " "),это что? Законы Форума строги, но справедливы. Новый вопрос - новая тема! 0

@DrOffset 19409 / 10028 / 2443 Регистрация: 30.01.2014 Сообщений: 17,678
	18.01.2019, 09:29	12
	Сообщение от Daniil__ "Стандартная библиотека c++.Справочное руководство" там 2 издание,стоит ли читать перое и третье? Читайте второе. Первое устарело. Третьего нет в природе, где вы его нашли? Добавлено через 19 минут Сообщение от Daniil__ Какие есть ещё хорошие книги? Литература C++ 1

Опции темы