Programacion Metodos De Ordenacion

Métodos de Ordenación Elementales
Los métodos de ordenación elementales proporcionan:
* una terminología básica
* un mecanismo básico que puede extenderse a otros métodos más generales, sofisticados y con mejor desempeño.
Típicamente, los métodos de ordenación elementales tienen peor desempeño que los sofisticados, pero existen muchas aplicaciones en las que es mejor utilizar unmétodo de ordenación elemental. Por ejemplo, cuando el algoritmo se utiliza pocas veces y/o se ordenan pocos elementos.
Como regla general se tiene que los métodos elementales necesitan cerca de pasos para ordenar elementos organizados al azar.
En general, no se recomienda su uso para ordenar:
* archivos grandes
* archivos clasificados aleatoriamente.
Por su parte, métodos masavanzados pueden lograr desempeños de orden , , . Mas aún, se puede demostrar que ningún método de ordenación puede utilizar menos de comparaciones entre claves cuando éstas están organizadas al azar.
Terminología General
En el contexto de los métodos de ordenación, cada elemento de dato tiene su clave, y los métodos de ordenación trabajan ordenando los elementos de dato según sus claves. Por loregular, los métodos comparan las claves e intercambian los elementos de dato. En lugar de desplazar físicamente los elementos de datos, con frecuencia, sólo se intercambian índices, punteros o referencias. Esto se denomina ordenación indirecta.
Un método de ordenación que trabaja sobre un conjunto de datos que se encuentra en memoria (e.g., un arreglo, una lista) se dice que es un método deordenación interna. Por el contrario, si el conjunto de datos almacenados en archivos no pueden ser cargado en memoria (por ejemplo, por razones de tamaño) y el método de ordenación opera sobre los archivos, se dice que es de ordenación externa. Evidentemente, en la ordenación interna se accede a los elementos de dato más fácilmente, mientras que en la ordenación externa se accede a los elementos dedato de forma secuencial o al menos en grades bloques.
Los métodos de ordenación se pueden clasificar de acuerdo a sus requerimientos de memoria. Los métodos in situ son aquellos que requieren ninguna o muy poca memoria extra. En el otro extremo, existen métodos que requieren mucha memoria extra.
Una característica que puede ser importante es la estabilidad del método de ordenación. Unalgoritmo de ordenación es estable si elementos de dato con la misma clave conservan su orden relativo luego de su aplicación. Típicamente, los métodos elementales son estables mientras que la mayoría de los algoritmos sofisticados no lo son.
Entre los métodos de ordenación elementales están Selección e Inserción, los cuales son descritos a continuación.
Método de Ordenación por SelecciónSupongamos que tenemos un arreglo con los datos, entonces el procedimiento es como sigue:
1. se sitúa en el primer elemento (i=0).
2. se busca el elemento más pequeño de arreglo (desde i hasta el final).
3. se intercambia el elemento más pequeño con el que está en la posición i.
4. se incrementa i (i++).
Nótese que se gasta la mayor parte del tiempo en intentar en encontrar elelemento mínimo.
A continuación se presenta una implementación en Java del método de ordenación por selección:
/**
* Clase que implementa métodos de ordenación elementales.
*/
public class Sorting
{
static public void selectionSort(Comparable array[])
{// No se incluye validación de parámetro de entrada.
int min;
for (int i = 0; i < array.length; i++)
{
min = i;
for (int j = i + 1; j < array.length; j++)
{
if (array[j].compareTo(array[min]) < 0)
{...