Vraag Een vector sorteren waarin de eerste elementen al zijn gesorteerd?


Overweeg een std::vector  v van N elementen, en van mening dat de n eerste elementen zijn al gesorteerdn < N en waar (N-n)/N is erg klein:

sorted/unsorted vector

Is er een slimme manier om de STL-algoritmen te gebruiken om deze vector sneller te sorteren dan met een complete std::sort(std::begin(v), std::end(v)) ?

EDIT: een verduidelijking: de (N-n) ongesorteerde elementen moeten op de juiste positie worden ingevoegd binnen de n eerste elementen die al zijn gesorteerd.

EDIT2: bonusvraag: en hoe vind je n? (wat overeenkomt met het eerste ongesorteerde element)


37
2018-02-06 01:33


oorsprong


antwoorden:


void foo( std::vector<int> & tab, int n ) {
     std::sort( begin(tab)+n, end(tab));
     std::inplace_merge(begin(tab), begin(tab)+n, end(tab));
}

voor bewerking 2

auto it = std::adjacent_find(begin(tab), end(tab),  std::greater<int>() );
if (it!=end(tab)) {
    it++;
    std::sort( it, end(tab));
    std::inplace_merge(begin(tab), it, end(tab));
}

21
2018-02-06 01:39



Sorteer alleen het andere bereik en gebruik vervolgens std :: merge.


23
2018-02-06 01:36



De optimale oplossing zou zijn om het staartgedeelte onafhankelijk te sorteren en vervolgens in plaats samen te voegen, zoals hier wordt beschreven

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.5750

Het algoritme is nogal ingewikkeld en wordt meestal beschouwd als "niet de moeite waard".

Natuurlijk kunt u met C ++ direct gebruiksklaar gebruiken std::inplace_merge. De naam van dat algoritme is echter zeer misleidend. Ten eerste is er geen garantie dat std::inplace_merge werkt eigenlijk op zijn plaats. En wanneer het daadwerkelijk op zijn plaats is, is er geen garantie dat het niet als een volledig soort wordt geïmplementeerd. In de praktijk komt het neer op het proberen en zien of het goed genoeg is voor uw doeleinden.

Maar als je het echt op zijn plek wilt maken en formeel efficiënter dan een volledige sortering, dan moet je het handmatig implementeren. STL kan helpen met een paar hulpprogramma-algoritmen, maar het biedt geen solide oplossingen van "slechts een paar oproepen naar standaardfuncties".


9
2018-02-06 01:59



Insertion sort gebruiken N - n laatste elementen:

template <typename IT>
void mysort(IT begin, IT end) {
    for (IT it = std::is_sorted_until(begin, end); it != end; ++it) {
        IT insertPos = std::lower_bound(begin, it, *it);
        IT endRotate = it;
        std::rotate(insertPos, it, ++endRotate);
    }
}

4
2018-02-06 13:11



De Timsort sorteeralgoritme is een hybride algoritme ontwikkeld door Pythonista Tim Peters. Het maakt optimaal gebruik van reeds gesorteerde subsegmenten overal in de array, inclusief in het begin. Hoewel je misschien een sneller algoritme vindt als je dat zeker weet de eerste n elementen zijn al gesorteerd, dit algoritme zou nuttig moeten zijn voor de algehele klasse van problemen. Wikipedia beschrijft het als:

Het algoritme vindt subsets van de gegevens die al zijn besteld en gebruikt die kennis om de rest efficiënter te sorteren.

In de eigen woorden van Tim Peters,

Het heeft bovennatuurlijke prestaties op veel   soorten gedeeltelijk geordende arrays (minder dan lg (N!) vergelijkingen nodig, en   zo weinig als N-1), maar toch zo snel als de vorige, sterk afgestelde samplesort van Python   hybride op willekeurige arrays.

Volledige details worden beschreven in dit ongedateerde tekstdocument van Tim Peters. De voorbeelden staan ​​in Python, maar Python zou best leesbaar moeten zijn, zelfs voor mensen die niet bekend zijn met de syntaxis ervan.


3
2018-02-06 10:06



Gebruik std :: partition_point (of is_sorted_until) om n te vinden. Als n-m klein is, voer dan een invoegsortering uit (lineair zoeken + std: roteren).


2
2018-02-06 07:57



Ik neem aan dat je vraag twee doelen heeft:

  • runtime verbeteren (op een slimme manier)
  • met weinig moeite (beperken tot STL)

Gezien deze doelstellingen, raad ik ten zeerste af voor deze specifieke optimalisatie, tenzij u zeker weet dat de inspanning het voordeel waard is. Voor zover ik me herinner, implementeert std :: sort () het quick sort-algoritme, dat bijna net zo snel is op de voorgesorteerde invoer als om te bepalen of en hoe veel van de invoer is gesorteerd.

In plaats van u te bemoeien met std: sort, kunt u proberen de gegevensstructuur te wijzigen in een wachtrij met een sortering / prioriteit.


1
2018-02-06 10:11