Почему число сравнений в быстрой сортировке ( Хоара) различно?

@Sasha760 · Регистрация: 03.05.2013

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

Сортирую один и тот же массив, но в различной степени упорядоченности, почему число сравнений различно, ведь всегда должно NlogN выходить?

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
int my_qsort(int *a, int L, int R,int &num_swap,int &num_compare)
{
 int l=L, r=R; int c;
 int med = a [(L+R)/2];
 
 while(l<=r)
 {
 
    num_compare++;//следующее сравнение точно произойдет
    while((a[l] < med) && (l < = r)) {l++;   num_compare++;}
    num_compare++;//следующее сравнение точно произойдет
    while((a[r] > med) && (r > = l) ) {r-- ; num_compare++;}
 
    if(l <= r) {c=a[r];a[r]=a[l];a[l]=c;r--;l++;num_swap++;}
 
 }
 
 
 if (l < R ) my_qsort(a,l,R,num_swap, num_compare);
 
 if (r > L)  my_qsort(a,L,r,num_swap, num_compare);
 
 return 0;
}

@Dimension · 23.10.2015, 11:18

почему бы не почитать это в интернете? сложность зависит от того, как удачно выберите средний элемент ,худший случай n*n

@Kuzia domovenok · 23.10.2015, 12:52

Dimension, ппц бредятина. Это ты про num_swap может быть говоришь?

Sasha760, NlogN это не точное количество сравнений, а лишь "порядок сложности алгоритма", который кореллирует с размером массива, но не даёт точного количества операций. Вообще, оценка О-нотацией тем лучше, чем больше и рандомней сам массив.
"следующее сравнение точно произойдет", а ты не на эти условия смотри, а на условия сортировки подмассивов - в зависимости от того, как сойдутся звёзды, подмассив может быть рекурсивно отсортирован, а может и нет.

@Dimension · 23.10.2015, 13:25

Сообщение от Kuzia domovenok

ппц бредятина.

что именно в моих словах бредятина?

@Kuzia domovenok · 23.10.2015, 14:24

Dimension, да без разницы, я не читал твои слова и не собираюсь

@Dimension · 23.10.2015, 14:26

Сообщение от Kuzia domovenok

я не читал твои слова и не собираюсь

зачем тогда бредятиной называешь раз не читал?

@mporro · 23.10.2015, 15:12

Sasha760
Как и сказал Dimension, точное количество сравнений и перестановок находится в интервале от $https://www.cyberforum.ru/cgi-bin/latex.cgi?N log_2 N$ до $https://www.cyberforum.ru/cgi-bin/latex.cgi?N^2$ . Всё зависит от того, где "встречаются" индексы l и r, когда завершается цикл 6:16. В лучшем случае массив всегда делится пополам, то есть индексы встречаются ровно посредине, и требуется $https://www.cyberforum.ru/cgi-bin/latex.cgi?log_2 N$ рекурсивных вызовов. В худшем случае индексы встречаются у края массива. Тогда потребуется все $https://www.cyberforum.ru/cgi-bin/latex.cgi?N-1$ рекурсивных вызовов.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Dimension Dimension 595 / 463 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	23.10.2015, 11:18
	почему бы не почитать это в интернете? сложность зависит от того, как удачно выберите средний элемент ,худший случай n*n 1

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,532 Записей в блоге: 1
	23.10.2015, 12:52
	Dimension, ппц бредятина. Это ты про num_swap может быть говоришь? Sasha760, NlogN это не точное количество сравнений, а лишь "порядок сложности алгоритма", который кореллирует с размером массива, но не даёт точного количества операций. Вообще, оценка О-нотацией тем лучше, чем больше и рандомней сам массив. "следующее сравнение точно произойдет", а ты не на эти условия смотри, а на условия сортировки подмассивов - в зависимости от того, как сойдутся звёзды, подмассив может быть рекурсивно отсортирован, а может и нет. 1

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,532 Записей в блоге: 1
	23.10.2015, 14:24
	Dimension, да без разницы, я не читал твои слова и не собираюсь 0

@mporro 306 / 101 / 18 Регистрация: 04.07.2014 Сообщений: 571
	23.10.2015, 15:12
	Сообщение было отмечено Sasha760 как решение Решение Sasha760 Как и сказал Dimension, точное количество сравнений и перестановок находится в интервале от $https://www.cyberforum.ru/cgi-bin/latex.cgi?N log_2 N$ до $https://www.cyberforum.ru/cgi-bin/latex.cgi?N^2$ . Всё зависит от того, где "встречаются" индексы l и r, когда завершается цикл 6:16. В лучшем случае массив всегда делится пополам, то есть индексы встречаются ровно посредине, и требуется $https://www.cyberforum.ru/cgi-bin/latex.cgi?log_2 N$ рекурсивных вызовов. В худшем случае индексы встречаются у края массива. Тогда потребуется все $https://www.cyberforum.ru/cgi-bin/latex.cgi?N-1$ рекурсивных вызовов. 2

Почему число сравнений в быстрой сортировке ( Хоара) различно?

Решение