Universidad Del Valle de Guatemala

Introducción a la Programación Orientada a Objetos CC2002

Investigación Corta

“Sorting”

Guatemala, 3 de octubre de 2004

Sorting

Uno de los problemas fundamentales de la ciencia de la computación es ordenar una lista de objetos. Para esta necesidad existe una solución, llamada “sorting algorithms”, término cuya traducción en español es “algoritmos de ordenamiento”. Algunos algoritmos son simples y casi deducidos intuitivamente. Otros son extremadamente complicados pero dan resultados inmediatos (Weisstein, 1999). A continuación se presenta una breve introducción al tema.

¿Qué es sorting?

En español significa ordenamiento. En las ciencias de la computación y en las matemáticas, un algoritmo de sorting es aquel que coloca a los elementos de una lista en determinado orden. Los órdenes más utilizados son los órdenes numéricos y lexicográficos. Un proceso de sorting (ordenamiento) eficiente es necesario para optimizar el uso de otros algoritmos. Es muy utilizado para organizar “human readable output” (Lamont, 2003).

Sorting es el arreglo de números (u otros objetos ordenables) en una lista, en el correcto orden lexicográfico. Por tanto la alfabetización es una forma de ordenamiento. Debido a la importancia extrema que tiene el ordenamiento de datos en casi todos los algoritmos de computación y database, muchos esfuerzos han sido enfocados a la creación y el análisis de eficientes algoritmos de ordenamiento (Weisstein, 1999).

Clasificación de algoritmos de Sorting

En las ciencias de la computación los algoritmos de ordenamiento se clasificados según (Lamont, 2003):

• Complejidad computacional. Son aquellos que se clasifican en términos de la eficiencia que tenga determinado algoritmo para organizar una lista de tamaño n. Normalmente un buen comportamiento es aquel en que el número de comparaciones es n logn (Lamont, 2003).

• Uso de memoria (Lamont, 2003). Internal Sort, se le llama a cualquier algoritmo que utilice main mamory exclusivamente, durante el ordenamiento. Esto asume una “high-speed random acces to all memory”. External Sort, se le llama a cualquier algoritmo que utilice memoria externa, como lo podría ser un disco o algún tipo de cinta magnética (Scitec 2004).

• Estabilidad. Los algoritmos que mantienen cierto tipo de estabilidad mantienen el orden relativo de ingreso de los valores de misma magnitud. Es decir, un algoritmo es estable si al ingresar S y R con la misma tecla, pero si R aparece antes que S en la lista original, R aparecerá antes de S en la lista ordenada (Lamont, 2003).

Entre los algoritmos de tipo estable están: Bubble Sort, Insertion Sort, Bucket Sort, Merge Sort y Coctail Sort. Entre los algoritmos de tipo inestable están: Selection Sort, Shell sort, Quick Sort, Heap Sort y Smooth Sort (Lamont, 2003).

Nomenclatura para estimados de Tiempo, de algoritmos de ordena miento:

Es posible pronosticar un estimado de tiempo de la ejecución de los algoritmos utilizando la notación O (big-oh). Por ejemplo un algoritmo que ejecuta en O(n2) indica que el tiempo de ejecución crece según el cuadrado de el tamaño de la data (Knuth, 1998).

Algunos Algoritmos de Sorting más populares:

Bubble Sort:

Es el método de ordenamiento más fácil de realizar y más fácil de comprender. Este se considera el más simple y es utilizado a nivel mundial. El algoritmo inicia al principio de el conjunto de información a ordenar. Compara los primeros dos elementos, y si el primero es más grande que el segundo, los intercambia y luego repite este procedimiento hasta que no hayan ocurrido cambios en la última evaluación. El algoritmo realiza esto para cada par de elementos adyacentes, hasta que no tiene más elementos que comparar. Sin embargo este algoritmo es muy ineficiente, y es raramente utilizado, excepto para fines educacionales. Una variante de este método de ordenamiento es llamado Shuttle Sort (Lamont, 2003).

Insertion Sort:

