Secuencias.

Diagrama de colaboración para Secuencias.:

En Aleph una secuencia comprende toda estructura de datos que involucre a un arreglo o a una lista enlazada y algoritmos pertinentes a estas técnicas de organización de datos. Más...


Clases
class	ArrayQueue
	Pila implantada con arreglos estáticos y verificación de número de elementos. Más...
class	ArrayStack
	Pila implantada con arreglos estáticos y verificación de número de elementos. Más...
class	BitArray
	Arreglo contiguo de bits. Más...
class	Dlink
	Enlace de nodo de lista circular doblemente enlazada con nodo cabecera. Más...
class	Dlink::Iterator
	Iterador sobre enlaces. Más...
class	Dlist
	Lista doblemente enlazada de nodos sin destructor virtual. Más...
class	Dlist_Node
	Nodo sin destructor virtual de lista doblemente enlazada. Más...
class	Dlist_Node_Vtl
	Nodo con destructor virtual de lista doblemente enlazada. Más...
class	DlistVtl
	Lista doblemente enlazada de nodos con destructor virtual. Más...
class	Dnode
	Nodo perteneciente a lista doblemente enlazada circular. Más...
struct	Dnode::Iterator
	Iterador sobre los nodos de una lista doble circular. Más...
class	DynArray
	Arreglo dinámico perezoso. Más...
class	DynDlist
	Lista dinámica de elemento de tipo T. Más...
class	DynDlist::Iterator
	Iterador sobre lista dinámica. Más...
class	DynListQueue
	Cola dinámica de elementos de tipo genérico T. Más...
class	DynListStack
	Pila dinámica de elementos de tipo T. Más...
class	DynSlist
	Lista dinámica de elementos de tipo T instrumentada mediante una lista simplemente enlazada. Más...
struct	DynSlist::Iterator
	Iterador sobre listas dinámicas implementadas con listas simplemente enlazadas. Más...
class	FixedQueue
	Cola implantada con arreglos estáticos y sin verificación de número de elementos. Más...
class	FixedStack
	Pila implantada con arreglos estáticos y sin verificación de número de elementos. Más...
class	GenDlist
	Lista genérica doblemente enlazada de nodos. Más...
class	GenDlist::Iterator
	Iterador sobre los nodos de una lista doblemente enlazada. Más...
class	list
	Implementación Aleph del contenedor estándar C++ List<T>. Más...
class	list::iterator
	Iterador sobre List<T>. Más...
class	ListQueue
	Cola de nodos instrumentada con listas simplemente enlazadas. Más...
class	ListStack
	Pila de nodos simplemente enlazados. Más...
class	queue
	Implantación Aleph del contenedor estándar queue<T>. Más...
class	Slink
	Enlace simple a lista de nodos. Más...
class	Slist
	Lista simplemente enlazada de nodos conteniendo datos de tipo T. Más...
class	Slist::Iterator
	Iterador sobre lista de nodos simples. Más...
class	Snode
	Nodo simple con dato de tipo de T de una lista simplemente enlazada. Más...
class	stack
	Implantación Aleph del contenedor estándar stack<T>. Más...
class	vector
	Implantación Aleph del contenedor estándar C++ vector<T>. Más...
class	vector::iterator
	Iterador sobre un vector<T>. Más...
Definiciones
#define	DLINK_TO_TYPE(type_name, link_name)
	Genera una función de conversión de nombre de enlace doble a estructura que lo contenga.
#define	LINKNAME_TO_TYPE(type_name, link_name)
	Genera función de conversión de nombre de enlace doble a estructura que lo contenga.
#define	SLINK_TO_TYPE(type_name, link_name)
	Genera función de conversión de nombre de enlace simple a estructura que lo contenga.
Funciones
template<class T, class Compare>
int	binary_search (DynArray< T > &a, const T &x, int l, int r)
	Búsqueda binaria sobre un arreglo dinámico ordenado.
template<typename T>
int	binary_search_rec (T a[], const T &x, const int &l, const int &r)
	Búsqueda binaria recursiva sobre un arreglo ordenado.
template<class T, class Compare>
void	bubble_sort (DynArray< T > &a)
	Ordena un arreglo dinámico por el método de la burbuja.
template<typename T, class Compare>
Dnode< T > *	dlink_random_search (Dlink &list, const T &x)
	Búsqueda aleatoria de un elemento en una lista dlink.
template<class Compare>
Dlink *	dlink_random_select (Dlink &list, const size_t &i)
	Selección aleatoria del i-ésimo elemento de una lista basada sobre Dlink.
template<typename T, class Compare>
void	faster_heapsort (T *array, const size_t &n)
	Ordena un arreglo por el método heapsort mejorado.
template<typename T, class Compare>
void	heapsort (T *array, const size_t &n)
	Ordena un arreglo por el método heapsort.
template<class T>
void	heapsort (DynArray< T > &a)
	Ordena un arreglo dinámico por el método heapsort.
template<class Compare>
void	insertion_sort (Dlink &list)
	Ordena según el método de inserción una lista basada en Dlink.
template<typename T, class Compare>
void	insertion_sort (T a[], const size_t &l, const size_t &r)
	Ordena un arreglo por el método de inserción.
template<class T, class Compare>
void	insertion_sort (DynArray< T > &a)
	Ordena un arreglo dinámico por el método de inserción.
template<class T, class Compare>
void	merge_lists (Dnode< T > &l1, Dnode< T > &l2, Dnode< T > &result)
	Mezcla dos listas ordenadas de tipo Dnode en una sola.
template<class Compare>
void	merge_lists (Dlink &l1, Dlink &l2, Dlink &result)
	Mezcla dos listas ordenadas en una sola.
template<typename T, class Compare>
void	mergesort (DynDlist< T > &list)
	Ordena una lista dinámica según el método de mezcla (mergesort).
template<typename T, class Compare>
void	mergesort (Dnode< T > &list)
	Ordena una lista según el método de mezcla (mergesort).
template<class Compare>
void	mergesort (Dlink &list)
	Ordena una lista según el método de mezcla (mergesort).
template<typename T, class Compare>
void	mergesort (T a[], const int &l, const int &r)
	Ordena un arreglo por el método de mezcla.
template<typename T, class Compare>
void	quicksort (Dnode< T > &list)
	Ordena una lista por el método quicksort.
template<class Compare>
void	quicksort (Dlink &list)
	Ordena una lista enlazada por el método quicksort.
template<typename T, class Compare>
void	quicksort (T a[], const int &l, const int &r)
	Ordena un arreglo por el método quicksort sin recursión.
template<class T, class Compare>
void	quicksort (DynArray< T > &a)
	Ordena un arreglo dinámico por el método quicksort sin recursión.
template<typename T, class Compare>
void	quicksort_insertion (T a[], const int &l, const int &r)
	Ordena un arreglo por el método quicksort mejorado.
