Ordenamiento Shell sort

•Es un algoritmo de ordenación interna sencillo pero ingenioso, basado en comparaciones e intercambios.

 

•Sus resultados son radicalmente mejores que los que se pueden obtener con el método (la burbuja, selección directa  o inserción directa).

•Es un algoritmo que casi no se usa por las siguientes causas:

 

•Para su comprensión requiere un cierto esfuerzo y algo de tiempo, y se suele centrar la atención en los tres algoritmos más básicos (burbuja, selección e inserción).

•ShellSort, es el mejor algoritmo de ordenación, en los que la cantidad de memoria adicional que necesita (aparte de los propios datos a ordenar) es constante, sea cual sea la cantidad de datos a ordenar.

   

•Otros métodos de ordenación, como QuickSort, BinSort, HeapSort o RadixSort pueden pueden superar a ShellSort en cuanto al tiempo de ejecución, pero ninguno es algoritmo in-situ.

•

•Es necesario gestionar una cantidad adicional de memoria proporcional al tamaño de los datos a ordenar.

Caracteristicas 

• •Se trata de un algoritmo de ordenación interna. Al igual que cualquier otro de ordenación interna (los datos están en memoria principal)

• •Se basa en comparaciones e intercambios.

• •Necesita que el tiempo de acceso a cualquier dato sea constante,         Aplicado a otras estructuras, como listas enlazadas , etc. , el tiempo de acceso a un elemento no es constante, depende de la posición del elemento.

•

  Programa basado en C++

# include

void main (void)

{

int a[15];

int n, inc, i, j, tmp;

cout <<"De cuantos elementos es el arreglo? ";

cin >> n;

for (i=1; i<=n; i++)

{

cout <<"Introduce el elemento " <

cin >> a[i];

}

 

nc = n/2;

while (inc > 0)

{

for (i = inc +1; i<=n; i++)

{

tmp = a[i];

j=i;

while ( (j-inc) > 0 )

{

if (tmp < a[j-inc])

{

a[j]=a[j-inc];

j=j-inc;

} 

else

break;

} // fin del while //

a[j]=tmp;

} // fin del for //

inc = inc/2;

} // fin del while //

cout <

for (i=1; i<=n; i++)

cout << a[i] <

} // fin de shell sort //

 Video

•

 

•

Grafos

Un grafo es el principal objeto de estudio de la teoría de grafos. 

Es representado gráficamente como un conjunto de puntos (llamados vértices o nodos), unidos por líneas (llamadas aristas), los grafos permiten estudiar las interrelaciones entre unidades que se encuentran en interacción.

Grafo . Un grafo G consta de un conjunto de vértices o nodos V y un conjunto de arcos A, cada uno de los cuales une un vértice con otro.           

Arcos . También se llaman aristas del grafo y se representan por medio de un par de elementos , donde los elementos son los nodos que une el arco.

 Grafo Dirigido à Si los arcos tienen una dirección, se le llama grafo dirigido u orientado. En un grafo orientado cada arco se representado por un par ordenado (vi,vj)   donde el primer elemento es el nodo origen o fuente y el segundo es el nodo destino de ese arco, por lo tanto se puede decir que el arco va desde vi,  hasta vj y que vj es adyacente a vi.