Este método de ordenamiento es muy similar al Bubble Sort, con la diferencia que éste es más eficiente ya que reduce las comparaciones entre los elementos. Un elemento es comparado con cada elemento anterior, hasta que se encuentra un elemento más pequeño. Es decir, si un elemento contiene un valor menor que todos los elementos anteriores, compara ese elemento con todos los elementos anteriores antes de continuar con la siguiente comparación. Aunque éste algoritmo es más eficiente que el Bubble Sort, es ineficiente comparado con otros algoritmos de ordenamiento. Pero indudablemente Insertion Sort es una buena elección de método de ordenamiento para listas pequeñas de 30 elementos o menos. Una variante creada de insertion Sort que trabaja eficientemente con listas más grandes es shell Sort (Lamont, 2003). El tiempo promedio de ejecución es O(n 2 ) (Knuth, 1998).

Selection Sort:

El algoritmo de selección construye una ordenada secuencia de elementos tomando uno a la vez, para luego añadir elementos a la secuencia ya ordenada. En cada paso, el siguiente elemento para ser añadido es seleccionado de la lista los elementos que quedan en la lista inicial (en desorden). Por el hecho de que los elementos son añadidos a la secuencia ordenada, estos siempre son añadidos al final. Esto es en lo que difiere Selection Sort del Insertion Sort. Ya que en la inserción los elementos son añadidos en un orden arbitrario. Ambos selection sort e insertion sort son arrays de ordenamiento de tipo in place. Consecuentemente, los ordenamientos son implementados intercambiando elementos del array. Selection sort difiere de Exchange sorting debido a que en cada paso se selecciona el siguiente elemento de la secuencia restante de elementos, y luego lo mueve a su posición final del array, cambiándolo con el que actualmente ocupa su posición (Weisstein, 1999)..

Shell Sort:

Este método de ordenamiento fue inventado en 1959 por Donald Shell. Mejora al ordenamiento Bubble y el Insertion mediante el movimiento de los elementos fuera de orden de más una posición a la vez. La implementación de este método puede ser descrita como un ordenamiento de datos secuenciales en dos dimensiones de un array y luego los ordena en columnas utilizando el método de Insertion Sort. Aunque este método es ineficiente para grandes cantidades de información. Es uno de los algoritmos más rápidos para ordenar pequeñas cantidades de elementos, listas de 10 elementos o menos. Otra ventaja de este algoritmo es que requiere pequeñas cantidades de memoria (Lamont, 2003). El tiempo promedio de ejecución es O(n7/6) y en el peor de los casos O(n4/3) (Knuth, 1998).

Bucket Sort:

Es probablemente la distribución más simple que tiene un algoritmo. El único requerimiento esencial es que el tamaño del universo del cual los elementos estén siendo ordenados, sea constante. Por ejemplo suponga que estamos ordenando elementos en el rango de {0, 1, . . ., m-1}. El ordenamiento de Bucket sort utiliza m contadores el contador ith mantiene cuenta del número de ocurrencias del elemento ith en el universo. Para una mejor comprensión observar la figura del apéndice referente a Bucket Sort (Weisstein, 1999).

El algoritmo trabaja partiendo un array en un número finito de buckets y luego ordena cada bucket. Tiene un promedio de tiempo de ejecución de O(n). El ordenamiento sigue los siguientes pasos. 1. Establece un array vacío de buckets, del tamaño del rango. 2. Va al array original y coloca cada objeto en su correspondiente bucket. 3. Ordena cada bucket que contenga elementos. 4. Coloca cada elemento de los buckets ordenados en el array original (BrainyE ,2000).

Quick Sort:

Es un algoritmo clasificado como in-place, divide-and-counter y extremadamente recursivo. Es esencialmente una versión más rápida del algoritmo de Merge. Este algoritmo es simple en teoría, pero muy complicado de colocarlo en código. Por largos años los científicos de computación se enredaron con una implementación práctica de este algoritmo. El algoritmo sigue los siguientes pasos: 1.Si existe uno o más elementos en el array aún por ser ordenados, los devuelve regresa al ordenamiento. 2. Elige un elemento del array que sirve como punto central de partida. 3. Parte el array en dos. Una parte contiene elementos más grandes que el punto central y la otra con elementos menores. 4. El algoritmo se repite el algoritmo en ambas mitades del array original (Lamont, 2003). Quick Sort es un método no estable.El tiempo promedio de ejecución es O(n logn) y en el peor de los casos O(n2) (Knuth, 1998).