template<typename T, class Compare>
void	quicksort_rec (T a[], const int &l, const int &r)
	Ordena un arreglo por el método quicksort.
template<typename T, class Compare>
void	quicksort_rec_min (T a[], const int &l, const int &r)
	Ordena un arreglo según el método quicksort con mínimo consumo de espacio.
template<typename T, class Compare>
T *	random_search (DynDlist< T > &list, const T &x)
	Búsqueda aleatoria de un elemento en una lista dinámica.
template<typename T, class Compare_T>
Dnode< T > *	random_search (Dlink &list, const T &x)
	Búsqueda aleatoria de un elemento en una lista dlink.
template<typename T, class Compare>
int	random_search (T a[], const T &x, const int &l, const int &r)
	Búsqueda aleatoria de un elemento en un arreglo.
template<typename T, class Compare>
T *	random_select (DynDlist< T > list, const size_t &i)
	Selección aleatoria del i-ésimo elemento de una lista dinámica.
template<typename T, class Compare>
Dnode< T > *	random_select (Dlink &list, const size_t &i)
	Selección aleatoria del i-ésimo elemento de una lista basada sobre Dlink.
template<typename T, class Compare>
const T &	random_select (T a[], const int &i, const int &n)
	Selección aleatoria del i-ésimo elemento de un arreglo.
template<typename T, class Compare>
T *	search_extreme (DynDlist< T > &list)
	Búsqueda genérica de un elemento extremo en una lista de nodos (Dlist<T>).
template<class Compare>
Dlink *	search_extreme (Dlink *list)
	Búsqueda genérica de un elemento extremo en una lista de nodos Dlink.
template<typename T, class Compare>
int	search_extreme (T a[], const int &l, const int &r)
	Búsqueda genérica en un arreglo de un elemento extremo.
template<class T, class Compare>
int	search_extreme (DynArray< T > &a, const int &l, const int &r)
	Búsqueda genérica en un arreglo dinámico de un elemento extremo.
template<typename T>
T *	search_max (DynDlist< T > &list)
	Retorna el máximo elemento de la lista list.
template<typename T>
int	search_max (T a[], const int &l, const int &r)
	Retorna el máximo elemento del arreglo a entre l y r.
template<class T>
int	search_max (DynArray< T > &a, const int &l, const int &r)
	Retorna el máximo elemento del arreglo a entre l y r.
template<typename T>
T *	search_min (DynDlist< T > &list)
	Retorna el mínimo elemento de la lista list.
template<typename T>
int	search_min (T a[], const int &l, const int &r)
	Retorna el mínimo elemento del arreglo a entre l y r.
template<class Compare>
Dlink *	search_min (Dlink &list)
	Búsqueda del menor elemento en una lista.
template<class T>
int	search_min (DynArray< T > &a, const int &l, const int &r)
	Retorna el mínimo elemento del arreglo dinámico a entre l y r.
template<typename T, class Compare>
void	selection_sort (Dnode< T > &list)
	Ordena una lista enlazada de tipo Dnode<T> mediante el método de selección.
template<class Compare>
void	selection_sort (Dlink &list)
	Ordena por el método de selección una lista doblemente enlazada.
template<typename T, class Compare>
void	selection_sort (T a[], const size_t &n)
	Ordena un arreglo por el método de selección.
template<class T, class Compare>
void	selection_sort (DynArray< T > &a)
	Ordena un arreglo dinámico por el método de selección.
template<typename T, class Equal>
T *	sequential_search (DynDlist< T > &list, const T &x)
	Búsqueda secuencial sobre una lista dinámica DynDlist.
template<typename T, class Equal>
Dnode< T > *	sequential_search (Dnode< T > &list, const T &x)
	Búsqueda secuencial sobre una lista de nodos.
template<typename T, class Equal>
int	sequential_search (DynArray< T > &a, const T &x, const int &l, const int &r)
	Búsqueda secuencial sobre un arreglo dinámico.
template<typename T, class Equal>
int	sequential_search (T a[], const T &x, const int &l, const int &r)
	Búsqueda secuencial sobre un arreglo.
template<class T, class Compare>
void	shellsort (DynArray< T > &a)
	Ordena un arreglo dinámico por el método de shell.

Descripción detallada

Dentro de esta categoría, comprende los siguientes grupos de algoritmos y estructuras de datos:

Arreglos: arreglos dinámicos DynArray<T> y arreglos de bits BitArray.
Listas enlazadas: la doctrina de Aleph es manejar listas enlazadas bajos los siguientes niveles:
1. Manejo de enlaces: en este nivel se asume un enlace simple (Slink) o uno doble (Dlink) que definen enlaces de nodos de listas enlazadas simples o dobles, respectivamente.
2. Manejo de nodos: en este nivel se define la abstracción de nodo de una lista enlazada que contiene un dato de algún tipo T. A este tenor, se proveen las clases Snode<T> y Dnode<T>.
3. Listas de nodos: Slist y Dlist.
4. Listas dinámicas: DynSlist y DynDlist.
Algoritmos de inserción, búsqueda y eliminación sobre arreglos y listas.
Métodos de ordenamiento: .

Autor:: Leandro R. León (lrleon en ula punto ve)

Documentación de las definiciones

#define DLINK_TO_TYPE	(	type_name,
		link_name		)

Valor:

inline static type_name * dlink_to_##type_name(Dlink * link) \
{ \
  type_name * ptr_zero = 0; \
  size_t offset_link   = reinterpret_cast<size_t>(&(ptr_zero->link_name)); \
  char * address_type  = reinterpret_cast<char*>(link) - offset_link; \
  return reinterpret_cast<type_name *>(address_type); \
}

Este macro se utiliza cuando se tiene un dlink que es parte de una estructura y se desea obtener un apuntador a la estructura desde el enlace.

Si tenemos, por ejemplo: struct Registro { ... Dlink l; ... };

Entonces DLINK_TO_TYPE(Registro, l) generará la función:

Registro * dlink_to_type(Dlink * link), la cual recibe un apuntador Dlink al campo de un registro "Registro" y retorna el puntero al registro.

Parámetros:

	type_name	el tipo de la estructura (struct o class) que contiene al dlink.
	link_name	el nombre del campo del enlace doble dentro de la estructura.

Definición en la línea 726 del archivo dlink.H.

#define LINKNAME_TO_TYPE	(	type_name,
		link_name		)

Valor:

inline static type_name * link_name##_to_##type_name(Dlink * link) \
{ \
  type_name * ptr_zero = 0; \
  size_t offset_link   = reinterpret_cast<size_t>(&(ptr_zero->link_name)); \
  char * address_type  = reinterpret_cast<char*>(link) - offset_link; \
  return reinterpret_cast<type_name *>(address_type); \
}

