STL di C++ :: qual è la differenza tra inplace_merge e ordinamento

Question

Per quanto ne so, inplace_merge fa esattamente la stessa cosa di ordinamento, tranne che funziona solo in determinate circostanze (quando il contenitore è già in due parti ordinate).

In altre parole, v'è una differenza tra questi due:

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

.

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

L'unica differenza sarà l'efficienza?

Answer 1

La loro complessità non è la stessa:

• sort() ha un caso peggiore di O(N²), a seconda dell'algoritmo di ordinamento utilizzato dal implementazione STL.

• inplace_merge() ha un caso peggiore di O(N*log(N)) e un caso migliore di O(N-1), quindi sarà mai più lento rispetto sort() (con gli stessi input).

Inoltre, come altri hanno sottolineato, inplace_merge() è stable: conserva l'ordinamento dei prodotti la cui chiave di ordinamento è lo stesso. sort() non lo garantisce. stable_sort() e la sua complessità nel caso peggiore è O(N*log(N)²).

Answer 2

due differenze:

• stabilità: inplace_merge è un algoritmo stabile (si manterranno elementi uguali nello stesso ordine sia all'interno sottointervalli e tra voi due gamme originali).
  Quindi, potrebbe esserci una leggera differenza nel risultato quando si gestiscono contenitori di tipi non primitivi, o quando la funzione di ordinamento è estratta. Naturalmente, con il contenitore di int Egers, non si noterà alcuna differenza :)
• efficienza: come hai detto, dato il fatto che si dispone già di due sottoinsiemi ordinati, inplace_merge deve essere attuata in un modo diverso e quindi probabilmente sarà più efficiente. Il solo fatto che esista questa funzione dice molto.

Answer 3

I sort metodo tipo 2 scelti elementi nell'intervallo (primo, ultimo) in ordine crescente.
inplace_search fonde la gamma 2 filtrate (primo, centrale) e (centrale, last) in un intervallo ordinato combinato (primo, ultimo).

• sort
• inplace_merge

---

Per inplace_merge per essere efficiente, i 2 subrange deve essere ordinati (che è la differenza). Inoltre, inplace_merge è teoricamente unstable, (ma stable in C++) ma richiede una memoria efficiente per eseguire (ultimo - primo) - 1 confronti altrimenti è simile all'ordinamento (che fa confronti O (n log n)).