StackSort сортировка массива через Stack Overflow


Оглавление (нажмите, чтобы открыть):

алгоритм — C ++ Получение ошибки StackOverflow в функции быстрой сортировки

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

Этот код работает нормально, когда я случайным образом генерирую массив любого размера, например, размером 5000. Но когда я генерирую массив размером 5000, отсортированный по убыванию, а затем пытаюсь отсортировать с использованием этого кода, я получаю ошибку stackoverflow. Ограничивает ли C ++ объем памяти, используемой стеком, и почему это происходит.

Решение

Quicksort имеет действительно ужасную производительность в худшем случае, как вы обнаружили здесь. Он вызывает себя на глубине стека 5000. Эта статья в Википедии имеет хорошую дискуссию на эту тему. В частности, упоминается хвостовая рекурсия как решение вашей проблемы переполнения стека.

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

Другие решения

Стандарт C ++ не определяет размер стека исполняемой программы.

Этот предел обычно определяется в файле make или в файле команды компоновщика вашего проекта.

В зависимости от вашей IDE вы также можете найти ее в настройках вашего проекта (в настройках компоновщика).

Ответ, данный TonyK довольно неплохо объясняет использование быстрой сортировки в стеке при худшем сценарии (как в вашем коде, где arr сортируется в обратном порядке).

Быстрая сортировка stackoverflow для больших массивов

Итак, мне было поручено реализовать быстрый алгоритм сортировки и сравнить время работы для массивов размером 500, 3500 и 80000. Массивы заполняются случайными числами:

Мой алгоритм быстрой сортировки работает для массивов размером 500 и 3500, но я всегда получаю ошибку stackoverflow при попытке отсортировать третий массив размером 80000. Мои другие алгоритмы сортировки отлично справляются с этими массивами.

Мой метод быстрой сортировки:

Мой метод разделения:

Я читал, что могу просто изменить размер стека в параметрах виртуальной машины (не уверен, как это сделать), но это просто игнорирует проблему в моем алгоритме. Что вызывает ошибку? Спасибо!

EDIT: Вот мой класс драйвера:

Вот мой класс SortTimes:

Если quickSort() все еще использует pivot x = a [p], а не x = a [(p + r)/2], то, если данные уже отсортированы, quickSort(), вероятно, получит переполнение стека ( это также произойдет, если будет много дубликатов). Любая вероятность того, что вы используете quickSort() для данных, которые уже были отсортированы по предыдущей сортировке?

Вот ваша оперативная сортировка:

Он работает, но в худшем случае он использует пространство стека O (r-p). Это слишком много для реальных реализаций. Исправить легко, однако — вы рекурсируете на более мелкий раздел, а затем зацикливаете на большой раздел. Рекурсия на меньшем разделе означает, что вы используете только пространство стека O (log (r-p)), независимо от того, что:

EDIT: так, таким образом, реализация реальных quicksort гарантирует, что в худшем случае нет переполнений стека.

НО В худшем случае никогда не происходит, когда вы инициализируете массив со случайными числами.

Вы сказали, что вы инициализировали массив с помощью (int)Math.random()*1000000 . Проверьте таблицы приоритетов! Приведение происходит до умножения, так что это всегда 0, поэтому вы получаете худшее поведение. Вы хотите (int)(Math.random()*1000000) .


EDIT: Ваша функция разбиения также нарушена. Он всегда будет оставлять [p] в позиции p, даже если это самый большой элемент в массиве

Вы сообщаете о переполнении стека с массивом из 80 тысяч элементов. Ваш код сортирует массив на 80 миллионов элементов на моем ноутбуке без проблем за 10 секунд. Я не вижу ошибок.

Если у вас есть случайный ввод, вы должны ожидать, что максимальная глубина рекурсии будет где-то в шаге журнала 2 (n), что меньше 30 для n = 80 000 000. статья quicksort wikipedia содержит более подробный анализ. В принципе, если вы не нажмете действительно патологический случай (где все ваши опорные точки ужасны), вы не должны ожидать увидеть столько рекурсии, что переполнение стека.

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

