Стрпљиво сортирање

Strpljivo sortiranje

Klasa	Algoritmi sortiranja
Struktura podataka	Niz
Najgora performanca	$O(n\log n)$

Strpljvo sortiranje (engl. Patience sorting) је алгоритам за сортирање, заснован на пасијанс карташкој игри, која има својство да је у стању да ефикасно израчунава дужину најдужег растучег подниза у дати низ.

Карташка игра

Игра поћиње са измешанимшпилом карата, означеним $1,2,\ldots ,n$.

Карте се деле једна по једна у низ гомила на столу, у складу са следећим правилима.

1. У почетку, нема гомила. Прва карта које се дели формира прву гомилу коју чини само једна карта.
2. Свака нова карта може бити постављена или на постојећу гомилу чија карта на врху има вредност вечу од вредности нове карте, чиме је број карата на тој гомили повећан, или десно од свих псотојећих гомила, ово формира нову гомилу.
3. Када више нема карата за дељење, игра се завршава.

Циљ игре је да се заврши са сто мање гомила. D. Алдоус анд П. Диацонис предлаже дефинисање 9 или мање гомила као победнички исход 9 за $n=52$, која има приближно 5% шансе да се догоди.

Алгоритам за сортирање

Дат је $n$-елемент низа са урађивачком релацијом као један улаз за сортирање, сматрамо да је то колекција карата, са (ункноwн ин тхе бегиннинг) стаатистичким наручивање сваког елемента који му служе као индекс. памти да игра никад не користи стварну вредност карата, изузевза поређење између две карте, и релативни редолсед било која два елемента низа је познат.

Сада симулирамо игру Патиенце сортирања, играну са похлепоом стратегијом, и.е., псотављајући сваку нову карту на крајњу леву гомилу коју је могуће легално користити.У свакој фази игре, под овом стратегијом, оyнаке на картама које се налазе на врховима сваке гомиле се повећавају с лева на десно. Да би повратили сортиран низ, више пута вадимо минималну видљиву карту.

Сложеност

Ако су вредности карата у распону $1,\ldots ,n$, постоји ефкиасна имплементација са $O(n\cdot \log \log n)$ најгори сличај потребног времена за стављање карата на гомиле, ослањајући се на ван Емде Боас стабло.Опис је дат у раду С. Беспамyатникх и M. Сегал.

Када не постоји претпоставка о вредностима, похлепна стратегија се може применити у $O(n\log n)$ поређења у најгорем случају. У ствари, један се може применитиса низом гомила поређане по вредностима карата са врха, за убацивање нове карте, користи се бинарна претрага, која је $O(\log p)$ поређења у најгорем случају, где је $p$ број гомила. Да би завршили сортирањ на ефикасан начин (ака $O(n\log n)$ најгори случај), сваки корак ће вратити карту са најмањом вредношћу са леве гомиле, а затим мора да се обави неки посао. Налажење следеће карте претрагом врхова свих гомила, као што је предлоћено и у wикибоокс доле, даје $O(n{\sqrt {n}})$ најгори случај. Међутим, моемо користити ефикаснији ред приоритета(на пример, бинарни хип)да одржи гомиле да б ми могли извући максимум података у О(лог н) времену.

Алгоритам за налажење најдућег растућег низа

Прво, извршити сортирање алгоритмом као што је горе описано. Број гомила је дужина најдуже подсеквенце. Кад год је карта постављена на врх гомиле, постављамо бацк-поинтер на карту на врху претходне гомиле (која, по претпоставци, има мању вредност од нове карте). На крају, пратимо бацк-показивач са горње карте на задњој гомили да би повратили опадајући подниз највеће дужине; њен нверз је одговор на најдужи растући подниз алгоритам.

С. Беспамyатникх и M. Сегал гдају опис ефикасније имплементације алгоритма, стварањем не додатног асyмптотиц трошка преко сортираног (како је бацк-показивач складиштен, стварање и траверсла захтевају линеарно време и порстор). они и даље показују како да пријаве све најдуже растуће поднизове из исте резултујуће структуре података.

Имплементација у језику C++

Ово је једна имплементација која користи Patience сортирање да би сортирала низ, са О(н лог н) тиме сложеношћу.

#include <vector>
#include <algorithm>
#include <stack>
#include <iterator>

template<typename PileType>
bool pile_less(const PileType& x, const PileType& y)
{
    return x.top() < y.top();
}

// reverse less predicate to turn max-heap into min-heap
template<typename PileType>
bool pile_more(const PileType& x, const PileType& y)
{
    return pile_less(y, x);
}

template<typename Iterator>
void patience_sort(Iterator begin, Iterator end)
{
    typedef typename std::iterator_traits<Iterator>::value_type DataType;
    typedef std::stack<DataType> PileType;
    std::vector<PileType> piles;

    for (Iterator it = begin; it != end; it++)
    {
        PileType new_pile;
        new_pile.push(*it);
        typename std::vector<PileType>::iterator insert_it =
            std::lower_bound(piles.begin(), piles.end(), new_pile,
                             pile_less<PileType>);
        if (insert_it == piles.end())
            piles.push_back(new_pile);
        else
            insert_it->push(*it);
    }
    // sorted array already satisfies heap property for min-heap

    for (Iterator it = begin; it != end; it++)
    {
        std::pop_heap(piles.begin(), piles.end(), pile_more<PileType>);
        *it = piles.back().top();
        piles.back().pop();
        if (piles.back().empty())
            piles.pop_back();
        else
            std::push_heap(piles.begin(), piles.end(), pile_more<PileType>);
    }
}

Имплементација у Јави

import java.util.*;
public class PatienceSort
{
    public static <E extends Comparable<? super E>> void sort (E[] n)
    {
        List<Pile<E>> piles = new ArrayList<Pile<E>>();
        // sort into piles
        for (E x : n)
        {
            Pile<E> newPile = new Pile<E>();
            newPile.push(x);
            int i = Collections.binarySearch(piles, newPile);
            if (i < 0) i = ~i;
            if (i != piles.size())
                piles.get(i).push(x);
            else
                piles.add(newPile);
        }
        System.out.println("longest increasing subsequence has length = " + piles.size());
        
        // priority queue allows us to retrieve least pile efficiently
        PriorityQueue<Pile<E>> heap = new PriorityQueue<Pile<E>>(piles);
        for (int c = 0; c < n.length; c++)
        {
            Pile<E> smallPile = heap.poll();
            n[c] = smallPile.pop();
            if (!smallPile.isEmpty())
                heap.offer(smallPile);
        }
        assert(heap.isEmpty());
    }
    
    private static class Pile<E extends Comparable<? super E>> extends Stack<E> implements Comparable<Pile<E>>
    {
        public int compareTo(Pile<E> y) { return peek().compareTo(y.peek()); }
    }
}

Историја

Према D. Алдоус и П. Диацонис, стршљиво сортирање је први пут препознато као алгоритам за израчунавање најдужег растучег подниза дужине од стране Хаммерслеy, и А.С.C. Росс и независно Роберт W. Флоyд као алгоритам за сортирање. почетне анализе је урадио Маллоwс.

Употреба

Базаар верзија контроле система користи Патианце алгоритам за спајање резолуције.