Терпеливая сортировка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 26 промежуточных версий 3 участников)
Строка 2: Строка 2:
  
 
== Алгоритм ==
 
== Алгоритм ==
Имеем массив <tex>source [0..n]</tex>, элементы которого нужно отсортировать по возрастанию. Разложим элементы массива по стопкам: для того чтобы положить элемент в стопку, требуется выполнение условия {{---}} новый элемент меньше элемента, лежащего на вершине стопки; либо создадим новую стопку справа и сделаем наш элемент её вершиной. Используем жадную стратегию: каждый элемент кладётся в самую левую стопку из возможных, если же таковой нет, справа от существующих стопок создаётся новая.
+
Имеем массив <tex>source [0..n-1]</tex>, элементы которого нужно отсортировать по возрастанию. Разложим элементы массива по стопкам: для того чтобы положить элемент в стопку, требуется выполнение условия {{---}} новый элемент меньше элемента, лежащего на вершине стопки; либо создадим новую стопку справа и сделаем наш элемент её вершиной. Используем жадную стратегию: каждый элемент кладётся в самую левую стопку из возможных, если же таковой нет, справа от существующих стопок создаётся новая.
Для получения отсортированного массива сначала построим массив стопок, затем выполним <tex>n</tex> шагов: на <tex>i</tex>-м шаге выберем из всех вершин стопок наименьшую, извлечём её и запишем в массив <tex>ans [0..n]</tex> на <tex>(i-1)</tex>-ю позицию.
+
Для получения отсортированного массива сначала построим массив стопок, затем выполним <tex>n</tex> шагов (здесь и далее нумерация шагов начинается с единицы): на <tex>i</tex>-м шаге выберем из всех вершин стопок наименьшую, извлечём её и запишем в массив <tex>ans [0..n-1]</tex> на <tex>i</tex>-ю позицию.
  
Мы формируем новую стопку, когда встречаем элемент больший, чем вершины всех стопок, расположенных слева. В то же время стопки слева были созданы ранее, то есть элементы в них идут в исходной последовательности раньше текущего. Значит, появление новой стопки можно понимать как увеличение длины наибольшей возрастающей подпоследовательности на единицу (изначально длина НВП равна единице). Кроме того, каждая стопка представляет собой убывающую последовательность, т.е. длина НВП в пределах стопки равна единице. Поэтому длина наибольшей возрастающей подпоследовательности равна количеству стопок.
+
Мы формируем новую стопку, когда встречаем элемент больший, чем вершины всех стопок, расположенных слева. В то же время стопки слева были созданы ранее, то есть элементы в них идут в исходной последовательности раньше текущего. Каждая стопка представляет собой убывающую последовательность, то есть длина НВП в пределах стопки равна единице, поэтому появление новой стопки можно понимать как увеличение длины наибольшей возрастающей подпоследовательности на единицу (изначально длина НВП равна единице). Поэтому длина наибольшей возрастающей подпоследовательности равна количеству стопок.
  
 
Для получения наибольшей возрастающей подпоследовательности при формировании стопок проведём следующие операции: каждый раз, положив элемент на вершину стопки, будем создавать указатель на возможный предыдущий элемент (вершину ближайшей слева стопки). В конце для получения наибольшей возрастающей подпоследовательности нужно выполнить <tex>p</tex> шагов, начав с вершины самой правой стопки: на <tex>i</tex>-м шаге записать в <tex>lis[0..p-1]</tex> на <tex>(p-i)</tex>-ю позицию текущий элемент, перейти к предыдущему элементу по указателю,  <tex>p</tex> {{---}} количество стопок.
 
Для получения наибольшей возрастающей подпоследовательности при формировании стопок проведём следующие операции: каждый раз, положив элемент на вершину стопки, будем создавать указатель на возможный предыдущий элемент (вершину ближайшей слева стопки). В конце для получения наибольшей возрастающей подпоследовательности нужно выполнить <tex>p</tex> шагов, начав с вершины самой правой стопки: на <tex>i</tex>-м шаге записать в <tex>lis[0..p-1]</tex> на <tex>(p-i)</tex>-ю позицию текущий элемент, перейти к предыдущему элементу по указателю,  <tex>p</tex> {{---}} количество стопок.
  
 
== Сложность ==
 
== Сложность ==
Создадим массив [[стек|стеков]] для хранения стопок. При раскладывании элементов по стопкам для поиска самой левой подходящей стопки используем [[Целочисленный двоичный поиск|бинарный поиск]]. Соответственно, поиск самой левой стопки занимает <tex>O(\log</tex> <tex>p)</tex>, где p {{---}} количество стопок (стеков). Таким образом, временная сложность раскладывания по стопкам не превышает <tex>O(n \log n)</tex>. Если диапазон, в котором могут изменяться данные, известен, временная сложность алгоритма формирования стопок составляет <tex>O(n \log \log n)</tex>. Такая оценка основывается на структуре данных [[Дерево ван Эмде Боаса|Дерево ван Эмде Боаса]].
+
Создадим [[список|список]] [[стек|стеков]] для хранения стопок. При раскладывании элементов по стопкам для поиска самой левой подходящей стопки используем [[Целочисленный двоичный поиск|бинарный поиск]]. Соответственно, поиск самой левой стопки занимает <tex>O(\log</tex> <tex>p)</tex>, где p {{---}} количество стопок (стеков). Таким образом, временная сложность раскладывания по стопкам не превышает <tex>O(n \log n)</tex>.  
  