El nombre de la función es literalmente el parámetro que se instancie como link_name

Este macro se utiliza cuando se tiene dos o más Dlink que son parte de una estructura y se desea obtener un apuntador a la estructura desde algunos de los enlaces.

Si tenemos, por ejemplo: struct Registro { ... Dlink l1; Dlink l2; ... };

Entonces LINKNAME_TO_TYPE(Registro, l1) y LINKNAME_TO_TYPE(Registro, l2) generará las funciones:

Registro * l1_to_type(Dlink * link), la cual recibe un apuntador al campo l1 del registro y retorna el puntero al registro.

Registro * l2_to_type(Dlink * link), la cual recibe un apuntador al campo l2 del registro y retorna el puntero al registro.

La idea es disponer de esquemas de nombramiento que prmitan hacer la distición entre los campos.

Parámetros:

	type_name	el tipo de la estructura (struct o class) que contiene al Dlink.
	link_name	el nombre del campo del enlace doble dentro de la estructura.

Definición en la línea 772 del archivo dlink.H.

#define SLINK_TO_TYPE	(	type_name,
		link_name		)

Valor:

static type_name * slink_to_type(Slink * link) \
{ \
  type_name * ptr_zero = 0; \
  size_t offset_link   = reinterpret_cast<size_t>(&(ptr_zero->link_name)); \
  char * address_type  = reinterpret_cast<char*>(link) - offset_link; \
  return reinterpret_cast<type_name *>(address_type); \
}

El nombre de la función es literalmente el parámetro que se instancie como link_name

Este macro se utiliza cuando se tiene dos o más Slink que son parte de una estructura y se desea obtener un apuntador a la estructura desde algunos de los enlaces.

Si tenemos, por ejemplo: struct Registro { ... Slink l1; Slink l2; ... };

Entonces slink_TO_TYPE(Registro, l1) y SLINK_TO_TYPE(Registro, l2) generará las funciones:

Registro * l1_to_type(Slink * link), la cual recibe un apuntador al campo l1 del registro y retorna el puntero al registro.

Registro * l2_to_type(Slink * link), la cual recibe un apuntador al campo l2 del registro y retorna el puntero al registro.

La idea es disponer de esquemas de nombramiento que prmitan hacer la distición entre los campos.

Parámetros:

	type_name	el tipo de la estructura (struct o class) que contiene al Slink.
	link_name	el nombre del campo del enlace doble dentro de la estructura.

Definición en la línea 198 del archivo slink.H.

Documentación de las funciones

int Aleph::binary_search	(	DynArray< T > &	a,
		const T &	x,
		int	l,
		int	r
	)			`[inline]`

binary_search<T,Compare>(a,x,l,r) realiza la búsqueda de x en el arreglo a comprendida entre los límites inferior l y superior r.

La rutina es genérica y utiliza dos parámetros tipo:

El tipo de dato que alberga el arreglo.
La clase de comparación.

Una versión sobrecargada binary_search_rec<T> usa por omisión, como clase de comparación, el operador relacional "menor que".

La rutina usa el algoritmo de la búsqueda binaria, lo que exige que el arreglo esté ordenado. Esta condición no se verifica en el algoritmo.

El método siempre retorna un entero comprendido entre [l..r]. Si el elemento es encontrado, entonces el valor de retorno es índice donde éste se encuentra; de lo contrario, se retorna el índice donde se insertaría x para que el arreglo estuviese ordenado.

Parámetros:

`[in]`	a	el arreglo dinámico sobre el cual realizar la búsqueda.
`[in]`	x	el elemento a buscar.
`[in]`	l	índice izquierdo de búsqueda.
`[in]`	r	índice derecho de búsqueda.

Devuelve:: índice del elemento donde se encuentra x o el índice de la posición donde se insertaría x.

Ver también:: sequential_search()

Definición en la línea 540 del archivo dyn_sort_utils.H.

Hace referencia a DynArray::access().

int binary_search_rec	(	T	a[],
		const T &	x,
		const int &	l,
		const int &	r
	)			`[inline]`

binary_search_rec<T,Compare>(a,x,l,r) realiza la búsqueda de x en el arreglo a comprendida entre los límites inferior l y superior r.

La rutina es genérica y utiliza dos parámetros tipo:

El tipo de dato que alberga el arreglo.
La clase de comparación.

Una versión sobrecargada binary_search_rec<T> usa por omisión, como clase de comparación, el operador relacional "menor que".

La rutina usa el algoritmo de la búsqueda binaria, lo que exige que el arreglo esté ordenado. Esta condición no se verifica en el algoritmo.

El método siempre retorna un entero comprendido entre [l..r]. Si el elemento es encontrado, entonces el valor de retorno es índice donde éste se encuentra; de lo contrario, se retorna el índice donde se insertaría x para que el arreglo estuviese ordenado.

Parámetros:

`[in]`	a	el arreglo sobre el cual realizar la búsqueda.
`[in]`	x	el elemento a buscar.
`[in]`	l	índice izquierdo de búsqueda.
`[in]`	r	índice derecho de búsqueda.

Devuelve:: índice del elemento donde se encuentra x o el índice de la posición donde se insertaría x.

Ver también:: sequential_search()

Definición en la línea 639 del archivo tpl_sort_utils.H.

void Aleph::bubble_sort ( DynArray< T > & a ) [inline]

bubble_sort(a) emplea el método de la burbuja para ordenar el arreglo dinámico de n elementos.

El método de la burbuja tiene un desempeño de $O(n^2)$ . Posiblemente es el método más ineficiente de todos los existentes.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada bubble_sort(DynArray<T>&a) especializa la comparación al operador "menor que" sobre el tipo T.

Parámetros:

[in,out] a el arreglo a ordenar.

Ver también:: insertion_sort() quicksort_rec() mergesort() heapsort()

Definición en la línea 126 del archivo dyn_sort_utils.H.

Hace referencia a DynArray::access(), y DynArray::size().

Dnode<T>* Aleph::dlink_random_search	(	Dlink &	list,
		const T &	x
	)			`[inline]`

dlink_random_search(list,x) se vale del algoritmo de partición del quicksort para buscar el elemento x en la lista list.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

El procedimiento tiene una complejidad esperada de $O(n \; \lg n)$ , que es mayor que la mera búsqueda secuencial, pero con el añadido de que luego de la búsqueda la lista queda parcialmente ordenada.

Parámetros:

`[in,out]`	list	lista en la cual se realiza la búsqueda; es parcialmente modificada luego de la búsqueda.
`[in]`	x	elemento a buscar.

Devuelve:: puntero al nodo contentivo del valor x si ésta se encuentra dentro en la lista; NULL de lo contrario.

Ver también:: random_search(Dlink&list,const T&x)

Definición en la línea 1310 del archivo tpl_sort_utils.H.

