inicio GeNeura cursos

Algoritmos de busqueda y ordenacion


Dentro de este apartado se veran un conjunto de algoritmos bien conocidos y en cuya implementacion se ha cuidado al maximo 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 y ordenacion>


sort()

Función

template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last)}

template <class RandomAccessIterator, class Compare>
inline void sort(RandomAccessIterator first, RandomAccessIterator last,
                 Compare comp)

Descripción

sort() ordena una secuencia empleando una combinacion de dos metodos de ordenacion. Primero utiliza quicksort que divide la recursivamenet la entrada en 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 media de 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 <class RandomAccessIterator>
inline void stable_sort(RandomAccessIterator first,
                        RandomAccessIterator last)

template <class RandomAccessIterator, class Compare>
inline void stable_sort(RandomAccessIterator first,
                        RandomAccessIterator last, 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 caso N*log(N)*log(N).


partial_sort()

Función

template <class RandomAccessIterator>
inline void partial_sort(RandomAccessIterator first,
                         RandomAccessIterator middle,
                         RandomAccessIterator last)

template <class RandomAccessIterator, class Compare>
inline void partial_sort(RandomAccessIterator first,
                         RandomAccessIterator middle,
                         RandomAccessIterator last, Compare comp)

template <class InputIterator, class RandomAccessIterator>
inline RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
                  RandomAccessIterator result_first,
                  RandomAccessIterator result_last)

template <class InputIterator, class RandomAccessIterator, class Compare>
inline RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
                  RandomAccessIterator result_first,
                  RandomAccessIterator result_last, Compare comp)

Descripción

partial_sort() realiza una ordenacion parcial de una secuencia. Para ello localiza los elementos que compondran las n primeras posiciones de la seceuncia ordenada. El resto de elementos de la sequencia permanecen en un orden indeterminado. Hay versiones que realizan esta ordenacion parcial sobre la propia secuancia y otras que crean una copia.


nth_element()

Función

template <class RandomAccessIterator>
inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                        RandomAccessIterator last)

template <class RandomAccessIterator, class Compare>
inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                 RandomAccessIterator last, Compare comp)

Descripción

nth_element() particiona la secuencia de entrada alrededor del n-esimo elemento. Dicho elemento se posiciona en la posicion que le corresponderia dentro de la secuncia ordenada. A la vez el resto de elementos quedan ordenados en mayores y menores que dicho elemento.


lower_bound()

Función

template <class ForwardIterator, class T>
inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                                   const T& value)

template <class ForwardIterator, class T, class Compare>
inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                                   const T& value, Compare comp)

Descripción

lower_bound() devuelve un iterador que indica la primera posicion de la secuencia de entrada donde podemos insertar value sin violar la relacion de orden estblecida dentro de la secuncia. Si value es mayor que todos los elementos devuelve last para indicar que para no alterar el orden se debe insertar al final.


upper_bound()

Función

template &ly;class ForwardIterator, class T>
inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
                                   const T& value)

template &ly;class ForwardIterator, class T, class Compare>
inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
                                   const T& value, Compare comp)

Descripción

upper_bound() es un algoritmo que localiza la ultima posicion disponible para un objeto en una secuencia ordenada. El iterador que devuelve indica la ultima posicion en la que podemos insertar value para no violar la relacion de orden exixtente en la secuencia.


equal_range()

Función

template <class ForwardIterator, class T>
inline pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value)

template <class ForwardIterator, class T, class Compare>
inline pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value,
            Compare comp)

Descripción

equal_range() devuelve un par de iteradores con el resultado de lower_bound y upper_bound.


binary_search()

Función

template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
                   const T& value) 
{
  ForwardIterator i = lower_bound(first, last, value);
  return i != last && !(value < *i);
}

template <class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value,
                   Compare comp) 
{
  ForwardIterator i = lower_bound(first, last, value, comp);
  return i != last && !comp(value, *i);
}

Descripción

binary_search() devulve true si value esta en la sequencia y false en otro caso.


merge()

Función

 template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result) 
{
  while (first1 != last1 && first2 != last2) 
  {
    if (*first2 < *first1) 
    {
      *result = *first2;
      ++first2;
    }
    else 
    {
      *result = *first1;
      ++first1;
    }
    ++result;
  }
  return copy(first2, last2, copy(first1, last1, result));
}

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result, Compare comp) 
{
  while (first1 != last1 && first2 != last2) 
  {
    if (comp(*first2, *first1)) 
    {
      *result = *first2;
      ++first2;
    }
    else 
    {
      *result = *first1;
      ++first1;
    }
    ++result;
  }
  return copy(first2, last2, copy(first1, last1, result));
}

Descripción

merge() combina un par de secuencias ordenadas en otra nuevas secuncia ordenada mezcla de las dos originales. Las sequencias originales deben estar ordenadas.


inplace_merge()

Función

template <class BidirectionalIterator>
inline void inplace_merge(BidirectionalIterator first,
                          BidirectionalIterator middle,
                          BidirectionalIterator last)

template <class BidirectionalIterator, class Compare>
inline void inplace_merge(BidirectionalIterator first,
                          BidirectionalIterator middle,
                          BidirectionalIterator last, Compare comp)

Descripción

inplace_merge() realiza la misma accion que merge pero asumiendo ciertas cosas acerca de las secuencias: las dos secuencias deben ocupar posiciones consecutivas de memoria.