APENDICE

Implementación en java de los algoritmos de ordenamiento:

Bubble Sorting:

void bubbleSort(int array[], int array_size)

{

int i, j, temp;

for (i = (array_size - 1); i >= 0; i--)

{

for (j = 1; j <= i; j++)

{

if (array[j-1] > array[j])

{

temp = array[j-1];

array[j-1] = array[j];

array[j] = temp;

}

}

}

}

Insertion Sorting:

void insertionSort(int array[], int array_size)

{

int i, j, index;

for (i=1; i < array_size; i++)

{

index = array[i];

j = i;

while ((j > 0) && (array[j-1] > index))

{

array[j] = array[j-1];

j = j - 1;

}

array[j] = index;

}

} (Weisstein, 1999).

Selection Sorting:

void selectionSort( dataElem array[ ], int array_size)

{

int i, j;

int min, temp;

for (i = 0; i < array_size-1; i++)

{

min = i;

for (j = i+1; j < array_size; j++)

{

if (array [j] < array [min])

min = j;

}

temp = array [i];

array [i] = array [min];

array [min] = temp;

}

} (Weisstein, 1999).

Shell Sorting:

void quickSort(int numbers[], int array_size)

{

q_sort(numbers, 0, array_size - 1);

}

void q_sort(int numbers[], int left, int right)

{

int pivot, l_hold, r_hold;

l_hold = left;

r_hold = right;

pivot = numbers[left];

while (left < right)

{

while ((numbers[right] >= pivot) && (left < right))

right--;

if (left != right)

{

numbers[left] = numbers[right];

left++;

}

while ((numbers[left] <= pivot) && (left < right))

left++;

if (left != right)

{

numbers[right] = numbers[left];

right--;

}

}

numbers[left] = pivot;

pivot = left;

left = l_hold;

right = r_hold;

if (left < pivot)

q_sort(numbers, left, pivot-1);

if (right > pivot)

q_sort(numbers, pivot+1, right);

} (Lamont, 2003).

Bucket Sorting:

void bucketSort(dataElem array[], int array_size)

{

int i, j;

dataElem count[array_size];

for(i =0; i < array_size; i++)

count[i] = 0;

for(j =0; j < array_size; j++)

++count[array[j]];

for(i =0, j=0; i < array_size; i++)

for(; count[i]>0; --count[i])

array[j++] = i;

} (Weisstein, 1999).

Quick Sorting:

void q_sort(int array[], int left, int right)

{

int pivot, l_hold, r_hold;

l_hold = left;

r_hold = right;

pivot = array[left];

while (left < right)

{

while ((array[right] >= pivot) && (left < right))

right--;

if (left != right)

{

array[left] = array[right];

left++;

}

while ((array[left] <= pivot) && (left < right))

left++;

if (left != right)

{

array[right] = array[left];

right--;

}

}

array[left] = pivot;

pivot = left;

left = l_hold;

right = r_hold;

if (left < pivot)

q_sort(array, left, pivot-1);

if (right > pivot)

q_sort(array, pivot+1, right);

}

void quickSort(int array[], int array_size)

{

q_sort(array, 0, array_size - 1);

}

Diagrama de Implementación de algoritmos de ordenamiento:

Bubble Sorting : (Weisstein, 1999) Insertion Sorting: (Weisstein, 1999)

(Weisstein, 1999).

Insertion Sorting:

(Weisstein, 1999).

Selection Sorting:

Bucket Sorting:

(Weisstein, 1999).

Quick Sorting:

Selection Sorting: (Weisstein, 1999)

Bucket Sorting: (Weisstein, 1999)

(Weisstein, 1999).

Quick Sorting:

(Weisstein, 1999)