Hace referencia a Dlink::append(), Dlink::concat_list(), Dlink::is_empty(), Dlink::remove_next(), y Dlink::swap().

Dlink* Aleph::dlink_random_select	(	Dlink &	list,
		const size_t &	i
	)			`[inline]`

random_select(list,i) retorna el i-ésimo menor elemento contenido en la lista list según criterio de orden determinado por la clase Compare.

La rutina se sirve de la partición del quicksort para buscar la posición i en tiempo $O(n \; \lg n)$ , lo cual es un tiempo substancialmente mejor que el de la búsqueda secuencial ( $O(n^2)$ ).

Parámetros:

`[in,out]`	list	lista donde se buscará el i-ésimo elemento. La lista queda semi-ordenado a través de las sucesivas particiones que se hayan realizado.
`[in]`	i	posición que se desea acceder.

Devuelve:: puntero a Dlink correspondiente a la posición i dentro de la lista;

Definición en la línea 1505 del archivo tpl_sort_utils.H.

Hace referencia a Dlink::append(), Dlink::concat_list(), Dlink::is_empty(), y Dlink::remove_next().

void faster_heapsort	(	T *	array,
		const size_t &	n
	)			`[inline]`

faster_heapsort(array,n) emplea una versión substancialmente mejorada del heapsort para ordenar el arreglo a de n elementos.

El heapsort tiene un desempeño garantizado de $O(n \; \lg n)$ y es estable.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada faster_heapsort() especializa la comparación al operador "menor que" sobre el tipo T.

Parámetros:

`[in,out]`	array	el arreglo a ordenar.
`[in]`	n	la dimensión del arreglo.

Ver también:: insertion_sort() quicksort_rec() mergesort() heapsort()
selection_sort() heapsort()

Definición en la línea 168 del archivo tpl_arrayHeap.H.

void heapsort	(	T *	array,
		const size_t &	n
	)			`[inline]`

heapsort(array,n) emplea el método de heapsort para ordenar el arreglo a de n elementos.

El heapsort tiene un desempeño garantizado de $O(n \; \lg n)$ y es estable.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada heapsort() especializa la comparación al operador "menor que" sobre el tipo T.

Parámetros:

`[in,out]`	array	el arreglo a ordenar.
`[in]`	n	la dimensión del arreglo.

Ver también:: insertion_sort() quicksort_rec() mergesort()
selection_sort() faster_heapsort()

Definición en la línea 128 del archivo tpl_arrayHeap.H.

void Aleph::heapsort ( DynArray< T > & a ) [inline]

heapsort(a) emplea el método de heapsort para ordenar el arreglo a de n elementos.

El heapsort tiene un desempeño garantizado de $O(n \; \lg n)$ y es estable.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada heapsort() especializa la comparación al operador "menor que" sobre el tipo T.

Parámetros:

[in,out] a el arreglo a ordenar.

Ver también:: insertion_sort() quicksort_rec() mergesort()
selection_sort() faster_heapsort()

Definición en la línea 323 del archivo dyn_sort_utils.H.

Hace referencia a DynArray::access(), y DynArray::size().

void Aleph::insertion_sort ( Dlink & list ) [inline]

insertion_sort(list) ordena según el método de inserción la lista enlazada list basada en una derivación de Dlink.

El método de inserción tiene un desempeño de $O(n^2)$ .

Parámetros:

[in,out] list la lista a ordenar.

Ver también:: Dlink

Definición en la línea 603 del archivo tpl_sort_utils.H.

Hace referencia a Dlink::is_empty(), Dlink::remove_next(), y Dlink::swap().

void insertion_sort	(	T	a[],
		const size_t &	l,
		const size_t &	r
	)			`[inline]`

insertion_sort(a,l,r) emplea el método de selección para ordenar el arreglo a entre los índices l y r.

El método de inserción tiene un desempeño de $O(n^2)$ . Es un método simple, por lo que consume poco tiempo constante. En promedio realiza la mitad de los intercambios que el método de selección. Su tiempo tiende a ser lineal si el arreglo está semi-ordenado. Es un buen método para arreglos pequeños y para particiones realizadas por métodos superiores pero con mayores tiempos constantes.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada insertion_sort() especializa la comparación al operador "menor que" sobre el tipo T.

Parámetros:

`[in,out]`	a	el arreglo a ordenar.
`[in]`	l	índice izquierdo del arreglo.
`[in]`	r	índice derecho del arreglo.

Ver también:: selection_sort() quicksort_rec() mergesort() heapsort()

Definición en la línea 548 del archivo tpl_sort_utils.H.

void Aleph::insertion_sort ( DynArray< T > & a ) [inline]

insertion_sort(a) emplea el método de selección para ordenar el arreglo dinámico a.

El método de inserción tiene un desempeño de $O(n^2)$ . Es un método simple, por lo que consume poco tiempo constante. En promedio realiza la mitad de los intercambios que el método de selección. Su tiempo tiende a ser lineal si el arreglo está semi-ordenado. Es un buen método para arreglos pequeños y para particiones realizadas por métodos superiores pero con mayores tiempos constantes.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada insertion_sort() especializa la comparación al operador "menor que" sobre el tipo T.

Parámetros:

[in,out] a el arreglo a ordenar.

Ver también:: selection_sort() quicksort_rec() mergesort() heapsort()

Definición en la línea 174 del archivo dyn_sort_utils.H.

Hace referencia a DynArray::access(), y DynArray::size().

void Aleph::merge_lists	(	Dnode< T > &	l1,
		Dnode< T > &	l2,
		Dnode< T > &	result
	)			`[inline]`

merge_lists(l1,l2,result) toma dos listas ordenadas l1 y l2 y las fusiona en una sola lista ordenada result según criterio de comparación Compare.

No se verifica si las listas l1 y l2 están ordenadas. Resultados serán incorrectos si no se cumple esta premisa.

Parámetros:

`[in,out]`	l1	una lista ordenada a fusionar.
`[in,out]`	l2	una lista ordenada a fusionar.
`[out]`	result	la lista donde se colocará el resultado.

Definición en la línea 752 del archivo tpl_sort_utils.H.

void Aleph::merge_lists	(	Dlink &	l1,
		Dlink &	l2,
		Dlink &	result
	)			`[inline]`

merge_lists(l1,l2,result) toma dos listas ordenadas l1 y l2 y las fusiona en una sola lista ordenada result según criterio de comparación Compare.

No se verifica si las listas l1 y l2 están ordenadas. Resultados serán incorrectos si no se cumple esta premisa.

Parámetros:

`[in,out]`	l1	una lista ordenada a fusionar.
`[in,out]`	l2	una lista ordenada a fusionar.
`[out]`	result	la lista donde se colocará el resultado.

Definición en la línea 717 del archivo tpl_sort_utils.H.