Исправьте генерацию случайных чисел

(int)Math.random()*1000000 будет всегда возвращать нуль . Вам нужно добавить еще один набор скобок для усечения после умножения: (int)(Math.random()*1000000) .

Мастер Йода рекомендует:  Введение в spritesheet анимацию

Исправьте логику раздела

Ваш метод разделения почти соответствует логике схемы Hoare. Однако у вас, похоже, есть несколько ошибок. Если вы сравните свой код с кодом из википедии, вы увидите несколько отличий.

  • Вы устанавливаете i=p и j=r , но должны быть i=p-1 и j=r+1 .
  • Вы должны удалить приращение и декремент в своей логике подкачки, поэтому a[i++] должен быть только a[i] , а a[j—] должен быть a[j] .

Вот код, который я использовал для проверки:

Как отсортировать в Powershell объекты через Sort-Object

10 августа 2020

Для сортировки в Powershell есть командлет Sort-Object. Мы можем отсортировать любой вывод команд, в том числе массивы, хэш таблицы и по датам. Каждый вариант мы рассмотрим на примерах.

По умолчанию командлет сортирует по возрастанию (ASC). На примере ниже я получил данные по отклику процессора:

Ключ Property допускает использование нескольких значений.

Если нам нужно выполнить сортировку по убыванию (DESC), то для этого есть следующий ключ:

Если у нас не указан ключ Descending, то у нас будет такая последовательность вывода:

  1. Числа
  2. Буквы английского алфавита
  3. Буквы русского алфавита

Сортировка массивов и дат в Powershell Sort-Object

На самом деле любой объект сортируется аналогично предыдущим примерам. Если мы собираемся выполнить в Powershell сортировку по дате нужно убедиться, что нужное свойство имеет формат Datetime.

Бывает так, что дата формата INT (численный) или STR (строковый) и если вы не хотите сортировать как числа или строки, то их нужно преобразовать. Для примера так я отсортирую по типу данных datetime преобразовав число:

Как переименовывать папки в Powershell

Пример с сортировкой массива:


Хэш таблцицы сортируются так же.

Дополнительные параметры сортировки в Powershell

Хоть это и мало относится к сортировке, то у нас есть возможность получить уникальные значения в выводе:

Для сортировки с учетом регистра букв есть ключ CaseSensitive, но он похоже не работает ( как минимум в PS 5.1 ).

Другие примеры использования команд можно увидеть так:

Сортировка стека с использованием временного стека

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

Примеры:

Рекомендовано: Пожалуйста, сначала решите вопрос по « ПРАКТИКЕ », прежде чем переходить к решению.

Мы следуем этому алгоритму.

  1. Создайте временный стек, скажем, tmpStack .
  2. Пока входной стек НЕ пуст, сделайте это:
    • Вытолкнуть элемент из стека ввода, называть его временным
    • в то время как временный стек НЕ пуст и вершина временного стека больше, чем временная,
      выскочить из временного стека и вставить его в стек ввода
    • толкать темп во временном стеке
  3. Сортированные числа находятся в tmpStack

Вот пробная версия приведенного выше псевдокода.

Вопрос по sorting, quicksort, algorithm, stack-overflow, java &#8211 Stackoverflow с реализацией Quicksort Java

Возникли проблемы с реализацией быстрой сортировки в Java. Я получаю ошибку переполнения стека при запуске этой программы, и я не совсем уверен, почему. Если кто-то может указать на ошибку, было бы здорово.

Си является начальным индексом. ei — конечный индекс.

последние две строки. два, которые вызывают быструю сортировку на правой и левой сторонах центра.

Какая строка выдает исключение?

Базовый случай выглядит довольно стандартно, если размер подмассива равен 0 или 1.

Правая и левая сторона или условия выглядят как одно и то же. ei логически точно так же, как si >= ei .

