Introducción

              

Java

Java es un lenguaje de programación de propósito general, concurrente, orientado a objetos que fue diseñado específicamente para tener tan pocas dependencias de implementación como fuera posible. Su intención es permitir que los desarrolladores de aplicaciones escriban el programa una vez y lo ejecuten en cualquier dispositivo (conocido en inglés como WORA, o "write once, run anywhere"), lo que quiere decir que el código que es ejecutado en una plataforma no tiene que ser recompilado para correr en otra. Java es, a partir de 2012, uno de los lenguajes de programación más populares en uso, particularmente para aplicaciones de cliente-servidor de web, con unos 10 millones de usuarios reportados.

El lenguaje de programación Java fue originalmente desarrollado por James Gosling de Sun Microsystems (la cual fue adquirida por la compañía Oracle) y publicado en 1995 como un componente fundamental de la plataforma Java de Sun Microsystems. Su sintaxis deriva en gran medida de C y C++, pero tiene menos utilidades de bajo nivel que cualquiera de ellos. Las aplicaciones de Java son generalmente compiladas a bytecode (clase Java) que puede ejecutarse en cualquier máquina virtual Java (JVM) sin importar la arquitectura de la computadora subyacente.

Ordenamiento de vectores

En la programación, en la cual utilizamos código fuente se suele utilizar lo que se denomina vectores, que se define como una zona de almacenamiento continuo, que contiene una serie de elementos del mismo tipo, los elementos del vector, desde el punto de vista lógico un vector se puede ver como un conjunto de elementos ordenados en fila o en forma de columna. A su vez en muchas ocasiones se requiere de su ordenamiento, dependiendo del uso que requiera el mismo, para esto se han creado varios métodos para lograr dicho objetivo como son los siguientes:

• Método de Burbuja.
• Método de Inserción.
• Método de bisección.
• Método de Selección
• Método Shell.
• Método Quickshort.

Método de burbuja.

La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

                               

Pseudocódigo

public static void burbuja(int [] A)
{

 int i, j, aux;
 for(i=0;i<A.length-1;i++)
 for(j=0;j<A.length-i-1;j++)

        if(A[j+1]<A[j])
            {
              aux=A[j+1];
              A[j+1]=A[j];
              A[j]=aux;
            }
}

                                         

Método de inserción.

El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.

Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

                                   

Pseudicódigo

algoritmo insercion( A : array de n elementos indizados de 1 a n)
variables: enteros i,j, temporal
//estas son las pasadas, desde 2 hasta n
//en cada una intentaremos encontrar la posición
//relativa del elemento i entre los anteriores
para i desde 2 hasta n
j=i-1
//vamos "descendiendo" el elemento
//haciendo intercambios
mientras (j>=1) Y (A[j]>A[j+1]) hacer
//intercambio de la posicion j y la siguiente
temporal=A[j+1]
A[j+1]=A[j]
A[j]=temporal
j=j-1
fin mientras
fin para
fin algoritmo

                             

Método de Selección

El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n^2) operaciones para ordenar una lista de n elementos.

Este algoritmo mejora ligeramente el algoritmo de la burbuja. En el caso de tener que ordenar un vector de enteros, esta mejora no es muy sustancial, pero cuando hay que ordenar un vector de estructuras más complejas, la operación intercambiar() sería más costosa en este caso. Este algoritmo realiza muchas menos operaciones intercambiar() que el de la burbuja, por lo que lo mejora en algo. Si la línea comentada con (!) se sustituyera por intercambiar(lista[i], lista[j]) tendríamos una versión del algoritmo de la burbuja (naturalmente eliminando el orden intercambiar del final).

Otra desventaja de este algoritmo respecto a otros como el de burbuja o de inserción directa es que no mejora su rendimiento cuando los datos ya están ordenados o parcialmente ordenados. Así como, por ejemplo, en el caso de la ordenación de burbuja se requeriría una única pasada para detectar que el vector ya está ordenado y finalizar, en la ordenación por selección se realizarían el mismo número de pasadas independientemente de si los datos están ordenados o no.

Pseudocódigo para ordenar una lista de n elementos indexados desde el 1.

para i=1 hasta n-1
mínimo = i;
para j=i+1 hasta n
si lista[j] < lista[mínimo] entonces
mínimo = j /* (!) */
fin si
fin para
intercambiar(lista[i], lista[mínimo])
fin para

Ordenamiento Shell.

El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementación con un rendimiento de O(n log2 n) en el peor caso. Esto es mejor que las O(n2) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n). Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.

El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:

El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".

El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.

El algoritmo Shell sort 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 su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.

Pseudocódigo

public static void shell(int A[]){
int salto, aux, i;
boolean cambios;
for(salto=A.length/2; salto!=0; salto/=2){
cambios=true;
while(cambios){ // Mientras se intercambie algún elemento
cambios=false;
for(i=salto; i< A.length; i++) // se da una pasada
if(A[i-salto]>A[i]){ // y si están desordenados
aux=A[i]; // se reordenan
A[i]=A[i-salto];
A[i-salto]=aux;
cambios=true; // y se marca como cambio.
}
}
}

                                                   

Método Quicksort

El ordenamiento rápido (quicksort en inglés) es un algoritmo creado por el científico británico en computación C. A. R. Hoare basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

El algoritmo fundamental

• Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote. 

• Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

• La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha. 

• Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

• En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).

• En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.

• En el caso promedio, el orden es O(n·log n).

No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.