Hace referencia a Dlink::append(), Dlink::concat_list(), Dlink::get_next(), Dlink::is_empty(), y Dlink::remove_next().

void Aleph::mergesort ( DynDlist< T > & list ) [inline]

Ordena mediante el método de mezcla (mergesort) una lista dinámica según criterio de comparación Compare.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada mergesort(DynDlist<T> & list) especializa la comparación al operador "menor que" sobre el tipo T.

Este método tiene un desempeño determinista de $O(n \; \lg n)$ y un consumo de espacio de $O(1)$ . Es un muy buen método para listas.

Parámetros:

[in,out] list la lista a ser ordenada.

Ver también:: quicksort(DynDlist<T> & list)

Definición en la línea 845 del archivo tpl_sort_utils.H.

void Aleph::mergesort ( Dnode< T > & list ) [inline]

Ordena mediante el método de mezcla (mergesort) una lista basada en Dnode<T>, según criterio de comparación Compare.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada mergesort(Dnode<T> & list) especializa la comparación al operador "menor que" sobre el tipo T.

Este método tiene un desempeño determinista de $O(n \; \lg n)$ y un consumo de espacio de $O(1)$ . Es un muy buen método para listas.

Parámetros:

[in,out] list la lista a ser ordenada.

Ver también:: mergesort(Dlink & list) quicksort(Dnode<T>)

Definición en la línea 810 del archivo tpl_sort_utils.H.

void Aleph::mergesort ( Dlink & list ) [inline]

Ordena mediante el método de mezcla (mergesort) una lista basada en Dlink, según criterio de comparación Compare.

Este método tiene un desempeño determinista de $O(n \; \lg n)$ y un consumo de espacio de $O(1)$ . Es un muy buen método para listas.

Parámetros:

[in,out] list la lista a ser ordenada.

Ver también:: mergesort(Dnode<T> & list)

Definición en la línea 772 del archivo tpl_sort_utils.H.

Hace referencia a Dlink::is_unitarian_or_empty(), y Dlink::split_list().

void mergesort	(	T	a[],
		const int &	l,
		const int &	r
	)			`[inline]`

mergesort(a,l,r) ordena el arreglo a entre los índices l y r según el método de mezcla según criterio de comparación Compare.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada mergesort() especializa la comparación al operador "menor que" sobre el tipo T.

Este método tiene un desempeño de $O(n \; \lg n)$ , pero un consumo de espacio de $O(n)$ .

Parámetros:

`[in,out]`	a	el arreglo a ordenar.
`[in]`	l	índice inferior.
`[in]`	r	índice superior.

Ver también:: selection_sort() insertion_sort() quicksort_rec() heapsort()

Definición en la línea 685 del archivo tpl_sort_utils.H.

void Aleph::quicksort ( Dnode< T > & list ) [inline]

quicksort(list) ordena una lista mediante el método quicksort según criterio de comparación Compare.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada quicksort() especializa la comparación al operador "menor que" sobre el tipo T.

Este método tiene un desempeño esperado de $O(n \; \lg n)$ y es considerado el método de ordenamiento más veloz.

Esta primitiva puede usarse para listas de tipo Dlist y DynDlist.

Parámetros:

[in,out] list la lista a ordenar.

Ver también:: Dnode Dlist DynDlist

Definición en la línea 1123 del archivo tpl_sort_utils.H.

Referenciado por Map_Matrix_Graph::copy_list_graph().

void Aleph::quicksort ( Dlink & list ) [inline]

quicksort(list) ordena una lista según el método quicksort según criterio de comparación Compare.

Este método tiene un desempeño esperado de $O(n \; \lg n)$ y es considerado el método de ordenamiento más veloz.

Parámetros:

[in,out] list la lista a ordenar.

Definición en la línea 1072 del archivo tpl_sort_utils.H.

Hace referencia a Dlink::append(), Dlink::concat_list(), Dlink::is_empty(), Dlink::is_unitarian_or_empty(), y Dlink::remove_next().

void quicksort	(	T	a[],
		const int &	l,
		const int &	r
	)			`[inline]`

quicksort_rec(a,l,r) ordena el arreglo a entre los índices l y r según el método quicksort según criterio de comparación Compare.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada quicksort() especializa la comparación al operador "menor que" sobre el tipo T.

Este método tiene un desempeño esperado de $O(n \; \lg n)$ y es considerado el método de ordenamiento más veloz.

Esta versión de quicksort puede ocupar espacio $O(n)$ . Utilice quicksort_rec_min() si se desea garantizar un consumo máximo de espacio de $O(\lg n)$ en detrimento de un poco más de tiempo constante.

El quicksort es un método probabilístico. En un muy mal caso -muy mala suerte- puede degradarse a $O(n^2)$ . Para paliar, en la medida de la suerte, los malos casos, use quicksort_insertion() que ejecuta heurísticas para paliar los malos casos e invoca al método de inserción para particiones del arreglo pequeñas.

Parámetros:

`[in,out]`	a	el arreglo a ordenar.
`[in]`	l	índice inferior.
`[in]`	r	índice superior.

Ver también:: selection_sort() insertion_sort() mergesort() heapsort()
quicksort_rec_min() quicksort_insertion() quicksort_rec()

Definición en la línea 1024 del archivo tpl_sort_utils.H.

Hace referencia a FixedStack::pop(), FixedStack::push(), y FixedStack::size().

void Aleph::quicksort ( DynArray< T > & a ) [inline]

quicksort(a) ordena el arreglo dinámico según el método quicksort según criterio de comparación Compare.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada quicksort() especializa la comparación al operador "menor que" sobre el tipo T.

Este método tiene un desempeño esperado de $O(n \; \lg n)$ y es considerado el método de ordenamiento más veloz.

Esta versión de quicksort ocupa espacio máximo de $O(\lg n)$ .

El quicksort es un método probabilístico. En un muy mal caso -muy mala suerte- puede degradarse a $O(n^2)$ . Para paliar, en la medida de la suerte, los malos casos, use quicksort_insertion() que ejecuta heurísticas para paliar los malos casos e invoca al método de inserción para particiones del arreglo pequeñas.

Parámetros:

[in,out] a el arreglo a ordenar.

Ver también:: selection_sort() insertion_sort() heapsort()
quicksort_rec_min() quicksort_insertion() quicksort_rec()

Definición en la línea 422 del archivo dyn_sort_utils.H.

Hace referencia a FixedStack::is_empty(), FixedStack::pop(), y DynArray::size().

void quicksort_insertion	(	T	a[],
		const int &	l,
		const int &	r
	)			`[inline]`

quicksort_insertion(a,l,r) ordena el arreglo a entre los índices l y r según el método quicksort según criterio de comparación Compare.

El procedimiento combina diversas técnicas para acelerar el ordenamiento y a la vez evitar degradación por malos casos.