Покажите нам сайт для звонков.

моего быстрого сканирования этого, но .

Даже если вы этого не сделаете, вы все равно будете использоватьмного стека с этой реализацией. Достаточно, чтобы вызвать переполнение стека. Что произойдет, если вы укажете 1 миллион уже отсортированных предметов? Вы разделите их на 1 и 999 999 пунктов, а затем выполните рекурсию. Таким образом, вам понадобится 1 миллион стековых фреймов для этой работы.

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

постскриптум ошибка здесь:


Назовите меня старомодным, но я подумал, что смысл ответа — ответить на вопрос полностью?

это не проблема: я просто запустил этот код с 14 элементами: stackoverflow .

@MitchWheat: мое исправление решает переполнение стека для одного примера, который я пробовал. Я не собираюсь исчерпывающе проверять его код, чтобы найти любую другую ошибку, которая может быть там.

Все еще не решено: могу ли я предложить вам запустить код, который вы предлагаете .

@MitchWheat: так что, возможно, я должен был сказать «ошибка», а не «ошибка».

Сортировка через стек

20 ответов

Без использования дополнительных структур данных — невозможно.

Подозреваю, что нужно использовать «аппаратный» стек вызовов?

Хорошая задача.
Если хватит соображалки, то с C# переведете:

using System;
using System.Collections.Generic;
using System.Text;

namespace StackSort <
class Program <

static void SortCompareAndPush (Stack stack, ref T item)
where T: IComparable <
if (stack.Count > 0) < // if(!stack.IsEmpty) <
do <
T next_item = stack.Pop();
if (item.CompareTo(next_item) == 1) < // if(item >next_item) <
T temp = item;
item = next_item;
next_item = temp;
>
SortCompareAndPush (stack, ref next_item);
> while (item.CompareTo(stack.Peek()) == 1); // > while(item > stack.Top);
>
stack.Push(item);
>

static void SortStack (Stack stack)
where T : IComparable <
if (stack.Count > 1) < // if(!stack.IsEmpty) <
T item = stack.Pop();
SortCompareAndPush (stack, ref item);
>
>

static void PrintStack (Stack stack) <
foreach (T item in stack) <
Console.WriteLine(item);
>
>

static void Main(string[] args) <
Stack stack = new Stack ();

