Mtodos Internos En Java
Ordenacin interna.
Ordenar significa reagrupar o reorganizar un conjunto de datos u objetos en
una secuencia especfica, la cual puede ser de dos formas distintas:
Ascendente (menor a mayor) o
Descendente (mayor a menor).
Los mtodos de ordenacin se clasifican en dos categoras:
Ordenacin interna (de arreglos) y
Ordenacin externa (de archivos).
La ordenacin interna o de arreglos, recibe este nombre ya que los elementos o
componentes del arreglo se encuentran en la memoria principal de la
computadora.
Los mtodos de ordenacin interna a su vez se clasifican en:
-
Mtodos directos (n2) y
Mtodos logartmicos (n * log n).
Los mtodos directos, son los ms simples y fciles de entender, son eficientes
cuando se trata de una cantidad de datos pequea. Los mtodos logartmicos,
son ms complejos, difciles de entender y son eficientes en grandes
cantidades de datos.
Los mtodos directos ms conocidos son:
-
Ordenacin por intercambio.
Ordenacin por insercin.
Ordenacin por seleccin.
Burbuja.
El mtodo de ordenacin por intercambio directo o mtodo de la burbuja, es el
ms 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).
El primer procedimiento del mtodo de la burbuja es:
Generar un ciclo que inicie desde uno hasta el nmero de elementos del
arreglo.
Generar un segundo ciclo dentro del anterior que inicie desde cero hasta el
nmero de elementos del arreglo menos dos.
Dentro del segundo ciclo debe existir una comparacin que determina el tipo
de ordenamiento (ascendente o descendente) entre el primer elemento
(posicin generado por el segundo ciclo) y el segundo elemento (el que le
sigue), si la respuesta a la condicin es verdadera se realiza un intercambio
entre los dos elementos.
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.
Procedimiento Bubble Sort
paso 1: [Inicializa i al final de arreglo] For i <- N down to 1 do
paso 2: [Inicia desde la segunda pos.] For j <- 2 to i do
paso 4: [Si a[j-1] es mayor que el que le sigue] If a[j-1] <>
paso 5: [Los intercambia] Swap(a, j-1, j).
paso 6: [Fin] End.
Tiempo de ejecucin del algoritmo burbuja:
1. Para el mejor caso (un paso) O(n)
2. Peor caso n(n-1)/2
3. Promedio O(n2)
Algoritmos de insercin
En este tipo de algoritmo los elementos que van a ser ordenados son
considerados uno a la vez. Cada elemento es INSERTADO en la posicin
apropiada con respecto al resto de los elementos ya ordenados.
Entre estos algoritmos se encuentran el de INSERCION DIRECTA, SHELL SORT,
INSERCION BINARIA y HASHING.
Algoritmos de seleccin
En este tipo de algoritmos se SELECCIONA o se busca el elemento ms
pequeo (o ms grande) de todo el conjunto de elementos y se coloca en su
posicin adecuada. Este proceso se repite para el resto de los elementos hasta
que todos son analizados.
Entre estos algoritmos se encuentra el de SELECCION DIRECTA.
Procedimiento Selection Sort
paso 1: [Para cada pos. del arreglo] For i <- 1 to N do
paso 2: [Inicializa la pos. del menor] menor <- i
paso 3: [Recorre todo el arreglo] For j <- i+1 to N do
paso 4: [Si a[j] es menor] If a[j] <>
paso 5: [Reasigna el apuntador al menor] min = j
paso 6: [Intercambia los datos de la pos.
min y posicin i] Swap(a, min, j).
paso 7: [Fin] End.
Ejemplo:
El arreglo a ordenar es a = ['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e'].
Se empieza por recorrer el arreglo hasta encontrar el menor elemento. En este
caso el menor elemento es la primera 'a'. De manera que no ocurre ningn
cambio. Luego se procede a buscar el siguiente elemento y se encuentra la
segunda 'a'.
Esta se intercambia con el dato que est en la segunda posicin, la 's',
quedando el arreglo as despus de dos recorridos: a =
['a','a','o','r','t','i','n','g','e','x','s','m','p','l','e'].
El siguiente elemento, el tercero en orden de menor mayor es la primera 'e', la
cual se intercambia con lo que est en la tercera posicin, o sea, la 'o'. Le sigue
la segunda 's', la cual es intercambiada con la 'r'.
El arreglo ahora se ve de la siguiente manera: a =
['a','a','e','e','t','i','n','g','o','x','s','m','p','l','r'].
De esta manera se va buscando el elemento que debe ir en la siguiente
posicin hasta ordenar todo el arreglo.
El nmero de comparaciones que realiza este algoritmo es :
Para el primer elemento se comparan n-1 datos, en general para el elemento isimo se hacen n-i comparaciones, por lo tanto, el total de comparaciones es:
la sumatoria para i de 1 a n-1 (n-i) = 1/2 n (n-1).