Primer Deber
FORO CALIFICADO PRIMER BIMESTRE (1p)
Estimado (a) Se le invita a participar en el foro calificado.
Objetivo: Abordar un diálogo que permita hacer un análisis de los métodos (algoritmos) de ordenación directos.
Fecha de entrega: disponible hasta las 23:55 del miércoles 22 de abril de 2015
Una vez culminado el tiempo no se calificará las participaciones fuera de fecha.
Material de Apoyo:
sección 1.2 de la guía didáctica "Operación con arreglos", capítulo
correspondiente en el texto básico y demás enlaces web relacionados con
la temática.
Metodología: Para guiar su reflexión en lo que será su intervención, lo invito a responder las siguientes preguntas:
1. ¿Cuáles son los métodos de ordenación directa en arreglos, describa cada uno?
Los métodos de ordenación interna se aplican principalmente a arreglos unidimensionales. Los principales algoritmos de ordenación interna son:
Selección: Este método consiste en buscar el elemento más pequeño del arreglo y ponerlo en primera posición; luego, entre los restantes, se busca el elemento más pequeño y se coloca en segundo lugar, y así sucesivamente hasta colocar el último elemento.
Burbuja: Consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados.
Inserción directa: En este método lo que se hace es tener una sublista ordenada de elementos del arreglo e ir insertando el resto en el lugar adecuado para que la sublista no pierda el orden. La sublista ordenada se va haciendo cada vez mayor, de modo que al final la lista entera queda ordenada.
Shell: Es una mejora del método de inserción directa, utilizado cuando el arreglo tiene un gran número de elementos. En este método no se compara a cada elemento con el de su izquierda, como en el de inserción, sino con el que está a un cierto número de lugares (llamado salto) a su izquierda. Este salto es constante, y su valor inicial es N/2 (siendo N el número de elementos, y siendo división entera). Se van dando pasadas hasta que en una pasada no se intercambie ningún elemento de sitio. Entonces el salto se reduce a la mitad, y se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así sucesivamente hasta que el salto vale 1.
Intercalación: no es propiamente un método de ordenación, consiste en la unión de dos arreglos ordenados de modo que la unión esté también ordenada. Para ello, basta con recorrer los arreglos de izquierda a derecha e ir cogiendo el menor de los dos elementos, de forma que sólo aumenta el contador del arreglo del que sale el elemento siguiente para el arreglo-suma.
Mergesort: Una técnica muy poderosa para el diseño de algoritmos es “Dividir para conquistar”. Los algoritmos de este tipo se caracterizan por estar diseñados siguiendo estrictamente las siguientes fases: • Dividir: Se divide el problema en partes más pequeñas. • Conquistar: Se resuelven recursivamente los problemas más chicos. • Combinar: Los problemas mas chicos de combinan para resolver el grande. Los algoritmos que utilizan este principio son en la mayoría de los casos netamente recursivos como es el caso de mergesort. El algoritmo de Mergesort es un ejemplo clásico de algoritmo que utiliza el principio de dividir para conquistar. Si el vector tiene más de dos elementos se lo divide en dos mitades, se invoca recursivamente al algoritmo y luego se hace una intercalación de las dos mitades ordenadas.
Ordenación rápida (quicksort): Este método se basa en la táctica “divide y vencerás”, que consiste en ir subdividiendo el arreglo en arreglos más pequeños, y ordenar éstos. Para hacer esta división, se toma un valor del arreglo como pivote, y se mueven todos los elementos menores que este pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido el arreglo. Normalmente se toma como pivote el primer elemento de arreglo, y se realizan dos búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran.
Netgrafia:
http://www.programacionfacil.com/estructura_datos_csharp/algoritmos_ordenacion.html
2. ¿Cuál sería el bucle en c++ de ordenación por BURBUJA?
//Programa Ordenamiento Burbuja v1.0
#include <iostream.h>
int i, n,aux=0;
main(){
cout<<"Ejemplo Ingresar y Presentar elementos de un ARREGLO \n";
cout<<"\nIngrese el numero de elementos: ";
scanf ("%d",&n);
int a[n];
/* Bucle para ingresar elementos */
for (i=0;i<n;i++){
cout<<"Ingrese arreglo[%d]: "+i;
cin >> a[i];
}
for (i=0;i<n;i++){
if(a[i]==a[i+1]){
a[i+1]= a[i];
}
if (a[i]>=a[i+1]){
aux=a[i];
a[i]=a[i+1];
a[i+1]=aux;
}
}
/* Bucle para recorrer y presentar los elementos originales*/
cout>> "\nLos elementos son: \n";
for (i=0;i<n;i++){
cout>> "%d ",a[i];
}
getch();
}
Basado en el ejemplo propuesto por el tutor.