Random rnd = new Random();
for (int i = 0; i (stack);

Console.WriteLine(«Sorted stack:»);
PrintStack (stack);

Код сортирует универсальный стек (класс Stack ) с использованием только лишь рекурсии.
Модификатор ref перед параметрами означает передачу аргумента по ссылке. Аналог & в C/C++ и var в Pascal.

З.Ы. Временная сложность сортировки в худшем случае O(n ^ 2).

Функция sort и компаратор в C++: что это такое

Привет, дорогие читатели! Этот урок посвящен встроенной сортировке C++ и ее учителю — компаратору.

Мастер Йода рекомендует:  Как написать бриф на разработку сайта

Что такое функция sort

Это функция, которая может сортировать указанный контейнер или обычный массив. По умолчанию она сортирует по неубыванию, но это можно изменить путем применения компаратора, об этом поговорим позже.


Принцип работы построен на алгоритме быстрой сортировки (quicksort), так что за быстроту можно не волноваться.

Также в C++ имеется другая сортировка — qsort, но она работает значительно медленнее текущей.

Чтобы нам оперировать данной функцией понадобится для начала подключить библиотеку — .

Многие языки не могут похвастаться такой гибкостью. Например, Pascal, там придется самостоятельно писать алгоритм сортировки (который составляет несколько десятков строк !).

Функция sort для вектора

Вот как выглядит конструкция вызова:

  • — здесь мы должны указать стартовую точку сортировки, необязательно это должно быть начало.
  • — тут аналогично, только уже указываем конец.
  • — его использовать в аргументах функции не обязательно. Подробнее о нем мы поговорим ниже.
  • В строках 14 — 17: добавляем элементы в вектор vec .
  • В строке 25: сортируем последовательность.
  • В строке 32: нашей стартовой точкой стала n / 2 , а также мы применили компаратор, из-за которого смогли поменять сторону сортировки (по не возрастанию). vec.begin() + n / 2 — так прибавлять к итератору можно только для вектора и массива, для других контейнеров нельзя. Подробнее почитайте про итераторы здесь.

Вот как выглядит пример запуска программы:

Функция sort для списка

Для списка list , функция sort() превращается в префиксный метод:

Функция sort для массива (array)

Чтобы отсортировать массив нам нужно использовать схему ниже:

Имя массива указывает на первую ячейку — [0] .

  • В первый аргумент записываем имя массива.
  • Далее также записываем имя массива, но уже через плюс указываем сколько ячеек надо отсортировать.

Так, например можно:

  • Отсортировать только первую половину массива, если укажем (. , + n / 2) ( n — размер массива).
  • Или начать сортировку со второй ячейки ( + 2, . ) .

Что такое компаратор

Компаратор — это функция, которая как бы учит сортировать sort. Так например можно сортировать по:


  • Кратности на 3.
  • Четности или нечетности.
  • Изменить сторону сортировки на — по убыванию.

sort передает элементы компаратору, а компаратор проверяет их по вашему алгоритму и передает true или false .

Обычно его используют когда имеется например — vector > vec и нужно отсортировать вектора по второму элементу первой ячейки ( vec[i][0].second ).

Как создать компаратор

Самого начала создаём функцию, которая и будет компаратором.

Реализации алгоритмов/Сортировка/Быстрая

Некоторые из представленных здесь реализаций используют в качестве опорного элемента один из крайних элементов подмассива. Эти реализации страдают одним общим недостатком: при передаче им уже отсортированного массива в качестве параметра, их время работы становится порядка Θ ( n 2 ) <\displaystyle \Theta (n^<2>)> .

Содержание

VBA [ править ]

Работает для произвольного массива из n целых чисел.

C# [ править ]

C [ править ]

Работает для произвольного массива из n целых чисел.

Исходный вызов функции qs для массива из n элементов будет иметь следующий вид.

C# [ править ]

C# с обобщёнными типами [ править ]

Тип Т должен реализовывать интерфейс IComparable .

C# с использованием лямбда-выражений [ править ]

C++ [ править ]

Быстрая сортировка на основе библиотеки STL [ править ]

Для вещественных чисел [ править ]

Java [ править ]

Java с инициализацией и перемешиванием массива [ править ]

и с измерением времени сортировки массива нанотаймером (работает только если нет совпадающих элементов массива).


Java без рекурсии, с использованием стека [ править ]

пошаговый алгоритм с возможностью вывода на экран текущего действия

JavaScript [ править ]

Python [ править ]

Через list comprehension:

Joy [ править ]

PHP [ править ]

Haskell [ править ]

Математическая версия — с использованием генераторов:

Данная версия алгоритма является самой короткой из возможных, но тратит слишком много дополнительной памяти. На практике такой алгоритм использоваться не может. Стоит также отметить, что списки — неудачный выбор для реализации быстрой сортировки.

Common Lisp [ править ]

В отличие от других вариантов реализации на функциональных языках, представленных здесь, приводимая реализация алгоритма на Лиспе является «честной» — она не порождает новый отсортированный массив, а сортирует тот, который поступил ей на вход, «на том же месте». При первом вызове функции в параметры l и r необходимо передать нижний и верхний индексы массива (или той его части, которую требуется отсортировать). Код использует «императивные» макросы Common Lisp’а.

Pascal [ править ]

В данном примере показан наиболее полный вид алгоритма, очищенный от особенностей, обусловленных применяемым языком. В комментариях показано несколько вариантов. Представленный вариант алгоритма выбирает опорный элемент псевдослучайным образом, что, теоретически, сводит вероятность возникновения самого худшего или приближающегося к нему случая к минимуму. Недостаток его — зависимость скорости алгоритма от реализации генератора псевдослучайных чисел. Если генератор работает медленно или выдаёт плохие последовательности ПСЧ, возможно замедление работы. В комментарии приведён вариант выбора среднего значения в массиве — он проще и быстрее, хотя, теоретически, может быть хуже.

Внутреннее условие, помеченное комментарием «это условие можно убрать» — необязательно. Его наличие влияет на действия в ситуации, когда поиск находит два равных ключа: при наличии проверки они останутся на местах, а при отсутствии — будут обменены местами. Что займёт больше времени — проверки или лишние перестановки, — зависит как от архитектуры, так и от содержимого массива (очевидно, что при наличии большого количества равных элементов лишних перестановок станет больше). Следует особо отметить, что наличие условия не делает данный метод сортировки устойчивым.

Устойчивый вариант (требует дополнительно O(n)памяти)

Быстрая сортировка, нерекурсивный вариант [ править ]

Нерекурсивная реализация быстрой сортировки через управляемый вручную стек. Функции compare и change реализуются в зависимости от типа данных.

Частично рекурсивная реализация [ править ]

Реализация на языке pascal с одной рекурсивной ветвью. После разделения массива меньшая часть сортируется рекурсивным вызовом, а бо’льшая — в цикле. Это гарантирует глубину рекурсии не более lg(N).

Пример реализации алгоритма в объектно-ориентированном стиле с обобщением по типу данных (Generics) [ править ]

В представленной реализации алгоритма быстрой сортировки элементов массива порядок сортировки определяется пользовательской функцией обратного вызова:

которая должна удовлетворять условиям контракта вызова и возвращаемого значения:

Библиотечный модуль [ править ]


Пример использования [ править ]

Prolog [ править ]

Ruby [ править ]

SML [ править ]

This example demonstrates the use of an arbitrary predicate in a functional language.

Мастер Йода рекомендует:  Задача про бесконечный поезд

Быстрая сортировка stackoverflow для больших массивов

Итак, мне было поручено реализовать быстрый алгоритм сортировки и сравнить время работы для массивов размером 500, 3500 и 80000. Массивы заполняются случайными числами:

Мой алгоритм быстрой сортировки работает для массивов размером 500 и 3500, но я всегда получаю ошибку stackoverflow при попытке отсортировать третий массив размером 80000. Мои другие алгоритмы сортировки отлично справляются с этими массивами.

Мой метод быстрой сортировки:

Мой метод разделения:

Я читал, что могу просто изменить размер стека в параметрах виртуальной машины (не уверен, как это сделать), но это просто игнорирует проблему в моем алгоритме. Что вызывает ошибку? Спасибо!

EDIT: Вот мой класс драйвера:

Вот мой класс SortTimes:

Если quickSort() все еще использует pivot x = a [p], а не x = a [(p + r)/2], то, если данные уже отсортированы, quickSort(), вероятно, получит переполнение стека ( это также произойдет, если будет много дубликатов). Любая вероятность того, что вы используете quickSort() для данных, которые уже были отсортированы по предыдущей сортировке?

Вот ваша оперативная сортировка:

Он работает, но в худшем случае он использует пространство стека O (r-p). Это слишком много для реальных реализаций. Исправить легко, однако — вы рекурсируете на более мелкий раздел, а затем зацикливаете на большой раздел. Рекурсия на меньшем разделе означает, что вы используете только пространство стека O (log (r-p)), независимо от того, что:

EDIT: так, таким образом, реализация реальных quicksort гарантирует, что в худшем случае нет переполнений стека.

НО В худшем случае никогда не происходит, когда вы инициализируете массив со случайными числами.

Вы сказали, что вы инициализировали массив с помощью (int)Math.random()*1000000 . Проверьте таблицы приоритетов! Приведение происходит до умножения, так что это всегда 0, поэтому вы получаете худшее поведение. Вы хотите (int)(Math.random()*1000000) .

EDIT: Ваша функция разбиения также нарушена. Он всегда будет оставлять [p] в позиции p, даже если это самый большой элемент в массиве

Вы сообщаете о переполнении стека с массивом из 80 тысяч элементов. Ваш код сортирует массив на 80 миллионов элементов на моем ноутбуке без проблем за 10 секунд. Я не вижу ошибок.

Если у вас есть случайный ввод, вы должны ожидать, что максимальная глубина рекурсии будет где-то в шаге журнала 2 (n), что меньше 30 для n = 80 000 000. статья quicksort wikipedia содержит более подробный анализ. В принципе, если вы не нажмете действительно патологический случай (где все ваши опорные точки ужасны), вы не должны ожидать увидеть столько рекурсии, что переполнение стека.

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

Исправьте генерацию случайных чисел

(int)Math.random()*1000000 будет всегда возвращать нуль. Вам нужно добавить еще один набор скобок для усечения после умножения: (int)(Math.random()*1000000) .


Исправьте логику раздела

Ваш метод разделения почти соответствует логике схемы Hoare. Однако у вас, похоже, есть несколько ошибок. Если вы сравните свой код с кодом из википедии, вы увидите несколько отличий.

  • Вы устанавливаете i=p и j=r , но должны быть i=p-1 и j=r+1 .
  • Вы должны удалить приращение и декремент в своей логике подкачки, поэтому a[i++] должен быть только a[i] , а a[j—] должен быть a[j] .

Вот код, который я использовал для проверки:

Быстрая сортировка

Быстрая сортировка представляет собой усовершенствованный метод сортировки, основанный на принципе обмена. Пузырьковая сортировка является самой неэффективной из всех алгоритмов прямой сортировки. Однако усовершенствованный алгоритм является лучшим из известных методом сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель Ч. Хоар назвал его быстрой сортировкой.

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

Тем самым массив разбивается на две части:

  • не отсортированные элементы слева от разрешающего элемента;
  • не отсортированные элементы справа от разрешающего элемента.

Чтобы отсортировать эти два меньших подмассива, алгоритм рекурсивно вызывает сам себя.

Если требуется сортировать больше одного элемента, то нужно

  • выбрать в массиве разрешающий элемент;
  • переупорядочить массив, помещая элемент на его окончательное место;
  • отсортировать рекурсивно элементы слева от разрешающего;
  • отсортировать рекурсивно элементы справа от разрешающего.

Ключевым элементом быстрой сортировки является алгоритм переупорядочения .

Рассмотрим сортировку на примере массива:

10, 4, 2, 14, 67, 2, 11, 33, 1, 15.

Для реализации алгоритма переупорядочения используем указатель left на крайний левый элемент массива. Указатель движется вправо, пока элементы, на которые он показывает, остаются меньше разрешающего. Указатель right поставим на крайний правый элемент массива, и он движется влево, пока элементы, на которые он показывает, остаются больше разрешающего.

Пусть крайний левый элемент — разрешающий pivot . Установим указатель left на следующий за ним элемент; right — на последний. Алгоритм должен определить правильное положение элемента 10 и по ходу дела поменять местами неправильно расположенные элементы.

Движение указателей останавливается, как только встречаются элементы, порядок расположения которых относительно разрешающего элемента неправильный.

Указатель left перемещается до тех пор, пока не покажет элемент больше 10; right движется, пока не покажет элемент меньше 10.

Эти элементы меняются местами и движение указателей возобновляется.

Процесс продолжается до тех пор, пока right не окажется слева от left .

Тем самым будет определено правильное место разрешающего элемента.

Осуществляется перестановка разрешающего элемента с элементом, на который указывает right .

Разрешающий элемент находится в нужном месте: элементы слева от него имеют меньшие значения; справа — большие. Алгоритм рекурсивно вызывается для сортировки подмассивов слева от разрешающего и справа от него.

Реализация алгоритма быстрой сортировки на Си

Добавить комментарий