Los malos casos son tratados mediante una selección del pivote consistente de la mediana entre l, r y el centro de la partición.

Para asegurar un consumo máximo de pila de $O(\lg n)$ , el método siempre procede recursivamente a ordenar la partición más pequeña.

Cuando la partición alcanza un tamaño menor o igual a la constante global Aleph::Insertion_Threshold, entonces la partición es ordenada por el método de inserción, el cual es más rápido que el quicksort para tamaños pequeños.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada quicksort_insertion() especializa la comparación al operador "menor que" sobre el tipo T.

Este método tiene un desempeño esperado de $O(n \; \lg n)$ y es considerado el método de ordenamiento más veloz.

Parámetros:

`[in,out]`	a	el arreglo a ordenar.
`[in]`	l	índice inferior.
`[in]`	r	índice superior.

Ver también:: insertion_sort() mergesort() heapsort()
quicksort_rec_min() quicksort_insertion() quicksort()

Definición en la línea 1174 del archivo tpl_sort_utils.H.

void quicksort_rec	(	T	a[],
		const int &	l,
		const int &	r
	)			`[inline]`

quicksort_rec(a,l,r) ordena el arreglo a entre los índices l y r según el método quicksort según criterio de comparación Compare.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada quicksort() especializa la comparación al operador "menor que" sobre el tipo T.

Este método tiene un desempeño esperado de $O(n \; \lg n)$ y es considerado el método de ordenamiento más veloz.

Esta versión de quicksort puede ocupar espacio $O(n)$ . Utilice quicksort_rec_min() si se desea garantizar un consumo máximo de espacio de $O(\lg n)$ en detrimento de un poco más de tiempo constante.

El quicksort es un método probabilístico. En un muy mal caso -muy mala suerte- puede degradarse a $O(n^2)$ . Para paliar, en la medida de la suerte, los malos casos, use quicksort_insertion() que ejecuta heurísticas para paliar los malos casos e invoca al método de inserción para particiones del arreglo pequeñas.

Parámetros:

`[in,out]`	a	el arreglo a ordenar.
`[in]`	l	índice inferior.
`[in]`	r	índice superior.

Ver también:: selection_sort() insertion_sort() mergesort() heapsort()
quicksort_rec_min() quicksort_insertion() quicksort()

Definición en la línea 919 del archivo tpl_sort_utils.H.

void quicksort_rec_min	(	T	a[],
		const int &	l,
		const int &	r
	)			`[inline]`

El quicksort puramente recursivo puede consumir pila proporcional al tamaño del arreglo a ordenar. Para evitar este problema, en detrimento de un ligero coste de ejecución, quicksort_rec_min() siempre ordena de primero la partición más pequeña. Por los demás, las mismas consideraciones que para quicksort_rec() aplican.

Parámetros:

`[in,out]`	a	el arreglo a ordenar.
`[in]`	l	índice inicial por donde se ordena.
`[in]`	r	índice final por donde se ordena.

Ver también:: quicksort_rec() quicksort() quicksort_insertion()

Definición en la línea 949 del archivo tpl_sort_utils.H.

T * random_search	(	DynDlist< T > &	list,
		const T &	x
	)			`[inline]`

random_search(list,x) se vale del algoritmo de partición del quicksort para buscar el elemento x en la lista dinámica list.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

El procedimiento tiene una complejidad esperada de $O(n \; \lg n)$ , que es mayor que la mera búsqueda secuencial, pero con el añadido de que luego de la búsqueda la lista queda parcialmente ordenada.

Una especialización usa la relación "menor que" como criterio de comparación y ahorra la escritura de esa clase.

Parámetros:

`[in,out]`	list	lista dinámica en la cual se realiza la búsqueda; es parcialmente modificada luego de la búsqueda.
`[in]`	x	elemento a buscar.

Devuelve:: puntero x dentro de la lista si ésta se encuentra dentro de ella; NULL de lo contrario.

Ver también:: DynDlist

Definición en la línea 1419 del archivo tpl_sort_utils.H.

Referenciado por Aleph::random_search().

Dnode< T > * random_search	(	Dlink &	list,
		const T &	x
	)			`[inline]`

random_search(list,x) se vale del algoritmo de partición del quicksort para buscar el elemento x en la lista list.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

El procedimiento tiene una complejidad esperada de $O(n \; \lg n)$ , que es mayor que la mera búsqueda secuencial, pero con el añadido de que luego de la búsqueda la lista queda parcialmente ordenada.

Una especialización usa la relación "menor que" como criterio de comparación y ahorra la escritura de esa clase.

Parámetros:

`[in,out]`	list	lista en la cual se realiza la búsqueda; es parcialmente modificada luego de la búsqueda.
`[in]`	x	elemento a buscar.

Devuelve:: puntero al nodo contentivo del valor x si ésta se encuentra dentro en la lista; NULL de lo contrario.

Ver también:: dlink_random_search

Definición en la línea 1379 del archivo tpl_sort_utils.H.

int random_search	(	T	a[],
		const T &	x,
		const int &	l,
		const int &	r
	)			`[inline]`

random_search(a,x,l,r) se vale del algoritmo de partición del quicksort para buscar el elemento x en el arreglo a comprendido entre los límites l y r.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

El procedimiento tiene una complejidad esperada de $O(n \; \lg n)$ , que es mayor que la mera búsqueda secuencial, pero con el añadido de que luego de la búsqueda el arreglo queda parcialmente ordenado y, puesto que la selección del pivote es la mediana entre l, r y el centro del arreglo, la búsqueda tiende a ser lineal a medida que se hacen más búsquedas aleatorias.

Parámetros:

`[in,out]`	a	arreglo a buscar; es parcialmente modificado luego de la búsqueda.
`[in]`	x	elemento a buscar.
`[in]`	l	índice inferior de comienzo de la búsqueda.
`[in]`	r	índice superior de término de la búsqueda.

Devuelve:: índice de una entrada del arreglo contentiva del valor x si ésta se encuentra dentro del arreglo; Not_Found (por general -1) de lo contrario.

Ver también:: sequential_search() binary_search_rec()

Definición en la línea 1265 del archivo tpl_sort_utils.H.

Hace referencia a Aleph::random_search().

T * random_select	(	DynDlist< T >	list,
		const size_t &	i
	)			`[inline]`

random_select(list,i) retorna el i-ésimo menor elemento contenido en la lista dinámica list.

La rutina se sirve de la partición del quicksort para buscar la posición i en tiempo $O(n \; \lg n)$ , lo cual es un tiempo substancialmente mejor que el de la búsqueda secuencial ( $O(n^2)$ ).

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión especializada implementa la relación "menor que".

Parámetros:

`[in,out]`	list	lista dinámica donde se buscará el i-ésimo elemento. La lista queda semi-ordenado a través de las sucesivas particiones que se hayan realizado.
`[in]`	i	posición que se desea acceder.

