manual

Algoritmos de busqueda y ordenacion
________________________________________
Dentro de este apartado se veran un conjunto de algoritmos bien conocidos y en cuya implementacion se ha cuidado almaximo la eficiencia.
Todos los algoritmos de este capitulo tienen dos versiones, una que utiliza el operator< y otra que utiliza un objeto funcion para comparar los elementos.
Algoritmos de busqueda yordenacion>
• sort()
• stable_sort()
• partial_sort()
• nth_element()
• lower_bound()
• upper_bound()
• equal_range()
• binary_search()
• merge()
• inplace_merge()________________________________________
sort()
Función
template
inline void sort(RandomAccessIterator first, RandomAccessIterator last)}

template
inline void sort(RandomAccessIterator first, RandomAccessIteratorlast,
Compare comp)
Descripción
sort() ordena una secuencia empleando una combinacion de dos metodos de ordenacion. Primero utiliza quicksort que divide la recursivamenet la entradaen particiones cada vez mas pequeñas. Cuando las particiones son menores que un tamaño predefinido, entonces se ordenan utilizando un algoritmo de insercion.
Este algoritmo tiene una eficiencia mediade N*log(N), sin embargo el peor caso, cuando la secuencia ya esta ordenada, tiene un eficiencia de N*N.
________________________________________
stable_sort()
Función
template
inline voidstable_sort(RandomAccessIterator first,
RandomAccessIterator last)

template
inline void stable_sort(RandomAccessIterator first,
RandomAccessIteratorlast, Compare comp)
Descripción
stable_sort() ordena una secuencia preservando el orden relativo de los elementos. La eficiencia de este algoritmo es, ene media, N*log(N), y en el pero casoN*log(N)*log(N).
________________________________________
partial_sort()
Función
template
inline void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,...