Быстрая сортировка и хвостовая рекурсия(как реализовать?)

@Maxim09 · Регистрация: 23.08.2015

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

Как реализовать хвостовую рекурсию в быстрой сортировке?

К примеру вот программа быстрого поиска:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void qsort (int b, int e)
{
  int l = b, r = e;
  int piv = arr[(l + r) / 2]; 
  while (l <= r)
  {
    while (arr[l] < piv)
      l++;
    while (arr[r] > piv)
      r--;
    if (l <= r)
      swap (arr[l++], arr[r--]);
  }
  if (b < r)
    qsort (b, r);
  if (e > l) 
    qsort (l, e); //полагаю что хвостовую рекурсию нужно реализовывать вместо этой части кода. Когда передаётся большая часть.
}

Так вот вопрос как реализовать хвостовую рекурсию в Быстрой сортировке?

@MayaNash · 11.07.2017, 19:20

Maxim09, у вас уже реализована хвостовая рекурсия. Хвостовая рекурсия - это когда функция вызывает сама себя последним вызовом. Вот у вас два последних вызова являются рекурсией. Задача уже решена. Главное - уметь объяснить это преподавателю.

@Maxim09 · 11.07.2017, 19:33 **[ТС]**

MayaNash, А если к примеру я сортирую массив в 1 миллион элементов то при рекурсии той части которая меньше опорной точки и той что больше стек разве не будет переполнен?
Я прочёл где-то что: нужно меньшую часть передать рекурсивно а большую сортировать в while цикле, не знаю как это сделать.

@MayaNash · 11.07.2017, 19:37

Maxim09, ну, да, программе выделяется лимитированное количество оперативной памяти. Но стек не будет переполнен при данном виде сортировки. Эти вызовы - они не происходят одновременно. Они происходят по очереди.
Не знаю где вы это прочитали, но это, скорее всего, устаревшая информация.

Добавлено через 15 секунд
Maxim09, ну, да, программе выделяется лимитированное количество оперативной памяти. Но стек не будет переполнен при данном виде сортировки. Эти вызовы - они не происходят одновременно. Они происходят по очереди.
Не знаю где вы это прочитали, но это, скорее всего, устаревшая информация.

Добавлено через 1 минуту
Maxim09, всегда есть предел производительности. И если говорить "а будет ли моя программа работать при бесконечном количестве элементов?" - нет не будет. Это касается любой программы.

@Maxim09 · 11.07.2017, 19:38 **[ТС]**

Вот из этого источника я взял эту идею и программу эту тоже там увидел.
Вот https://habrahabr.ru/sandbox/29775/

@MayaNash · 11.07.2017, 19:41

Вообще-то в статье написано, что имеет смысл брать элемент, максимально приближенный к медиане, и про while там ничего не говорится.
Преимущество рекурсии - в краткости изложения. Если делать ее через while, то это будет очень некрасиво.

Добавлено через 10 секунд
Да и статья 2011 года.

@DobroAlex · 11.07.2017, 19:43

Maxim09, компилятор оптимизирует рекурсию в while - цикл самостоятельно и стек вызовов не будет переполнен при исполнении

@Maxim09 · 11.07.2017, 19:45 **[ТС]**

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

брать элемент, максимально приближенный к медиане,

Т.е. вот так?

C++
1
int piv = arr[(l + r) / 2];

@MayaNash · 11.07.2017, 19:47

Maxim09, нет, вот так:

C++
1
average(arr[l], arr[r], arr[(l+r)/2])

хотя бы.

Добавлено через 1 минуту
Maxim09, медиана - это вроде среднего арифметического, только немного по-другому считается.

@Maxim09 · 11.07.2017, 19:50 **[ТС]**

медиана вроде-же так считается: первый индекс + последний индекс и делить на два так?

@MayaNash · 11.07.2017, 19:51

Maxim09, ссылка на Википедию

@Maxim09 · 11.07.2017, 20:21 **[ТС]**

А что это за метод?который вы написали.

C++
1
average(arr[l], arr[r], arr[(l+r)/2])

Т.е. что он делает? Принимает координаты начального и конечного элементов? и что-то ещё?
Поясните.

Добавлено через 26 минут
Вот сайт:http://dic.academic.ru/dic.nsf/ruwiki/46738
На котором тоже говорят что:

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

Так вот вопрос как это реализовать?

