C/C++ FAQ :: Быстрая сортировка (сортировка Хоара)

@voral · Регистрация: 16.03.2008

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

Вопрос, скорее академический, по мотивам реализации.
Вот в faq приведена реализация этого метода сортировки на C++. В коде есть следующий фрагмент:

C++
1
2
3
4
5
6
7
8
9
do {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;
 
    if (i <= j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i<=j );

Т.е. у нас бывает ситуация когда i=j ( я так понимаю - как раз центральный элемент). При этом мы так же прогоняем через temp.
Т.е. три лишних операции присвоения. Ускорится ли выполнение (понимаю что разница мала, но все же если немного изменить)

C++
1
2
3
4
5
if (i <= j)
    {
      if (i < j) {temp = a[i]; a[i] = a[j]; a[j] = temp;};
      i++; j--;
    }

@grizlik78 · 08.06.2011, 02:54

Вряд ли. Тут ещё вопрос, что будет дешевле — пустой обмен один раз или проверка условия много раз. Как бы медленнее не получилось

Тогда уж логичнее вообще вынести эту проверку из цикла.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  do {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;
 
    if (i < j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i < j );
 
  if (i == j) {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;
 
    if (i == j) {
      i++; j--;
    }
  }

Вроде я нигде не погорячился, но всё-равно надо тщательно проверять.
А в сколь-нибудь заметном выигрыше я опять же сомневаюсь. Если не лень — проведи эксперимент

@voral · 08.06.2011, 02:58 **[ТС]**

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

Вряд ли. Тут ещё вопрос, что будет дешевле — пустой обмен один раз или проверка условия много раз. Как бы медленнее не получилось

А. да. точно. что-то я тормознул...

@AlvinMax · 06.01.2013, 23:06

Можно и встроенной функцией sort отсортировать!

@voral · 08.01.2013, 13:54 **[ТС]**

Конечно можно.....
Только не во всех случаях это возможно и не во всех эффективно.

В данном конкретном топике вопрос был по алгоритму, а не о том "как отсортировать"

@palva · 03.06.2020, 18:29

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

В данном конкретном топике вопрос был по алгоритму, а не о том "как отсортировать"

Хоть и очень старый топик, но вопрос явно остался непроясненным. Я только что разбирался с алгоритмом и как раз задавался тем же вопросом. Соображения у меня такие: если допустить i = j, то на следующем уровне рекурсии подмассивы, отправляющиеся на досортировку, окажутся на единицу длиннее, что увеличит общее число обменов. Программа просто переложит часть своей работы на нижний уровень рекурсии.

Новые блоги и статьи Все статьи Все блоги /
Непрерывная интеграция для пакета Python Mr. Docker 22.06.2025 Было 4 часа утра пятницы, когда я выпустил новую версию нашей внутренней библиотеки для обработки данных. Релиз 0. 5. 2 содержал небольшой фикс для обработки дат в ISO формате, что может пойти не так?. . .	Продвинутый ETL на C# из OLTP БД в хранилище stackOverflow 22.06.2025 Работая в сфере корпоративной аналитики, я постоянно сталкиваюсь с одним и тем же - нужны чистые, структурированные и, главное, свежие данные. Без них современные аналитические системы, машинное. . .	Мастер-класс по микросервисам на Node.js Reangularity 21.06.2025 Node. js стал одной из самых популярных платформ для микросервисной архитектуры не случайно. Его неблокирующая однопоточная модель и событийно-ориентированный подход делают его идеальным для. . .	Управление Arduino из WPF приложения Wired 21.06.2025 Зачем вообще связывать Arduino с WPF-приложением? Казалось бы, у Arduino есть собственная среда разработки, своя экосистема, свои способы управления. Однако при создании серьезных проектов. . .	Звёздная пыль kumehtar 20.06.2025 Я просто это себе представляю: как создавался этот мир. Как энергия слипалась в маленькие частички. Как они собирались в первые звёзды, как во вселенной впервые появился Свет. Как эти звёзды. . .
Создание нейросети с PyTorch AI_Generated 19.06.2025 Ключевое преимущество PyTorch — его питоновская натура. В отличие от TensorFlow, который изначально был построен как статический вычислительный граф, PyTorch предлагает динамический подход. Это. . .	JWT аутентификация в ASP.NET Core UnmanagedCoder 18.06.2025 Разрабатывая веб-приложения, я постоянно сталкиваюсь с дилеммой: как обеспечить надежную аутентификацию пользователей без ущерба для производительности и масштабируемости? Классические подходы на. . .	Краткий курс по С# aaLeXAA 18.06.2025 Здесь вы найдете все необходимые функции чтоб написать програму на C# Задание 1: КЛАСС FORM 1 public partial class Form1 : Form { Spisok listin = new Spisok(); . . .	50 самых полезных примеров кода Python для частых задач py-thonny 17.06.2025 Эффективность работы разработчика часто измеряется не количеством написаных строк, а скоростью решения задач. Готовые сниппеты значительно ускоряют разработку, помогают избежать типичных ошибок и. . .	C# и продвинутые приемы работы с БД stackOverflow 17.06.2025 Каждый . NET разработчик рано или поздно сталкивается с ситуацией, когда привычные методы работы с базами данных превращаются в источник бессонных ночей. Я сам неоднократно попадал в такие ситуации,. . .

@AlvinMax 0 / 0 / 0 Регистрация: 05.01.2013 Сообщений: 16
	06.01.2013, 23:06
	Можно и встроенной функцией sort отсортировать! 0

@voral 2980 / 1412 / 256 Регистрация: 16.03.2008 Сообщений: 6,244 Записей в блоге: 2
	08.01.2013, 13:54 [ТС]
	Конечно можно..... Только не во всех случаях это возможно и не во всех эффективно. В данном конкретном топике вопрос был по алгоритму, а не о том "как отсортировать" 0

Опции темы

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара)

Решение