Devuelve:: puntero al elemento de la lista dinámica correspondiente a la posición i dentro de la lista; NULL si i está fuera de rango.

Definición en la línea 1616 del archivo tpl_sort_utils.H.

Dnode< T > * random_select	(	Dlink &	list,
		const size_t &	i
	)			`[inline]`

random_select(list,i) retorna el i-ésimo menor elemento contenido en la lista list.

La rutina se sirve de la partición del quicksort para buscar la posición i en tiempo $O(n \; \lg n)$ , lo cual es un tiempo substancialmente mejor que el de la búsqueda secuencial ( $O(n^2)$ ).

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión especializada implementa la relación "menor que".

Parámetros:

`[in,out]`	list	lista donde se buscará el i-ésimo elemento. La lista queda semi-ordenado a través de las sucesivas particiones que se hayan realizado.
`[in]`	i	posición que se desea acceder.

Devuelve:: puntero a Dlink correspondiente a la posición i dentro de la lista; NULL si i está fuera de rango.

Definición en la línea 1578 del archivo tpl_sort_utils.H.

const T & random_select	(	T	a[],
		const int &	i,
		const int &	n
	)			`[inline]`

random_select(a,i,n) retorna el i-ésimo menor elemento contenido en el arreglo a de dimensión n.

La rutina se sirve de la partición del quicksort para buscar la posición i en tiempo $O(n \; \lg n)$ , lo cual es un tiempo substancialmente mejor que el de la búsqueda secuencial ( $O(n^2)$ ).

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión especializada emplea la relación "menor que" como criterio de comparación.

Parámetros:

`[in,out]`	a	arreglo donde se buscará el i-ésimo elemento. El arreglo queda semi-ordenado a través de las sucesivas particiones que se hayan realizado.
`[in]`	i	posición que se desea acceder.
`[in]`	n	dimensión del arreglo

Excepciones:

out_of_range

si i es mayor o igual a n.

Definición en la línea 1471 del archivo tpl_sort_utils.H.

T * search_extreme ( DynDlist< T > & list ) [inline]

search_extreme(list) busca secuencialmente en la lista de nodos list el elemento extremo, mínimo o máximo según el criterio de comparación Compare.

Una versión especializada realiza la búsqueda del mínimo.

Parámetros:

[in] list la lista sobre la cual realizar la búsqueda.

Devuelve:: puntero al nodo contentivo del elemento extremo.

Nota:: No se verifica si la lista está vacía.

Definición en la línea 488 del archivo tpl_sort_utils.H.

Hace referencia a Dnode::get_data().

Dlink* Aleph::search_extreme ( Dlink * list ) [inline]

search_extreme(list) busca secuencialmente en la lista de nodos list el elemento extremo, mínimo o máximo según el criterio de comparación Compare.

Una versión especializada realiza la búsqueda del mínimo.

Parámetros:

[in] list la lista sobre la cual realizar la búsqueda.

Devuelve:: puntero al nodo contentivo del elemento extremo.

Nota:: No se verifica si la lista está vacía.

Definición en la línea 443 del archivo tpl_sort_utils.H.

Hace referencia a Dlink::Iterator::get_current(), Dlink::Iterator::has_current(), y Dlink::Iterator::next().

int search_extreme	(	T	a[],
		const int &	l,
		const int &	r
	)			`[inline]`

search_extreme(a, l, r) busca secuencialmente en el arreglo a, entre los índices l y r, el elemento extremo, mínimo o máximo según el criterio de comparación Compare.

Una versión especializada realiza la búsqueda del mínimo.

Parámetros:

`[in]`	a	el arreglo sobre el cual realizar la búsqueda.
`[in]`	l	índice de comienzo de la búsqueda.
`[in]`	r	índice de término de la búsqueda.

Devuelve:: índice contentivo del extremo.

Nota:: No se verifica si la secuencia está vacía.

Definición en la línea 394 del archivo tpl_sort_utils.H.

int Aleph::search_extreme	(	DynArray< T > &	a,
		const int &	l,
		const int &	r
	)			`[inline]`

search_extreme(a, l, r) busca secuencialmente en el arreglo a, entre los índices l y r, el elemento extremo, mínimo o máximo según el criterio de comparación Compare.

Una versión especializada realiza la búsqueda del mínimo.

Parámetros:

`[in]`	a	el arreglo sobre el cual realizar la búsqueda.
`[in]`	l	índice de comienzo de la búsqueda.
`[in]`	r	índice de término de la búsqueda.

Devuelve:: índice contentivo del extremo.

Nota:: No se verifica si la secuencia está vacía.

Definición en la línea 475 del archivo dyn_sort_utils.H.

Hace referencia a DynArray::access().

Dlink* Aleph::search_min ( Dlink & list ) [inline]

search_min(list) sobre una lista derivada de Dlink barre secuencialmente toda la lista en búsqueda del mínimo elemento.

La rutina requiere el parámetro tipo Compare que instrumenta la comparación entre los miembros de la lista. Compare se invoca como Compare()(l1,l2), donde l1 y l2 son dos enlaces de tipo Dlink. El usuario es responsable de instrumentar adecuadamente Compare()() de modo que se accedan los campos de interés y se efectúe la comparación.

Parámetros:

[in] list la lista sobre la cual se desea buscar el mínimo.

Devuelve:: puntero al nodo que contiene el menor elemento.

Definición en la línea 119 del archivo tpl_sort_utils.H.

Hace referencia a Dlink::Iterator::get_current(), Dlink::Iterator::has_current(), y Dlink::Iterator::next().

void Aleph::selection_sort ( Dnode< T > & list ) [inline]

Ordena la lista list, con nodos de tipo Dnode<T> según el método de selección.

El método de selección tiene un desempeño de $O(n^2)$ . Debido a su simplicidad de implantación su coste constante es bajo, por lo que es un buen método para arreglos de dimensión muy pequeña.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada selection_sort() especializa la comparación al operador "menor que" sobre el tipo T.

Parámetros:

[in,out] list ka lista a ser ordenada.

Definición en la línea 204 del archivo tpl_sort_utils.H.

void Aleph::selection_sort ( Dlink & list ) [inline]

selection_sort(list) sobre una lista derivada de Dlink ordena mediante el método de selección la lista list.

La rutina requiere el parámetro tipo Compare que instrumenta la comparación entre los miembros de la lista. Compare se invoca como Compare()(l1,l2), donde l1 y l2 son dos enlaces de tipo Dlink. El usuario es responsable de instrumentar adecuadamente Compare()() de modo que se accedan los campos de interés y se efectúe la comparación.

Parámetros:

[in,out] list lista a ser ordenada.

Definición en la línea 151 del archivo tpl_sort_utils.H.

