C++ STL :: inplace_merge ile sort arasındaki fark nedir?

Question

Anlayabildiğim kadarıyla inplace_merge, sıralama ile aynı şeyi yapar, yalnızca belirli durumlarda çalışır (Kapsayıcı zaten iki ayrı parçada olduğunda).

int first[] = {1,3,5,7}; 
int second[] = {2,4,6,8}; 
vector<int> v(8); 
vector<int>::iterator it; 
copy(first,first+4, v.begin()); 
copy(second,second+4, v.begin()+4); 

inplace_merge(v.begin(), v.begin()+4, v.end()) 

:

Diğer bir deyişle, bu ikisi arasında bir fark yoktur.

int first[] = {1,3,5,7}; 
int second[] = {2,4,6,8}; 
vector<int> v(8); 
vector<int>::iterator it; 
copy(first,first+4, v.begin()); 
copy(second,second+4, v.begin()+4); 

sort(v.begin(), v.end()) 

Tek fark verimlilik mi olacak?

Answer 1

Onların karmaşıklığı aynı değildir:

• sort() STL uygulanması kullandığı sıralama algoritması bağlı O(N²) bir kötü durum vardır.

• inplace_merge()O(N*log(N)) bir kötü durum ve O(N-1) bir iyi kutuya sahip, bu nedenle (aynı girişli) daha yavaş sort() olmayacak. Diğerleri işaret olarak

Ayrıca, inplace_merge()stable şudur: kimin sıralama anahtarı aynıdır öğelerin sıralamasını korur. sort() bunu garanti etmez. stable_sort() yapar ve en kötü durum karmaşıklığı O(N*log(N)²)'dir.

Answer 2

İki fark:

• kararlılık: inplace_merge istikrarlı algoritmadır (aynı sırayla iki orijinal aralığı arasında her iki alt aralıklara içinde ve eşit öğeleri tutacak).
  Bu nedenle, ilkel olmayan türlerdeki kaplarla ya da sıralama işleviniz tükendiğinde, sonuçta küçük bir fark olabilir. , Herhangi bir farklılık :)
• verimliliği fark etmez int egers haznesiyle Tabii : Eğer söylediği gibi, zaten iki sıralı alt-gruba sahip olduğu gerçeği göz önüne alındığında, inplace_merge farklı bir şekilde uygulanacak ve irade olmalıdır bu nedenle muhtemelen daha verimli olur. Bu işlevin var olduğu tek gerçek, çok şey anlatıyor.

Answer 3

sort yöntem sıralar 2 artan sırayla aralığı (ilk, son) içerisinde elemanları kriteri.
inplace_search kombine sıralanmış bir aralığı içine 2 kriteri aralığı (ilk, orta) ve (orta, son) (ilk, son) birleştirir.

---

inplace_merge etkili olması için inplace_merge

sort

, sıralanmış olmalıdır 2 alt-aralıklar, (bu fark). Ayrıca, inplace_merge teorik olarak unstable, (fakat C++ 'da stable), ancak yapmak için verimli bir bellek gerektirir (son - ilk) - 1 karşılaştırmaya benzer (yani O (n log n) karşılaştırmaları yapar) karşılaştırmalar.