Strpljivo sortiranje

Strpljivo sortiranje

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

Strpljvo sortiranje (engl. Patience sorting) je algoritam za sortiranje, zasnovan na pasijans kartaškoj igri, koja ima svojstvo da je u stanju da efikasno izračunava dužinu najdužeg rastučeg podniza u dati niz.

Kartaška igra

Igra poćinje sa izmešanimšpilom karata, označenim $1,2,\ldots ,n$.

Karte se dele jedna po jedna u niz gomila na stolu, u skladu sa sledećim pravilima.

1. U početku, nema gomila. Prva karta koje se deli formira prvu gomilu koju čini samo jedna karta.
2. Svaka nova karta može biti postavljena ili na postojeću gomilu čija karta na vrhu ima vrednost veču od vrednosti nove karte, čime je broj karata na toj gomili povećan, ili desno od svih psotojećih gomila, ovo formira novu gomilu.
3. Kada više nema karata za deljenje, igra se završava.

Cilj igre je da se završi sa sto manje gomila. D. Aldous and P. Diaconis predlaže definisanje 9 ili manje gomila kao pobednički ishod 9 za $n=52$, koja ima približno 5% šanse da se dogodi.

Algoritam za sortiranje

Dat je $n$-element niza sa urađivačkom relacijom kao jedan ulaz za sortiranje, smatramo da je to kolekcija karata, sa (unknown in the beginning) staatističkim naručivanje svakog elementa koji mu služe kao indeks. pamti da igra nikad ne koristi stvarnu vrednost karata, izuzevza poređenje između dve karte, i relativni redolsed bilo koja dva elementa niza je poznat.

Sada simuliramo igru Patience sortiranja, igranu sa pohlepoom strategijom, i.e., psotavljajući svaku novu kartu na krajnju levu gomilu koju je moguće legalno koristiti.U svakoj fazi igre, pod ovom strategijom, oynake na kartama koje se nalaze na vrhovima svake gomile se povećavaju s leva na desno. Da bi povratili sortiran niz, više puta vadimo minimalnu vidljivu kartu.

Složenost

Ako su vrednosti karata u rasponu $1,\ldots ,n$, postoji efkiasna implementacija sa $O(n\cdot \log \log n)$ najgori sličaj potrebnog vremena za stavljanje karata na gomile, oslanjajući se na van Emde Boas stablo.Opis je dat u radu S. Bespamyatnikh i M. Segal.

Kada ne postoji pretpostavka o vrednostima, pohlepna strategija se može primeniti u $O(n\log n)$ poređenja u najgorem slučaju. U stvari, jedan se može primenitisa nizom gomila poređane po vrednostima karata sa vrha, za ubacivanje nove karte, koristi se binarna pretraga, koja je $O(\log p)$ poređenja u najgorem slučaju, gde je $p$ broj gomila. Da bi završili sortiranj na efikasan način (aka $O(n\log n)$ najgori slučaj), svaki korak će vratiti kartu sa najmanjom vrednošću sa leve gomile, a zatim mora da se obavi neki posao. Nalaženje sledeće karte pretragom vrhova svih gomila, kao što je predloćeno i u wikibooks dole, daje $O(n{\sqrt {n}})$ najgori slučaj. Međutim, moemo koristiti efikasniji red prioriteta(na primer, binarni hip)da održi gomile da b mi mogli izvući maksimum podataka u O(log n) vremenu.

Algoritam za nalaženje najdućeg rastućeg niza

Prvo, izvršiti sortiranje algoritmom kao što je gore opisano. Broj gomila je dužina najduže podsekvence. Kad god je karta postavljena na vrh gomile, postavljamo back-pointer na kartu na vrhu prethodne gomile (koja, po pretpostavci, ima manju vrednost od nove karte). Na kraju, pratimo back-pokazivač sa gornje karte na zadnjoj gomili da bi povratili opadajući podniz najveće dužine; njen nverz je odgovor na najduži rastući podniz algoritam.

S. Bespamyatnikh i M. Segal gdaju opis efikasnije implementacije algoritma, stvaranjem ne dodatnog asymptotic troška preko sortiranog (kako je back-pokazivač skladišten, stvaranje i traversla zahtevaju linearno vreme i porstor). oni i dalje pokazuju kako da prijave sve najduže rastuće podnizove iz iste rezultujuće strukture podataka.

Implementacija u jeziku C++

Ovo je jedna implementacija koja koristi Patience sortiranje da bi sortirala niz, sa O(n log n) time složenošću.

#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>);
    }
}

Implementacija u Javi

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()); }
    }
}

Istorija

Prema D. Aldous i P. Diaconis, stršljivo sortiranje je prvi put prepoznato kao algoritam za izračunavanje najdužeg rastučeg podniza dužine od strane Hammersley, i A.S.C. Ross i nezavisno Robert W. Floyd kao algoritam za sortiranje. početne analize je uradio Mallows.

Upotreba

Bazaar verzija kontrole sistema koristi Patiance algoritam za spajanje rezolucije.