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

ALGORITMOS DE ORDENAMIENTO POR INTERCAMBIO

No description
by

Jacob Peña

on 11 November 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of ALGORITMOS DE ORDENAMIENTO POR INTERCAMBIO

ALGORITMOS DE ORDENAMIENTO POR INTERCAMBIO
El algoritmo del intercambio aunque es el más sencillo de implementar es uno de los mas pobres en rendimiento, se basa en la idea de buscar cada vez el menor elemento del conjunto y ubicarlo al principio del mismo, repitiendo este proceso cada vez con el conjunto sin su primer elemento (el menor del conjunto anterior), hasta llegar a un conjunto de un solo elemento que por definición ya está ordenado.

En cada paso del algoritmo se compara el primer elemento del conjunto x[i], con los demás elementos del mismo x[j] (j=i+1 .. n) y cuando x[i] es mayor que x[j], se intercambian sus valores. Cuando se termina de recorrer el arreglo el proceso nos garantiza que en x[i] está el menor elemento del conjunto.

Teniendo en cuenta que el algoritmo de ordenamiento por intercambio se realiza siempre de la misma manera independiente de los datos que estén almacenados, no existe un mejor, peor o caso promedio y su complejidad siempre será O(n^2)
ALGORITMOS DE ORDENACIÓN POR INTERCAMBIO
METODO BURBUJA
El método de ordenamiento rápido o método quicksort, es una técnica basada en otra conocida con el nombre divide y vencerás, que permite ordenar una cantidad de elementos en un tiempo proporcional a n2 en el peor de los casos o a n log n en el mejor de los casos. El algoritmo original es recursivo, como la técnica en la que se basa.
METODO QUICKSORT
Es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros.
METODO RADIX
DENTRO DEL ALGORITMO DE ORDENACIÓN POR INTERCAMBIO SE ENCUENTRAN 4 MÉTODOS:

-METODO DE LA BURBUJA
-METODO QUICKSORT
-METODO SHELLSORT
-METODO RADIX
El método de ordenación shellsort es una versión mejorada del método de ordenación por inserción directa, que se utiliza cuando el número de elementos es grande. Este método recibe su nombre gracias a su creados Donald L. Shell, también se conoce con el nombre inserción con incrementos decrecientes.

En el método de ordenación por inserción directa, cada elemento se compara con los elementos contiguos de su izquierda de uno por uno, para lograr su ordenamiento; si por ejemplo, el elemento a comparar es el más pequeño y se encuentra en la última posición del arreglo, hay que ejecutar muchas comparaciones antes de colocar el elemento en su lugar de forma definitiva.

El método de ordenación shellsort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga pasos más grandes hacia la posición que debe ocupar. Los pasos múltiples sobre los elementos se hacen con tamaños de espacio cada vez más pequeños y el último paso del método es un simple ordenamiento por inserción directa, pero para entonces, los elementos de arreglo ya casi están ordenados.

Para determinar el tamaño de los incrementos (saltos) constantes, el primero debe ser generado a partir del tamaño del arreglo entre dos, obteniendo solo su parte entera de la división o redondeando el resultado de la misma, y posteriormente ir reduciendo a la mitad el incremento en cada repetición, hasta que el incremento sea un uno.
METODO SHELL SORT
UNIDAD 6
ORDENACIÓN INTERNA O DE ARREGLOS
LA ORDENACIÓN INTERNA O DE ARREGLOS, RECIBE ESTE NOMBRE YA QUE LOS ELEMENTOS O COMPONENTES DEL ARREGLO SE ENCUENTRA EN LA MEMORIA PRINCIPAL DE LA COMPUTADORA, QUE ES LA MEMORIA RAM.
LOS MÉTODOS DE ORDENACIÓN INTERNA SE CLASIFICAN EN DOS:

- MÉTODOS DIRECTOS
- MÉTODOS LOGARÍTMICOS
MÉTODOS DIRECTOS
Son los más simples y fáciles de entender, son eficientes cuando se trata de una cantidad de datos pequeña.
EJEMPLO:
(n^2)
MÉTODOS LOGARÍTMICOS
Son más complejos, difíciles de entender y son eficientes en grandes cantidades de datos.
EJEMPLO:
(n * log n)
LOS MÉTODOS DIRECTOS MAS CONOCIDOS SON:

- Ordenación por intercambio.
- Ordenación por inserción.
- Ordenación por selección.
INTRODUCCIÓN
Como sabemos, ordenar significa reagrupar o reorganizar un conjunto de objetos en una secuencia específica y pueden ser Ascendentes (De menor a mayor) y Descendentes (De mayor a menor) y se clasifica en 2 métodos de ordenación:
- INTERNOS (De arreglos)
- EXTERNOS (De archivos)
El primer procedimiento del método de la burbuja es:

1-Generar un ciclo que inicie desde uno hasta el número de elementos del arreglo.

2-Generar un segundo ciclo dentro del anterior que inicie desde cero hasta el número de elementos del arreglo menos dos.

3-Dentro del segundo ciclo debe existir una comparación que determina el tipo de ordenamiento (ascendente o descendente) entre el primer elemento (posición generado por el segundo ciclo) y el segundo elemento (el que le sigue), si la respuesta a la condición es verdadera se realiza un intercambio entre los dos elementos.

4-Para realizar el intercambio se genera un almacenamiento temporal, el cual guarda el dato del primer elemento, el segundo elemento toma el lugar del primero y en el lugar del segundo se coloca lo que contiene el almacenamiento temporal.

Una vez que los ciclos terminan la estructura debe quedar ordenada de forma ascendente o descendente, pero este procedimiento es considerado como el pero de los casos ya que si el número de elementos de la estructura es de 100, se tienen que realizar 9900 comparaciones entes de terminar la ejecución del método.



Un segundo procedimiento del método de la burbuja es:

1-Generar un ciclo que inicie desde cero hasta el número de elementos menos dos.

2-Generar un segundo ciclo desde el valor del ciclo anterior mas uno hasta el número de elementos menos uno;

3-Dentro del segundo ciclo debe existir una comparación que determina el tipo de ordenamiento (ascendente o descendente) entre el primer elemento (posición generada por el primer ciclo) y el segundo elemento (posición generada por el segundo ciclo), si la respuesta a la condición es verdadera se realiza un intercambio entre los dos elementos.

4-Para realizar el intercambio se genera un almacenamiento temporal, el cual guarda el dato del primer elemento, el segundo elemento toma el lugar del primero y en el lugar del segundo se coloca lo que contiene el almacenamiento temporal.

Una vez que los ciclos terminan la estructura debe quedar ordenada, la diferencia con el procedimiento anterior radica en el número de comparaciones y posibles intercambios que se presentan, en este segundo procedimiento, es menor ya que cada pasada que se le da al arreglo se realiza una comparación menos que en la pasada anterior.
El tercer procedimiento del método de la burbuja es :

1-Generar un ciclo que inicie desde uno hasta el número de elementos menos uno.

2-Generar un segundo ciclo que inicie desde el número de elementos menos uno y mientras que ese valor sea mayor o igual al del ciclo anterior (con decrementos).

3-Dentro del segundo ciclo debe existir una comparación que determina el tipo de ordenamiento (ascendente o descendente) entre el primer elemento (posición generada por el segundo ciclo) y el segundo elemento (posición generada por el segundo ciclo menos uno), si la respuesta a la condición es verdadera se realiza un intercambio entre los dos elementos.

4-Para realizar el intercambio se genera un almacenamiento temporal, el cual guarda el dato del primer elemento, el segundo elemento toma el lugar del primero y en el lugar del segundo se coloca lo que contiene el almacenamiento temporal

Este tercer procedimiento es muy similar al anterior con la diferencia que el elemento que va quedando es su lugar el primero no el último como en el caso anterior.
El método de ordenación por intercambio directo o método de la burbuja, es el más simple y consiste en comparar dos elementos adyacentes para determinar si se realiza un intercambio entre los mismos, esto en caso de que el primero sea mayor que el segundo (forma ascendente) o el caso de que el primero sea menor que el segundo (forma descendente).
PROCEDIMIENTO DEL METODO BURBUJA
El procedimiento del algoritmo para el método de ordenamiento quicksort es la siguiente:

1-Debe elegir uno de los elementos del arreglo al que llamaremos pivote.

2-Debe acomodar los elementos del arreglo a cada lado del pivote, de manera que del lado izquierdo queden todos los menores al pivote y del lado derecho los mayores al pivote; considere que en este momento, el pivote ocupa exactamente el lugar que le corresponderá en el arreglo ordenado.

3-Colocado el pivote en su lugar, el arreglo queda separado en dos subarreglos, uno formado por los elementos del lado izquierdo del pivote, y otro por los elementos del lado derecho del pivote.

4-Repetir este proceso de forma recursiva para cada subarreglo mientras éstos contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.
Para elegir un pivote se puede aplicar cualquiera de las siguientes tres opciones:

1-El pivote será el primer elemento del arreglo.

2-El pivote será el elemento que esta a la mitad del arreglo. O

3-Que el pivote se elija de entre tres elementos del arreglo (cualesquiera), los cuales se deben comparar para seleccionar el valor intermedio de los tres y considerarlo como el pivote.


La forma o técnica de reacomodo de los elementos del lado izquierdo y derecho del pivote, aplica el siguiente procedimiento que es muy efectivo. Se utilizan dos índices: izq, al que llamaremos índice inicial, y der, al que llamaremos índice final. Conociendo estos elementos el algoritmo quedaría de la siguiente manera:

1-Recorrer el arreglo simultáneamente con izq y der: por la izquierda con izq (desde el primer elemento), y por la derecha con der (desde el último elemento).

2-Mientras el arreglo en su posición izq (arreglo[izq]) sea menor que el pivote, continuamos el movimiento a la derecha.

3-Mientras el arreglo en su posición der (arreglo[der]) sea mayor que el pivote, continuamos el movimiento a la izquierda.

4-Terminando los movimientos se compara los índices y si izq es menor o igual al der, se intercambian los elementos en esas posiciones y las posiciones se cambian izq a la derecha y der a la izquierda.

5-Repetir los pasos anteriores hasta que se crucen los índices (izq sea menor o igual a der).

6-El punto en que se cruzan los índices es la posición adecuada para colocar el pivote, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados).
PROCEDIMIENTO DEL METODO QUICKSORT
EJEMPLO:
Vector original:
25 57 48 37 12 92 86 33
Asignamos los elementos en colas basadas en el dígito menos significativo de cada uno de ellos.
0:
1:
2:12 92
3:33
4:
5:25
6:86
7:57 37
8:48
9:
Después de la primera pasada, la ordenación queda:
12 92 33 25 86 57 37 48
Colas basadas en el dígito más significativo.
0:
1:12
2:25
3:33 37
4:48
5:57
6:
7:
8:86
9:92
Lista ordenada:
12 25 33 37 48 57 86 92
PROCEDIMIENTO DEL METODO SHELL SORT
El procedimiento para aplicar el algoritmo de shell sort es el siguiente:

1-Generar un ciclo que se encargue de controlar el tamaño que deben tener los incrementos.

2-Este ciclo debe iniciar con la división del tamaño del arreglo entre dos.

3-Mientras que el incremento sea mayor a cero debe continuar.

4-El cambio de incremento se elige de entre dos opciones: un uno o la división del incremento anterior entre dos.
5-Un segundo ciclo dentro del anterior, controla el número de comparaciones que se deben hacer según el tamaño del incremento.

6-El control de este ciclo debe iniciar con el incremento generado anteriormente.

7-Mientras el control del ciclo sea menor que el tamaño del arreglo.
El control debe cambiar de uno en uno.
8-Un tercer ciclo dentro del segundo controla en que momento se detienen las comparaciones o se hacen los posibles intercambios entre los elementos.

9-El control de este ciclo debe iniciar con el valor del ciclo anterior.

10-Mientras que el control sea mayor o igual al incremento del primer ciclo y el elemento del arreglo de la posición del control de este ciclo menos el incremento, sea mayor que el elemento del arreglo de la posición control de este ciclo, realice los intercambios entre estas posiciones.

11-Y el control se decremente con el valor del incremento.
Full transcript