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, то на следующем уровне рекурсии подмассивы, отправляющиеся на досортировку, окажутся на единицу длиннее, что увеличит общее число обменов. Программа просто переложит часть своей работы на нижний уровень рекурсии.

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача №1: при указании работ (справочник РаботыПоРемонтуСпецтехники),. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

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

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

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

Решение