Сортировка терпения

Сортировка терпения — это алгоритм сортировки, основанный на карточной игре «Терпение». В этом алгоритме сортировки используются правила игры терпения для сортировки списка элементов на основе их значений.
Правила игры на терпение:

• Карты с меньшим значением можно положить поверх карты.
• Если нет подходящей позиции для карты, то можно создать новую стопку.
• Цель состоит в том, чтобы сформировать как можно меньше стопок.

Ниже представлена визуализация игры следующим образом:

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

• Инициализируйте 2D-массив для хранения свай.
• Пройдите по заданному массиву и выполните следующие операции:
  1. Перебрать все стопки и проверить, что вершина стопки каждой стопки меньше текущего элемента или нет. Если найдено, что это правда, то поместите текущий элемент на вершину стека.
  2. В противном случае создайте новую стопку с текущим элементом в качестве вершины этой стопки.
• Слияние стопок: Идея состоит в том, чтобы выполнить k -стороннее слияние p стопок, каждая из которых внутренне отсортирована. Перебрать все стопки, пока количество элементов в стопке больше или равно 0 , найти минимальный элемент из вершины каждой стопки и поместить его в отсортированный массив.

Ниже представлена визуализация этапов сортировки:

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(N)

Примечание. Приведенный выше подход можно оптимизировать путем объединения стопок с использованием priority_queue.
Временная сложность: O(N * log(N))
Вспомогательное пространство: O(N)

</br>function playGif(){ </br> var gif = document.getElementById('gif'); </br> if (gif.src == "https://media.geeksforgeeks.org/wp-content/uploads/20200501171647/Patience.gif"){ </br> gif.src = "https://media .geeksforgeeks.org/wp-content/uploads/20200501175532/base2.jpg»; </br> }else{ </br> gif.src = “https://media.geeksforgeeks.org/wp-content/uploads/20200501171647/Patience.gif”; </br> } </br>} </br>function playSortingGif(){ </br> var gif1 = document.getElementById('sorting'); </br> var gif2 = document.getElementById('sorting_gif1'); </br> gif1.style.display = «нет»; </br> gif2.style.display = «блокировать»; </br>}</br>function pauseSortingGif(){ </br> var gif1 = document.getElementById('sorting'); </br> var gif2 = document.getElementById('sorting_gif1'); </br> gif1.style.display = «блокировать»; </br> gif2.style.display = «нет»; </br>} </br>