@MayaNash · 12.07.2017, 13:14

Maxim09, это нестандартный метод, я просто привела пример. Average с английского - среднее арифметическое.
Как уже писал выше Alex, компилятор оптимизирует рекурсию - превращает ее в while. Так что этого можете не бояться.

@Maxim09 · 12.07.2017, 13:18 **[ТС]**

Благодарю всех за ответы!

Новые блоги и статьи Все статьи Все блоги /
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .

@MayaNash 1296 / 470 / 151 Регистрация: 24.08.2011 Сообщений: 2,249
	11.07.2017, 19:20
	Maxim09, у вас уже реализована хвостовая рекурсия. Хвостовая рекурсия - это когда функция вызывает сама себя последним вызовом. Вот у вас два последних вызова являются рекурсией. Задача уже решена. Главное - уметь объяснить это преподавателю. 0

@Maxim09 1 / 1 / 4 Регистрация: 23.08.2015 Сообщений: 458
	11.07.2017, 19:33 [ТС]
	MayaNash, А если к примеру я сортирую массив в 1 миллион элементов то при рекурсии той части которая меньше опорной точки и той что больше стек разве не будет переполнен? Я прочёл где-то что: нужно меньшую часть передать рекурсивно а большую сортировать в while цикле, не знаю как это сделать. 0

@MayaNash 1296 / 470 / 151 Регистрация: 24.08.2011 Сообщений: 2,249
	11.07.2017, 19:37
	Maxim09, ну, да, программе выделяется лимитированное количество оперативной памяти. Но стек не будет переполнен при данном виде сортировки. Эти вызовы - они не происходят одновременно. Они происходят по очереди. Не знаю где вы это прочитали, но это, скорее всего, устаревшая информация. Добавлено через 15 секунд Maxim09, ну, да, программе выделяется лимитированное количество оперативной памяти. Но стек не будет переполнен при данном виде сортировки. Эти вызовы - они не происходят одновременно. Они происходят по очереди. Не знаю где вы это прочитали, но это, скорее всего, устаревшая информация. Добавлено через 1 минуту Maxim09, всегда есть предел производительности. И если говорить "а будет ли моя программа работать при бесконечном количестве элементов?" - нет не будет. Это касается любой программы. 0

@Maxim09 1 / 1 / 4 Регистрация: 23.08.2015 Сообщений: 458
	11.07.2017, 19:38 [ТС]
	Вот из этого источника я взял эту идею и программу эту тоже там увидел. Вот https://habrahabr.ru/sandbox/29775/ 0

@MayaNash 1296 / 470 / 151 Регистрация: 24.08.2011 Сообщений: 2,249
	11.07.2017, 19:41
	Вообще-то в статье написано, что имеет смысл брать элемент, максимально приближенный к медиане, и про while там ничего не говорится. Преимущество рекурсии - в краткости изложения. Если делать ее через while, то это будет очень некрасиво. Добавлено через 10 секунд Да и статья 2011 года. 0

@DobroAlex Заклинатель змей 705 / 560 / 219 Регистрация: 30.04.2016 Сообщений: 2,605
	11.07.2017, 19:43
	Maxim09, компилятор оптимизирует рекурсию в while - цикл самостоятельно и стек вызовов не будет переполнен при исполнении 2

@Maxim09 1 / 1 / 4 Регистрация: 23.08.2015 Сообщений: 458
	11.07.2017, 19:50 [ТС]
	медиана вроде-же так считается: первый индекс + последний индекс и делить на два так? 0

@MayaNash 1296 / 470 / 151 Регистрация: 24.08.2011 Сообщений: 2,249
	11.07.2017, 19:51
	Maxim09, ссылка на Википедию 0

@MayaNash 1296 / 470 / 151 Регистрация: 24.08.2011 Сообщений: 2,249
	12.07.2017, 13:14
	Сообщение было отмечено Maxim09 как решение Решение Maxim09, это нестандартный метод, я просто привела пример. Average с английского - среднее арифметическое. Как уже писал выше Alex, компилятор оптимизирует рекурсию - превращает ее в while. Так что этого можете не бояться. 1

@Maxim09 1 / 1 / 4 Регистрация: 23.08.2015 Сообщений: 458
	12.07.2017, 13:18 [ТС]
	Благодарю всех за ответы! 0

Быстрая сортировка и хвостовая рекурсия(как реализовать?)

Решение