The Internet belongs to everyone. Let’s keep it that way.

Protect Net Neutrality
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

Copy of Métodos de Ordenación

Explica los métodos de ordenación disponibles dentro de la programación.
by

Jorge Saavedra

on 25 September 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Copy of Métodos de Ordenación

Métodos
Ordenacion Quick-sort
Ordenación por
intercambio
Métodos de Ordenación
Ordenación por selección
Conceptos clave
(cc) photo by Metro Centric on Flickr
(cc) photo by jimmyharris on Flickr
(cc) photo by Metro Centric on Flickr
Objetivos
Conocer, distinguir, interpretar y determinar la eficiencia
de los métodos de ordenación. Es decir, el alumno
sera capaz de usar los métodos de ordenación de
manera eficaz y eficiente.
Ordenación numérica

Ordenación alfabética

Complejidad cuadrática

Ordenación por intercambio

Ordenación rápida

Ordenación por inserción

Búsqueda secuencial y binaria

Complejidad logarítmica

Ordenación por selección
Ordenación
Proceso de organizar datos
en algún orden o secuencia especifica y basado en alguna característica o criterio.
Categorías
Interna
Dentro de un mismo archivo o documento.
Externa
Interacción con otros archivos o documentos externos.
Interna
Es la clasificación de los valores según el orden creciente en memoria central: rápida.
Externa
Se guardan adecuadamente en un dispositivo externo, lo cual los hace de lento acceso.
Intercambio
Inserción
shell
Selección
Quick-sort
Binsort
Radixsort
Se le denomina por intercambio debido
a que hace una comparación del elemento
inferior de la lista con los restantes
intercambiándolos, hasta que queden
todos ordenados.
También es denominado el método burbuja.
Pasos para llevarlo acabo:
1. Comparar el primer arreglo con el segundo; si están en orden se mantiene como están ; en caso contrario , se intercambian entre si.
2. A continuación se comparan el segundo arreglo con el siguiente elemento, y realiza el paso anterior.
3. El proceso continua hasta que cada elemento del vector ha sifo comparado con sus elementos adyacentes y se han realizado los intercambios necesarios.
En términos de programación:
void ordBurbuja (long a[], int n)
{
int interruptor = 1;
int pasada, j;
for (pasada = 0; pasada < n-1 && interruptor; pasada++)
{
/* bucle externo controla la cantidad de pasadas */
interruptor = 0;
for (j = 0; j < n-pasada-1; j++)
if (a[j] > a[j+1])
{
/* elementos desordenados, es necesario intercambio */
long aux;
interruptor = 1;
aux = a[j];
a[j] = a[j+1];
a[j+1] = aux;
}
}
}
Tiene dos argumentos, el array que se va a ordenar crecientemente, y el número de elementos n. En la codificación
se supone que los elementos son de tipo entero largo.
Y como sabemos que te gusta tanto
experimentar:
Crea un programa que ordenará una lista de n
elementos determinados por el usuario
y deben de ser de tipo entero introducida
en un arreglo y posteriormente la imprime
(o visualiza) en pantalla.
Este método es basado en buscar el elemento menor y colocarlo en primera posición, y así sucesivamente.
Pasos para su utilizacion:
1. Seleccionar elemento menor.
2. Intercambiar dicho elemento con el primero.
3. Repetir esas operaciones con los elementos
restantes, hasta que quede el elemento mayor.
En terminos de programación:
void ordSeleccion (double a[], int n)
{
int indiceMenor, i, j;
/* ordenar a[0]..a[n-2] y a[n-1] en cada pasada */
for (i = 0; i < n-1; i++)
{
/* comienzo de la exploración en índice i */
indiceMenor = i;
/* j explora la sublista a[i+1]..a[n-1] */
for (j = i+1; j < n; j++)
if (a[j] < a[indiceMenor])
indiceMenor = j;
/* sitúa el elemento más pequeño en a[i] */
if (i != indiceMenor)
{
double aux = a[i];
a[i] = a[indiceMenor];
a[indiceMenor] = aux ;
}
}
}
Ordenacion por shell
Debe el nombre a su inventor D. L. Shell. Se suele denominar también ordenación por inserción con incrementos decrecientes.
Modifica los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño y con ello se consigue que la ordenación sea más rápida. Generalmente se toma como salto inicial n/2 (siendo n el número de elementos), luego se reduce el salto a la mitad en cada
repetición hasta que el salto es de tamaño 1.
Pasos para el uso de método shell
1. Dividir la lista original 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 mitad (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 que el tamaño del salto es 1.
Hablando de programación:
void ordenacionShell(double a[], int n)
{
int intervalo, i, j, k;
intervalo = n / 2;
while (intervalo > 0)
{
for (i = intervalo; i < n; i++)
{
j = i - intervalo;
while (j >= 0)
{
k = j + intervalo;
if (a[j] <= a[k])
j = -1; /* así termina el bucle, par ordenado */
else
{
double temp;
temp = a[j];
a[j] = a[k];
a[k] = temp;
j -= intervalo;
}
}
}
intervalo = intervalo / 2;
}
}
La primera etapa en el algoritmo de partición es obtener el elemento pivote; una vez que se ha seleccionado se ha de buscar el sistema para situar en la sublista izquierda todos los elementos Algoritmos de ordenación y búsqueda menores que el pivote y en la sublista derecha todos los elementos mayores que el pivote. Supongamos que todos los elementos de la lista son distintos, aunque será preciso tener en cuenta los casos en que existan elementos idénticos.
Recibe el nombre de su autor, Tony Hoare. El método se basa en dividir los n elementos de la lista a ordenar en dos partes por medio de un elemento central denominado pivote. La división se hace de tal forma que todos los elementos de la primera sublista (izquierda) son menores que todos los elementos de la segunda sublista (derecha). Las dos sublistas se ordenan entonces independientemente.
void quicksort(double a[], int primero, int ultimo)
{
int i, j, central;
double pivote;
central = (primero + ultimo)/2;
pivote = a[central];
i = primero;
j = ultimo;
do {
while (a[i] < pivote) i++;
while (a[j] > pivote) j--;
if (i<=j)
{
double tmp;
tmp = a[i];
a[i] = a[j];
a[j] = tmp; /* intercambia a[i] con a[j] */
i++;
j--;
}
}while (i <= j);
if (primero < j)
quicksort(a, primero, j);/* mismo proceso con sublista izqda */
if (i < ultimo)
quicksort(a, i, ultimo); /* mismo proceso con sublista drcha */
}
Programando:
Otros métodos importantes:
es similar al proceso típico de ordenar tarjetas de nombres (cartas de una baraja) por orden alfabético, que consiste en insertar un nombre en su posición correcta dentro de una lista o archivo que ya está ordenado.
Binsort
O clasificación por urnas, para ordenar una secuencia de n elementos siempre que se conozca algo acerca del tipo de las claves por las que se están ordenando.
Es decir, este método utiliza urnas, cada urna contiene todos los registros con una misma clave.
Radixsort
Aprovecha la estrategia de la forma más antigua de clasificación manual, consistente en hacer diversos montone de fichas, cada uno caracterizado por tener sus componentes un mismo dígito (letra, si es alfabética) en la misma posición; estos montones se recogen en orden ascendente y se reparte de nuevo en montones según el siguiente dígito de la clave.
Bibliografia
Gracias!!
Inserción
1. El primer elemento A[0] se considera ordenado; es decir, la lista inicial consta de un elemento.
2. Se inserta A[1] en la posición correcta, delante o detrás de A[0], dependiendo de que sea menor o mayor.
3. Por cada bucle o iteración i (desde i=1 hasta n-1) se explora la sublista A[i-1] . . A[0] buscando la posición correcta de inserción; a la vez se mueve hacia abajo (a la derecha en la sublista) una posición todos los elementos mayores que el elemento a insertar A[i], para dejar vacía esa posición.
4. Insertar el elemento a la posición correcta.
Pasos a Seguir:
Programando:
void ordInsercion (int [] a, int n)
{
int i, j;
int aux;
for (i = 1; i < n; i++)
{
/* índice j explora la sublista a[i-1]..a[0] buscando la
posición correcta del elemento destino, lo asigna a a[j] */
j = i;
aux = a[i];
/* se localiza el punto de inserción explorando hacia abajo */
while (j > 0 && aux < a[j-1])
{
/* desplazar elementos hacia arriba para hacer espacio */
a[j] = a[j-1];
j--;
}
a[j] = aux;
}
}
Ing. Jorge Saavedra
Full transcript