Алгорим быстрой сортировки

@bgm313 · Регистрация: 27.07.2012

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

В одной из тем выложен алгоритм быстрой сортировки. Возник вопрос: если индексы i и j указывают на один элемент зачем нужен обмен?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void quick(char *items, int count)
{
  qs(items, 0, count-1);
}
 
void qs(char *items, int left, int right)
{
  register int i, j;
  char x, y;
 
  i = left; j = right;
  x = items[(left+right)/2];
 
  do {
    while((items[i] < x) && (i < right)) i++;
    while((x < items[j]) && (j > left)) j--;
 
    if(i <= j) {
      y = items[i];
      items[i] = items[j];
      items[j] = y;
      i++; j--;
    }
  } while(i <= j);
 
  if(left < j) qs(items, left, j);
  if(i < right) qs(items, i, right);
}

@OhMyGodSoLong · 11.08.2012, 20:32

Чтобы отработала строка 23 и цикл do–while закончился.

@bgm313 · 11.08.2012, 20:37 **[ТС]**

Что понимается под устойчивостью метода?

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

Сообщение от ~OhMyGodSoLong~

Чтобы отработала строка 23 и цикл do–while закончился.

Почему бы не сделать условное выражение в while, такое : i < j

@OhMyGodSoLong · 11.08.2012, 20:48

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

Что понимается под устойчивостью метода?

Устойчивые методы сортировки сохраняют относительный порядок равных элементов. К примеру, при сортировке массива
[b, D, L, a, U, S, y, r, A, s]
по алфавиту, но не по регистру (то есть A == a), устойчивый метод всегда вернёт
[a, A, b, D, L, r, S, s, U, y]
«Равные» буквы a, A, s, S следуют в точно таком же порядке, как в исходом массиве. При использовании неустойчивого алгоритма эти буквы могут идти в другом порядке, например, так:
[a, A, b, D, L, r, s, S, U, y]

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

Почему бы не сделать условное выражение в while, такое : i < j

Потому что надо, чтобы после выхода из него i > j, а не !(i < j) == (i >= j) [для того, чтобы рекурсивные вызовы не подрались за общий центральный элемент].
А такой хитрохак позволяет сэкономить пару строк кода и кидать понты «мой квиксорт укладывается в 20 строк».

@bgm313 · 11.08.2012, 20:54 **[ТС]**

Сообщение от
Потому что [I

надо[/I], чтобы после выхода из него i > j, а не !(i < j) == (i >= j). А такой хитрохак позволяет сэкономить пару строк кода и кидать понты «мой квиксорт укладывается в 20 строк».

Ну тогда смотрите можно рассмотреть 2 ситуации:
1)Действовать так, как в описанном выше алгоритме
2)Не тратить время в пустую и не обменивать элементы, сделать условие i < j и сразу после выхода сделать инкремент и декремент этих величин.
Как лучше действовать?

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

@OhMyGodSoLong · 11.08.2012, 21:15

Суть в том, что может случиться так, что i > j ещё до входа в if (в результате тех двух while выше). В этом случае инкременты делать не надо.

Дело в том, что этот лишний обмен выполняется один раз. А проверка на i == j, чтобы избежать обмена, выполняется на каждой итерации. В итоге для больших массивов может быть выгоднее сделать один лишний обмен, но не делать много лишних проверок.

Добавлено через 6 минут
И если волноваться об эффективности, то тут надо 1) избавиться от половины рекурсий, 2) выбирать вот этот индекс (left+right)/2 тщательнее, 3) маленькие массивы сортировать вставками.

Иначе достаточно уже того, что оно значительно быстрее всяких сортировок ~~обменом~~ выбором.

Новые блоги и статьи Все статьи Все блоги /
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.

@OhMyGodSoLong ~ Эврика! ~ 1258 / 1007 / 74 Регистрация: 24.07.2012 Сообщений: 2,002
	11.08.2012, 20:32
	Чтобы отработала строка 23 и цикл do–while закончился. 0

@OhMyGodSoLong ~ Эврика! ~ 1258 / 1007 / 74 Регистрация: 24.07.2012 Сообщений: 2,002
	11.08.2012, 21:15
	Суть в том, что может случиться так, что i > j ещё до входа в if (в результате тех двух while выше). В этом случае инкременты делать не надо. Дело в том, что этот лишний обмен выполняется один раз. А проверка на i == j, чтобы избежать обмена, выполняется на каждой итерации. В итоге для больших массивов может быть выгоднее сделать один лишний обмен, но не делать много лишних проверок. Добавлено через 6 минут И если волноваться об эффективности, то тут надо 1) избавиться от половины рекурсий, 2) выбирать вот этот индекс (left+right)/2 тщательнее, 3) маленькие массивы сортировать вставками. Иначе достаточно уже того, что оно значительно быстрее всяких сортировок ~~обменом~~ выбором. 1