c++ - ordenado - ordenamiento burbuja
El mejor algoritmo para verificar si un vector está ordenado (13)
¿Cuál sería la mejor manera de verificar que un std::vector esté ordenado? ¿Hay algo más rápido que un bucle que comprueba que v[i]<=v[i+1] ? ¿Es más rápido / más limpio con iteradores? ¿O es realmente mejor simplemente llamar a sort todo el tiempo (aunque el caso "v ya está ordenado" es bastante común)?
Podemos suponer con seguridad que el vector solo contiene POD, normalmente float y algunas veces double s e int s.
El tamaño del vector no es trivial (generalmente unos pocos miles de elementos) pero no es extremo (no tiene un tamaño de gigabyte).
- en algunos casos, ordenaremos el vector inmediatamente después; sin embargo, hay otras instancias en las que no lo hacemos (es un caso de error de nuestro algoritmo).
- ya usamos una bandera "IsSorted" siempre que sea posible.
¿Hay algo más rápido que un bucle que comprueba que v [i] <= v [i + 1]?
Necesitará verificar cualquier valor para ver si está ordenado, para que no sea más rápido que O (n) a menos que realice un seguimiento de los cambios usted mismo mientras muta el vector o usa una estructura de datos que ya está ordenada.
¿O es realmente mejor simplemente llamar a ordenar todo el tiempo (aunque el caso "v ya está ordenado" es bastante común)?
Recuerde que el peor comportamiento de los quicksorts ocurre cuando la lista ya está ordenada (y el pivote se elige incorrectamente). Para evitar dicho comportamiento, es posible que desee comprobar std :: stable_sort como un reemplazo.
¿Hay algo más rápido que un bucle que comprueba que v [i] <= v [i + 1]?
No.
Si esto es algo que desea verificar a menudo, es posible que desee crear una clase contenedora que mantenga una marca "ordenada" que comience False, se establezca como False cada vez que se agregue un elemento y agregue una función de miembro sort () que establezca la bandera en True después de ordenar.
¿Hay algo más rápido que un bucle que comprueba que v [i] <= v [i + 1]?
No.
Sin embargo, si va a realizar el control para decidir si desea ordenar el vector, es mejor que simplemente seleccione si usa el algoritmo de clasificación correcto, es decir, std :: stable_sort y not std :: sort.
C ++ - 11 contiene is_sorted en <algorithm>.
Como otros han notado, un predicado para determinar el estado ordenado es O (n). Pero por tu mención de una bandera ordenada, me pregunto si no quieres algo como esto:
Las bibliotecas de fundación de nuestra aplicación incluyen una clase de contenedor a la que se puede consultar para obtener membresía. Aquí hay un breve boceto:
class ObjList {
public:
ObjList() {};
~ObjList() {};
bool isMember(const Item *);
void add(const Item *, bool sort = false);
private:
unsigned int last_sorted_d;
bool sorted_d;
unsigned int count_d;
Item *store_d;
};
isMember () usa una búsqueda binaria en el rango ordenado de elementos, luego una búsqueda lineal de artículos después del rango ordenado. La inserción puede desencadenar una especie de elementos, o no, de acuerdo con la elección del programador. Por ejemplo, si es consciente de que va a agregar miles de elementos en un bucle cerrado, no los clasifique hasta la inserción final.
Lo anterior es solo un boceto, y la tienda es más complicada que una serie de punteros, pero se entiende.
Para verificar ordenado debe verificar cada artículo. Entonces v [i] <= v [i + 1] es la verificación más rápida posible.
Por supuesto, no tengo conocimiento del dominio de tu problema, así que por favor ignórame si lo que digo no es relevante, pero me parece que si requiero que una colección esté siempre ordenada cada vez que accedo a ella, una colección naturalmente no ordenada como vector<T> puede no ser la mejor opción.
Si al insertar elementos utiliza la búsqueda binaria para encontrar el punto de inserción, nunca se ordenará.
Si espera que la lista esté muy cerca de ser ordenada, podría ser beneficioso intentar una modificación de la ordenación por inserción . Si la lista ya está ordenada, solo hace una pasada y se lo dice. Si la lista está casi ordenada, se ordenará muy rápidamente. Si la lista no está ordenada, salga del orden después de un número de intercambios y cambie a una oferta rápida (o stable_sort).
Si su implementación de la biblioteca estándar de C ++ contiene el alogrithm is_sorted (), es la mejor opción.
Considere múltiples núcleos de CPU
Depende de su plataforma y cantidad de elementos en el vector. Tendría que comparar para encontrar lo mejor.
No es posible responder: ¿hay algo más rápido que un bucle que compruebe que v [i] <= v [i + 1]?
Con ningún.
Porque ... las computadoras hoy en día tienen múltiples cpus / núcleos / hyperthreading. Por lo tanto, puede ser mucho más rápido explotar el paralismo en la computadora al dividir el trabajo de verificar en varios hilos, de modo que cada CPU pueda verificar un pequeño rango en paralelo.
Probablemente sea mejor hacerlo a través de una función de biblioteca en lugar de implementarla usted mismo. Las nuevas versiones de las bibliotecas explotarán el paralismo. Por lo tanto, si busca un std :: sort, probablemente encontrará que cuando compila contra las implementaciones más recientes de STL, harán la operación en paralelo sin tener que preocuparse por ello. No sé si ya hay versiones disponibles de STL que hacen esto, pero vale la pena apegarse a las funciones de la biblioteca para que cuando actualice a una versión que sí lo haga, esta optimización esté ahí para usted sin que necesite realizar ningún cambio. .
std::adjacent_find(v.begin(), v.end(), std::greater<type>()) == v.end()