C++ STL :: ¿cuál es la diferencia entre inplace_merge y sort

Question

Por lo que puedo decir, inplace_merge hace exactamente lo mismo que ordenar, excepto que solo funciona en ciertas circunstancias (cuando el contenedor ya está en dos partes ordenadas).

En otras palabras, ¿hay una diferencia entre estos dos:

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

¿La única diferencia será la eficiencia?

Answer 1

Su complejidad no es lo mismo:

• sort() tiene un peor caso de O(N²), dependiendo del algoritmo de clasificación que utiliza su aplicación STL.

• inplace_merge() tiene un peor caso de O(N*log(N)) y una mejor caso de O(N-1), por lo que nunca será más lenta que sort() (con las mismas entradas).

También, como otros han señalado, inplace_merge() es stable: preserva el orden de las partidas cuya clave de clasificación es la misma. sort() no garantiza esto. stable_sort(), y su peor de los casos es la complejidad O(N*log(N)²).

Answer 2

dos diferencias:

• estabilidad: inplace_merge es un algoritmo estable (se mantener los elementos iguales en el mismo orden tanto dentro subintervalos y entre usted dos gamas originales).
  Por lo tanto, puede haber una ligera diferencia en el resultado cuando se trata de contenedores de tipos no primitivos o cuando se extrae su función de clasificación. Por supuesto, con el contenedor de int Egers, usted no notará ninguna diferencia :)
• eficiencia: como se dijo, dado el hecho de que ya tiene dos subconjuntos ordenados, inplace_merge se debe implementar de una manera diferente y por lo tanto, probablemente sea más eficiente. El solo hecho de que esta función exista mucho.

Answer 3

Los sort tipo Método 2 ordenadas elementos en el rango (primera, última) en orden ascendente.
inplace_search fusiona el rango de 2 ordenados (primera, medio) y (segundo, apellido) en una gama ordenada combinada (primera, última).

• sort
• inplace_merge

---

Para inplace_merge para ser eficiente, las 2 sub-intervalos debe ser clasificadas (esa es la diferencia). Además, inplace_merge es teóricamente unstable, (pero stable en C++) pero requiere memoria eficiente para hacer (último - primero) - 1 comparaciones de lo contrario es similar a sort (que hace comparaciones O (n log n)).