Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

MÉTODOS DE ORDENAMIENTO SHELL

No description
by

MAYCOLN JAMEZ MUÑOZ ORTEGA

on 25 October 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of MÉTODOS DE ORDENAMIENTO SHELL

El método de Shell es una versión mejorada del método de inserción directa recibe ese nombre en honor a su autor Donald L. Shell quien lo propuso en 1959. METODO DE ORDENAMIENTO SHELL Ordenamiento por intervalos decrecientes, nombrado así debido a su inventor Donald Shell, este algoritmo ordena subgrupos de elementos separados K unidades respecto de su posición en el arreglo. El valor K es llamado intervalo. Después de que los primeros K subgrupos fueron ordenados generalmente utilizando Inserción Directa, se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K. Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa.
El método se basa en tomar como salto al principio N/2, siendo N el número de elementos, y luego se va reduciendo a la mitad en cada repetición hasta lograr un valor de 1. MÉTODO DE ORDENACIÓN SHELL O SHELL SORT 1.- Dividir la lista en n/2 grupos de dos, considerando un incremento o salto entre los elementos de n/2.

2.- Clarificar cada grupo por separado, comparando las parejas de elementos, y si no están ordenados, se intercambian.

3.- Se divide ahora la lista en la mitad de grupos (n/4), con un incremento o salto entre los elementos también (n/4), y nuevamente se clasifica cada grupo por separado.

4.- Así sucesivamente, se sigue dividiendo la lista en la mitad de grupos que en el recorrido anterior con un incremento o salto decreciente en la mitad que el salto anterior, y luego clasificando cada grupo por separado.

5.- El algoritmo termina cuando se consigue cuando el tamaño del salto es 1. PASOS A SEGUIR DE MÉTODO DE ORDENAMIENTO SHELL: Se desean ordenarse la siguiente clave del arreglo

A: 15, 67, 08, 16, 44, 27, 12, 35, 56, 21, 13, 28, 60, 36, 07, 10

Primera Pasada

Los elementos se dividen en 8 grupos:

A: 15, 67, 08, 16, 44, 27, 12, 35 | 56, 21, 13, 28, 60, 36, 07, 10

La ordenación produce:

A: 15, 21, 08, 16, 44, 27, 07, 10, 56, 67, 13, 28, 60, 36, 12, 35

Segunda Pasada

Se dividen los elementos en 4 grupos:

A: 15, 21, 08, 16 | 44, 27, 07, 10 | 56, 67, 13, 28 | 60, 36, 12, 35

La ordenación produce:

A: 15, 21, 07, 10, 44, 27, 08, 16, 56, 36, 12, 28, 60, 67, 13, 35

Tercera Pasada

Se divide los elementos 2 grupos

A: 15, 21 | 07, 10 | 44, 27 | 08, 16 | 56, 36 | 12, 28 | 60, 67 | 13, 35

La ordenación produce:

A = 07, 10, 08, 16, 12, 21, 13, 27, 15, 28, 44, 35, 56, 36, 60, 67

Cuarta Pasada

Divida los elementos en un solo grupo.

La ordenación produce:

A: 07, 08, 10, 12, 13, 15, 16, 21, 27, 28, 35, 36, 44, 56, 60, 67 EJEMPLO 1 DE LA APLICACION DEL METODO SHELL UNIVERSIDAD MINUTO DE DIOS
TECNOLOGÍA EN INFORMATICA

TRABAJO DE ESTRUCTURA DE DATOS

Presentado Por: MAYCOLN JAMEZ MUÑOZ ORTEGA

Presentado A. GERMAN MORALES

SANTIAGO DE CALI
18 DE OCTUBRE DEL AÑO 2012 PRIMERO VAMOS A DEFINIREMOS QUE ES ORDENAMIENTO ¿Qué es ordenamiento?
Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento.
Es la operación de arreglar los registros, valores o datos de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento. El ordenamiento se efectúa con base en el valor de algún campo en un registro.
El ordenamiento se efectúa con base en el valor de algún campo en un registro.
El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado. Introducción ¿CUÁNDO CONVIENE USAR UN
MÉTODO DE ORDENAMIENTO? Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.
El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente o descendente. TIPOS DE ORDENAMIENTO •Los 2 tipos de ordenamientos que se pueden realizar son: los internos y los externos.
•Los internos son aquellos en los que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder cualquier elemento sea el mismo (a[1], a[500], etc.). Por ejemplo, el Shell sort, quicksort, mergesort.
•Los externos son aquellos en los que los valores a ordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc.), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada (posición 1, posición 500, etc.). Por ejemplo, Straightmerging, Polyphasesort, Distribution of initialruns. VENTAJAS DEL SHELL No requiere memoria adicional.
Mejor rendimiento que el metodo de incercion clasico.
Fácil implementación. DESVENTAJAS DEL SHELL Implementa algo confuso
Lento
Realiza numerozas comparaciones e intercambios. GRACIAS VIDEO EJEMPLO 1 VIDEO EJEMPLO 2 CODIGO EN JAVA public static void main(String [] args) {
//arreglo
int Entrada[] = {
321, 123, 213, 234, 1, 4, 5, 6, 21, 15 };
//llamada
shellSort(Entrada);
for (int i = 0; i < Entrada.length; i++) { System.out.print(Entrada[i]+" ");
}
} public static void shellSort( int vec[]) {
// saltos
for( int p = vec.length / 2; p > 0; p = p == 2 ? 1 : (int) ( p / 2.2 ) ) { for( int i = p; i < vec.length; i++) {
int tmp = vec[i]; int j;
for(j = i; j >= p && tmp < vec[j - p]; j -= p ) {
vec[j] = vec[j - p];
} vec[j] = tmp;
}
}
} void shellSort(int numbers[], int array_size)
{
int i, j, increment, temp;
increment = 3;
while (increment > 0)
{
for (i=0; i < array_size; i++)
{
j = i;
temp = numbers[i];
while ((j >= increment) && (numbers[j-increment] > temp))
{
numbers[j] = numbers[j - increment];
j = j - increment;
}
numbers[j] = temp;
}
if (increment/2 != 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}
} CODIGO EN JAVA para i=1 hasta n-1 minimo = i;
para j=i+1 hasta n
si lista[j] < lista[minimo] entonces minimo = j /* (!) */
fin si
fin para
intercambiar(lista[i], lista[minimo])
fin para PSEUDOCODIGO
Full transcript