Для получения отстортированного массива используем [[Двоичная куча|бинарную кучу]]. На каждом шаге алгоритма необходимо извлечь из кучи стек с минимальной вершиной за <tex>O(\log</tex> <tex>p)</tex>, где p - количество стеков в куче. Снять вершину выбранного стека и вернуть его в кучу за <tex>O(\log</tex> <tex>p)</tex>. Получение отсортированного массива займёт <tex>O(n \log</tex> <tex>n)</tex> времени.
+
Для получения отстортированного массива используем [[Двоичная куча|бинарную кучу]]. На каждом шаге алгоритма необходимо извлечь из кучи стек с минимальной вершиной за <tex>O(\log</tex> <tex>p)</tex>, где <tex>p</tex> {{---}} количество стеков в куче. Снять вершину выбранного стека и вернуть его в кучу за <tex>O(\log</tex> <tex>p)</tex>. Получение отсортированного массива займёт <tex>O(n \log</tex> <tex>n)</tex> времени.
 
Получение наибольшей возрастающей подпоследовательности выполняется за <tex>O(n)</tex> по описанному выше алгоритму.
 
Получение наибольшей возрастающей подпоследовательности выполняется за <tex>O(n)</tex> по описанному выше алгоритму.
 
Таким образом, алгоритм сортировки требует <tex>O(n \log n)</tex> времени в худшем случае и <tex>O(n)</tex> дополнительной памяти при любом раскладе.
 
Таким образом, алгоритм сортировки требует <tex>O(n \log n)</tex> времени в худшем случае и <tex>O(n)</tex> дополнительной памяти при любом раскладе.
Строка 18: Строка 18:
 
== Псевдокод ==
 
== Псевдокод ==
  
   //формирование стопок
+
   Map<E, E> previous
   List<Stack<E>> piles
+
  <font color = green>// формирование стопок</font>
  '''for''' (i = 0..n - 1)
+
   List<Stack<E>> createPiles(E[] source):
  Stack<E> pile = Pile(source[i])
+
      List<Stack<E>> piles
  i = BinarySearch(piles, pile)
+
      '''for''' i = 0..n - 1
  '''if''' (i == piles.size)
+
          Stack<E> pile = Pile(source[i])
      piles.Add(pile)
+
          j = binarySearch(piles, pile)
  '''else'''
+
          '''if''' j == piles.size
      piles[i].Add(Pile(source[i]))
+
              piles.add(pile)
  piles[i].Top.Previous() = piles[i - 1].Top // для последующего получения НВП
+
          '''else'''
 +
              piles[j].add(Pile(source[i]))
 +
          previous.set(piles[j].peek(), piles[j - 1].peek()) <font color=green> // для последующего получения НВП </font>
 +
      '''return''' piles
  
   //Получение отсортированного массива
+
   <font color = green>// Получение отсортированного массива</font>
   bool comparePiles (Stack<E> x, Stack<E> y)
+
   '''bool''' comparePiles(Stack<E> x, Stack<E> y):
       return x.Peek() < y.Peek()
+
       return x.peek() < y.peek()
   PriorityQueue<Stack<E>> q(piles, comparePiles)
+
   E[] getSortedArray(E[] source):
  '''for''' (i = 0..n - 1)
+
      List<Stack<E>> piles = createPiles(source):
      answer[i] = q.Min().Pop()
+
      PriorityQueue<Stack<E>> q(piles, '''comparator''' = comparePiles)
 +
      '''for''' i = 0..n - 1
 +
          answer[i] = q.min().pop()
 +
      '''return''' answer
  
   //Получение наибольшей возрастающей подпоследовательности
+
   <font color = green>// Получение наибольшей возрастающей подпоследовательности</font>
   answer[n - 1] = piles[piles.size - 1].Top
+
   E[] getLIS(List<Stack<E>> piles):
  E prev = answer[n - 1].Previous()
+
      lis[n - 1] = piles[piles.size - 1].peek()
  '''for''' (i = n - 2..0)
+
      E prev = previous.get(lis[n - 1])
      answer[i]=prev
+
      '''for''' i = n - 2..0
      prev = answer[i].Previous()
+
          lis[i] = prev
 +
          prev = previous.get(lis[i])
 +
      '''return''' lis
  
 
== Пример ==
 
== Пример ==

Текущая версия на 19:21, 4 сентября 2022