Hace referencia a Dlink::append(), Dlink::del(), Dlink::is_empty(), y Dlink::swap().

void selection_sort	(	T	a[],
		const size_t &	n
	)			`[inline]`

selection_sort(a,n) emplea el método de selección para ordenar el arreglo a de n elementos.

El método de selección tiene un desempeño de $O(n^2)$ . Debido a su simplicidad de implantación, su coste constante es bajo, por lo que es un buen método para arreglos de dimensión muy pequeña.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada selection_sort() especializa la comparación al operador "menor que" sobre el tipo T.

Parámetros:

`[in,out]`	a	el arreglo a ordenar.
`[in]`	n	la dimensión del arreglo.

Ver también:: insertion_sort() quicksort_rec() mergesort() heapsort()

Definición en la línea 81 del archivo tpl_sort_utils.H.

void Aleph::selection_sort ( DynArray< T > & a ) [inline]

selection_sort(a) emplea el método de selección para ordenar el arreglo dinámico de n elementos.

El método de selección tiene un desempeño de $O(n^2)$ . Debido a su simplicidad de implantación, su coste constante es bajo, por lo que es un buen método para arreglos de dimensión muy pequeña.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada selection_sort(DynArray<T>&a) especializa la comparación al operador "menor que" sobre el tipo T.

Parámetros:

[in,out] a el arreglo a ordenar.

Ver también:: insertion_sort() quicksort_rec() mergesort() heapsort()

Definición en la línea 78 del archivo dyn_sort_utils.H.

Hace referencia a DynArray::access(), y DynArray::size().

T * sequential_search	(	DynDlist< T > &	list,
		const T &	x
	)			`[inline]`

sequential_search(list,x) busca secuencialmente, en la lista dinámica list (DynDlist<T>) la primera ocurrencia de x.

La función maneja dos parámetros tipo:

T: el tipo de datos que alberga el arreglo.
Equal: clase comparación entre los elementos.

Una versión sobrecargada de sequential_search() se especializa con criterio de comparación la relación "menor que" para el tipo T.

Parámetros:

`[in]`	list	la lista dinámica sobre el cual se realiza la búsqueda.
`[in]`	x	el elemento a buscar.

Devuelve:: puntero al primer elemento con valor igual a x; NULL de lo contrario.

Ver también:: DynDlist

Definición en la línea 366 del archivo tpl_sort_utils.H.

Hace referencia a Dnode::get_data().

Dnode<T>* Aleph::sequential_search	(	Dnode< T > &	list,
		const T &	x
	)			`[inline]`

sequential_search(list,x) busca secuencialmente, en la lista de nodos de tipo Dnode<T> list la primera ocurrencia de x.

La función maneja dos parámetros tipo:

T: el tipo de datos que alberga el arreglo.
Equal: clase comparación entre los elementos.

Una versión sobrecargada de sequential_search() se especializa con criterio de comparación la relación "menor que" para el tipo T.

Parámetros:

`[in]`	list	la lista sobre el cual se realiza la búsqueda.
`[in]`	x	el elemento a buscar.

Devuelve:: puntero al primer nodo que contiene el elemento x; NULL de lo contrario.

Ver también:: Dnode

Definición en la línea 326 del archivo tpl_sort_utils.H.

Hace referencia a Dnode::get_data().

int Aleph::sequential_search	(	DynArray< T > &	a,
		const T &	x,
		const int &	l,
		const int &	r
	)			`[inline]`

sequential_search(a,x,l,r) busca secuencialmente, en el arreglo a, entre los índices l y r, respectivamente, la primera ocurrencia de x.

La función maneja dos parámetros tipo:

T: el tipo de datos que alberga el arreglo.
Equal: clase comparación entre los elementos.

Esta versión sobre arreglos dinámicos salta las posiciones que con certeza no han sido escritas. Sin embargo, tómese en consideración que, según el tamaño del bloque, pueden haber entradas no escritas pero circunscritas en direcciones de memoria válidas. En este sentido, es posible que dentro de aquella clase de entradas se encuentre un elemento con valor x.

Una versión sobrecargada de sequential_search() se especializa con criterio de comparación la relación "menor que" para el tipo T.

Parámetros:

`[in]`	a	el arreglo dinámico sobre el cual se realiza la búsqueda.
`[in]`	x	el elemento a buscar.
`[in]`	l	índice izquierdo donde comienza la búsqueda.
`[in]`	r	índice derecho donde termina la búsqueda.

Devuelve:: índice de la primera posición en arreglo que contiene el elemento x; -1 de lo contrario.

Nota:: La búsqueda no puede distinguir si una entrada válida ha sido escrita o no. La programación de la clase Equal puede considerar un valor especial que represente que la entrada no ha sido escrita. Se garantiza que entrada que no haya sido mapeada en un bloque no será accedida.

Ver también:: DynArray

Definición en la línea 281 del archivo tpl_sort_utils.H.

Hace referencia a DynArray::access(), y DynArray::exist().

int sequential_search	(	T	a[],
		const T &	x,
		const int &	l,
		const int &	r
	)			`[inline]`

sequential_search(a,x,l,r) busca secuencialmente, en el arreglo a, entre los índices l y r, respectivamente, la primera ocurrencia de x.

La función maneja dos parámetros tipo:

T: el tipo de datos que alberga el arreglo.
Equal: clase comparación entre los elementos.

Una versión sobrecargada de sequential_search() se especializa con criterio de comparación la relación "menor que" para el tipo T.

Parámetros:

`[in]`	a	el arreglo sobre el cual se realiza la búsqueda.
`[in]`	x	el elemento a buscar.
`[in]`	l	índice izquierdo donde comienza la búsqueda.
`[in]`	r	índice derecho donde termina la búsqueda.

Devuelve:: índice de la primera posición en arreglo que contiene el elemento x; -1 de lo contrario.

Definición en la línea 236 del archivo tpl_sort_utils.H.

void Aleph::shellsort ( DynArray< T > & a ) [inline]

shellsort(a) emplea el método de selección para ordenar el arreglo dinámico a.

El método shell tiende a un desempeño de $O(n^2)$ , pero en la práctica es considerablemente menor.

El método emplea dos parámetros tipo:

T: el tipo de elementos que tiene el arreglo.
Compare: clase de comparación.

Una versión sobrecargada shellsort(DynArray<T>&a) especializa la comparación al operador "menor que" sobre el tipo T.

Parámetros:

[in,out] a el arreglo a ordenar.

Ver también:: selection_sort() quicksort_rec() mergesort() heapsort()

Definición en la línea 219 del archivo dyn_sort_utils.H.

Hace referencia a DynArray::access(), y DynArray::size().

Secuencias.

Clases

Definiciones

Funciones

Descripción detallada

Documentación de las definiciones

Documentación de las funciones