Терпеливая сортировка (англ. patience sorting) — алгоритм сортировки с худшей сложностью [math]O(n[/math] [math]\log[/math] [math]n)[/math]. Позволяет также вычислить длину наибольшей возрастающей подпоследовательности данного массива. Алгоритм назван по одному из названий карточной игры "Солитёр" — "Patience".

Алгоритм

Имеем массив [math]source [0..n-1][/math], элементы которого нужно отсортировать по возрастанию. Разложим элементы массива по стопкам: для того чтобы положить элемент в стопку, требуется выполнение условия — новый элемент меньше элемента, лежащего на вершине стопки; либо создадим новую стопку справа и сделаем наш элемент её вершиной. Используем жадную стратегию: каждый элемент кладётся в самую левую стопку из возможных, если же таковой нет, справа от существующих стопок создаётся новая. Для получения отсортированного массива сначала построим массив стопок, затем выполним [math]n[/math] шагов (здесь и далее нумерация шагов начинается с единицы): на [math]i[/math]-м шаге выберем из всех вершин стопок наименьшую, извлечём её и запишем в массив [math]ans [0..n-1][/math] на [math]i[/math]-ю позицию.

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

Для получения наибольшей возрастающей подпоследовательности при формировании стопок проведём следующие операции: каждый раз, положив элемент на вершину стопки, будем создавать указатель на возможный предыдущий элемент (вершину ближайшей слева стопки). В конце для получения наибольшей возрастающей подпоследовательности нужно выполнить [math]p[/math] шагов, начав с вершины самой правой стопки: на [math]i[/math]-м шаге записать в [math]lis[0..p-1][/math] на [math](p-i)[/math]-ю позицию текущий элемент, перейти к предыдущему элементу по указателю, [math]p[/math] — количество стопок.

Сложность

Создадим список стеков для хранения стопок. При раскладывании элементов по стопкам для поиска самой левой подходящей стопки используем бинарный поиск. Соответственно, поиск самой левой стопки занимает [math]O(\log[/math] [math]p)[/math], где p — количество стопок (стеков). Таким образом, временная сложность раскладывания по стопкам не превышает [math]O(n \log n)[/math].

Для получения отстортированного массива используем бинарную кучу. На каждом шаге алгоритма необходимо извлечь из кучи стек с минимальной вершиной за [math]O(\log[/math] [math]p)[/math], где [math]p[/math] — количество стеков в куче. Снять вершину выбранного стека и вернуть его в кучу за [math]O(\log[/math] [math]p)[/math]. Получение отсортированного массива займёт [math]O(n \log[/math] [math]n)[/math] времени. Получение наибольшей возрастающей подпоследовательности выполняется за [math]O(n)[/math] по описанному выше алгоритму. Таким образом, алгоритм сортировки требует [math]O(n \log n)[/math] времени в худшем случае и [math]O(n)[/math] дополнительной памяти при любом раскладе.

Псевдокод

  Map<E, E> previous
  // формирование стопок
  List<Stack<E>> createPiles(E[] source):
      List<Stack<E>> piles
      for i = 0..n - 1
          Stack<E> pile = Pile(source[i])
          j = binarySearch(piles, pile)
          if j == piles.size
              piles.add(pile)
          else
              piles[j].add(Pile(source[i]))
          previous.set(piles[j].peek(), piles[j - 1].peek())  // для последующего получения НВП 
      return piles
  // Получение отсортированного массива
  bool comparePiles(Stack<E> x, Stack<E> y):
     return x.peek() < y.peek()
  E[] getSortedArray(E[] source):
      List<Stack<E>> piles = createPiles(source):
      PriorityQueue<Stack<E>> q(piles, comparator = comparePiles)
      for i = 0..n - 1
          answer[i] = q.min().pop()
      return answer
  // Получение наибольшей возрастающей подпоследовательности
  E[] getLIS(List<Stack<E>> piles):
     lis[n - 1] = piles[piles.size - 1].peek()
     E prev = previous.get(lis[n - 1])
     for i = n - 2..0
         lis[i] = prev
         prev = previous.get(lis[i])
     return lis

Пример

Рассмотрим работу алгоритма на массиве [math][3, 1, 2, 4, 5, 0][/math].

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

Стопка 1 Стопка 2 Стопка 3 Стопка 4 Стопка 5 Стопка 6
3 не существует не существует не существует не существует не существует
3 1 не существует не существует не существует не существует не существует
3 1 2 (предшествующий элемент - 1) не существует не существует не существует не существует
3 1 2 4 (предшествующий элемент - 2) не существует не существует не существует
3 1 2 4 5 (предшествующий элемент - 4) не существует не существует
3 1 0 2 4 5 не существует не существует

Получим отсортированный массив:

Вершины Минимум
0 2 4 5 0
1 2 4 5 1
3 2 4 5 2
3 4 5 3
4 5 4
5 5

Получим наибольшую возрастающую подпоследовательность:

Текущий элемент Предшествующий элемент
5 4
4 2
2 1
1 null

Источники информации