Ordenación por monticulos (Heap Sort) Java

El algoritmo de ordenación por monticulos o Heap Sort recorre el conjunto de elementos desde la posición de la mitad hasta la primera organizando el montículo correspondiete a dicho elemento. Una vez terminado este proceso, se inicia el proceso de ordenación ntercambiando el primer elemento por el último del arreglo y reorganizando el montículo a partir de la primera posición.
En el siguiente ejemplo si visualiza mejor el algoritmo de Heap Sort:

public static void ordenacion Monticulos (int[ ] v) {
.....final int N = v.length;
.....for (int nodo = N/2; nodo >=0; nodo--) hacerMonticulo (v, nodo, N-1);
.....for (int nodo = N-1; nodo >=0; nodo--) {
............int tmp = v[0];
............v[0] = v[nodo];
............v[nodo]= tmp;
............hacerMonticulo(v,0,nodo-1);
............}
...}

public static void hacerMonticulo (int [ ] v, int nodo, int fin) {
......int izq = 2*nodo 1;
......int der = izq 1;
......int may;
......if (izq>fin) return;
......if (der>fin) may=izq;
......else may = v[izq]>v [der]?izq:der;
......if (v[nodo] ..........int tmp = v[nodo];
...........v[nodo] = v[may];
...........v[may] = tmp;
..........hacerMonticulo (v,may, fin);
.........}
}

La complejidad del algoritmo de ordenación por montículos es O(n log n)teniendo en cuenta que el proceso de organizar el montículo en el peor caso solamente tiene que hacer intercambios sobre una sola línea de elementos desde la raíz del árbol hasta alguna de las hojas para un máximo de log n intercambios.

Búsqueda Matríz

La búsqueda en matrices es parecida a la que se hace en vectores, la unica diferencia es que se usan 2 bucles en lugar de uno, ya que uno aplica a las filas y otro a las columnas.
El siguiente es el algoritmo de busqueda:

Declarar Matrices

Como su nombre lo indica, son aquellos que tinen dos dimensiones y, en consecuencia se maneja con dos índices:

• Se puede ver tambien como un arreglo de arreglos.

• Un arreglo bidimensional equivalente a una tabla con múltiples filas y columnas.

Al igual que los vectores, las matrices se declaran indicando nombre identificador, número de filas de columnas y tipo de datos que contiene.[ ]
 Por ejemplo:

• Enteros M[3][5] declara una matriz llamada M de 3 filas y 5 columnas de enteros. 

M (1,1)	M (1,2)	M (1,3)	M (1,4)	M (1,5)
M (2,1)	M (2,2)	M (2,3)	M (2,4)	M (2,5)
M (3,1)	M (3,2)	M (3,3)	M (3,4)	M (3,5)

Búsqueda Binaria

Es el método mas eficiente para encontrar elelmentos en un arreglo ordenado.El proceso comienza comparando el elemento central del arreglo con el valor buscado.Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.
Y su algoritmo es el siguiente:

El siguiente ejemplo explica de manera simple su funcionamiento:
Tenemos el arreglo: A= {1,3,4,2,5,6,12,43,21}  y queremos buscar el numero 12, entonces lo primero que se hace es comparar la casilla A(5) que en este caso vale 5 y como 5<>12 entonces entra a la siguiente condicion y compara 12>5 entonces entra al siguiente ciclo donde i vale 5 y compara A(5) y da que 5<>12 entonces i aumenta en 1 y ahora compara A(6) que vale 6 y da lo siguiente 6<>12 entonces i se incrementa en 1 y ahora vale 7 a lo que A(7) se compara y da que 12=12 por lo tanto el valor de la bandera cambia a verdadero y se interrumpe el ciclo y se llega a la condicion final donde se toma en cuenta el valor de la bandera y como en este caso es verdadero se muestra lo siguiente "12 hallado en posicion 7".

Búsqueda secuencial

Es la técnica más simple para buscar un elemento en un arreglo.Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave).Se empieza con la primer casilla del arreglo y se observa una casilla tras otra hasta que se encuentre el elemento buscado o se a vistotodas las casillas.El resultado de la búsqueda es solo un valor, y será la posición del elemento buscado o cero.Dado que el arreglo no ésta en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como el último. Por lo tanto, en promedio, el programa tendrá que el valor buscado con la mitad de los elementos del arreglo.
El método de busqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados. Si el arreglo está ordenado, se puede utlizar la tecnica de alta velocidad de búsqueda binaria, donde se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.
Su algoritmo es el siguiente:

 

Por ejemplo si tenemos el siguiente vector: 

A = {23,21,34,54,89,92,89,72,12,7} 

Y queremos buscar el 54 en el arreglo, entonces lo que sucede es lo siguiente:

La bandera se inicia en falso y la i en 1, asi que se compara la casilla A[1] con el valor a buscar, pero como 23 <> 54 entonces la i se incrementa en 1 y ahora i vale 2 y se compara de nuevo pero ahora es la casilla A[2], pero 21<> 54 y la i vuelve a incrementar y ahora i vale 3 y se compara A[3] es decir 34 <> 54 y la i aumenta en 1 y vale 4 ahora se compara A[4] 54 = 54, entonces a la bandera se le asigna verdadero, esto hace que se interrumpa el ciclo y ahora sigue la siguiente condición, y como la bandera es verdadera se muestra lo siguiente "54 se encontro en posicion 4".

Ordenamiento por Insercíon

El fudamento de este método consiste en insertar los elementos no ordenados del arreglo en subarreglos del mismo que ya estén ordenados.Dependiendo del método elegido para encontrar la posición de inserción tendremos distintas versiones del método de inserción.
por ejemplo: queremos insertar el número 6.

números[3/7/9/10/--/--]

La posición en la que deberá insertarse el 6 es la 2, por lo que los elementos 7,9,10; deberán recorrerse a la derecha, dejando la casilla 2 libre.

números[3/6/7/9/10/--]

El algoritmo de inserción es:

Ordenamiento por selección

Este metodo consiste en.encontrar el elemento más pequeño de la lista y colocarlo en la primera posición, luego se encuentra el segundo elemento más pequeño y se lleva a la segunda posición. Se continúa el proceso hasta llegar a la penúltima posición del vector.

Para obtener el elemento más pequeño se compara el primer valor con cada uno de los restantes y cada vez que se encuentra uno mas pequeño se intercambian los valores.

Ordenación por burbuja

Una manera simple de expresar el ordenamiento de burbuja en pseudocódigo es la siguiente:

En este algoritmo se trata de ordenar una lista de valores: a, de n términos numerados del termino 0 al n-1, consta de dos bucles anidados uno con el índice i, que acota el recorrido de la burbuja en sentido inverso de 2 a n, y un segundo bucle con el índice j, con un recorrido desde 0 hasta n-i, para cada iteración del primer bucle, que indica el lugar de la burbuja.
La burbuja son dos términos de la lista seguidos, j y j+1, que se comparan, si el primero es menor que el segundo sus valores se intercambian.
Esta comparación se repite en el centro de los dos bucles, dando lugar a la postre a una lista ordenada, puede verse que el número de repeticiones sola depende de n, y no del orden de los términos, esto es si pasamos al algoritmo una lista ya ordenada, realizara todas las comparaciones exactamente igual que para una lista no ordenada, esta es una característica de este algoritmo, luego veremos una variante que evita este problema.
Para comprender el funcionamiento, veamos un ejemplo sencillo:
Partimos de una lista de números que hay que ordenar:

Podemos ver que la lista tiene cinco términos, luego:

n = 5 

El indice i hará un recorrido de 2 hasta n:





Que en este caso será de 2 a 5. Para cada uno de los valores de i, j tomara sucesivamente los valores de 0 hasta n-i:

Para cada valor de j, obtenido en ese orden, se compara el valor del índice j con el siguiente:

Si el termino j es menor, en su caso podría se mayor, que el termino j+1, los valores se permutan, en caso contrario se continúa con la iteración.

Para el caso del ejemplo, tenemos que:

 n=5 

Para la primera iteración del primer bucle:

i=2

y j tomara los valores de 0 hasta 3:


Cuando j vale 0, se comparan a₀a₁ el 55 y el 86, dado que 55 <> 48, se permutan, dando lugar a una nueva lista.
Ahora j vale 1 y se comparan a₁a₂ el 86 y el 48 Como 86 > 48, se permutan, dando lugar a una nueva lista.
Se repite el proceso hasta que j valga 3, dando lugar a una lista parcialmente ordenada, podemos ver que el termino de mayor valor esta en el lugar más alto.

Ahora i vale 3, y j hará un recorrido de 0 a 2.
Primero j vale 0, se comparan , el 55 y el 48, como 55 > 48 se permutan dando lugar a la nueva lista.
Para j = 1 se compara el 55 con el 16 y se cambian de orden.
Para j = 2 se compara el 55 y el 82 y se dejan como están, finalizando el bucle con una lista mejor ordenada, puede verse que los dos valores más altos ya ocupan su lugar. No se ha realizado ninguna comparación con el termino cuarto, dado que ya se sabe que después del primer ciclo es el mayor de la lista.
El algoritmo consiste en comparaciones sucesivas de dos términos consecutivos, ascendiendo de abajo a arriba en cada iteración, como la ascensión de las burbujas de aire en el agua, de ahí el nombre del procedimiento, en la primera iteración el recorrido ha sido completo, en el segundo se ha dejado él ultimo termino, al tener ya el mayor de los valores, en los sucesivos sé ira dejando re realizar las ultimas comparaciones, como se puede ver.

Ahora ya i vale 4 y j recorrerá los valores de 0 a 1.
Cuando j vale 0, se comparan esto es el 48 y el 16 dado que 48 es mayor que 16 se permutan los valores, dando lugar a una lista algo más ordenada que la anterior, desde esta nueva ordenación, j pasa a valer 1, con lo que se comparan los términos el 48 y el 55 que quedan en el mismo orden.
En este caso la burbuja ha ascendido menos que en los casos anteriores, y la lista esta ya ordenada, pero el algoritmo tendrá que completarse, realizando una ultima iteración.
Hay que tener en cuenta que el bucle para realiza un número fijo de repeticiones y para finalizar tendrán que completarse, aun en el caso extremo, de que la lista estaría previamente ordenada.
Por ultimo i vale 5 y j solo puede vale 0, con lo que solo se realizara una comparación de el 16 y el 48, que ya están ordenados y se dejan igual.

Los bucles finalizan y también el procedimiento, dejando la lista ordenada.
Una variante que finaliza en caso de que la lista este ordenada, puede ser la siguiente, empleando un centinela ordenado, que detecta que no se ha modificado la lista en un recorrido de la burbuja, y que por tanto la lista ya esta ordenada, finalizando.

Ordenamiento

Uno de los procedimientos más comunes y útiles en el procesamiento de datos, es la clasificación u ordenación de los mismos. Se considera ordenar al proceso de reorganizar un conjunto dado de objetos en una secuencia determinada. Cuando se analiza un método de ordenación, hay que determinar cuántas comparaciones e intercambios se realizan para el caso más favorable, para el caso medio y para el caso más desfavorable.

La colocación en orden de una lista de valores se llama Ordenación. Por ejemplo, se podría disponer una lista de valores numéricos en orden ascendente o descendente, o bien una lista de nombres en orden alfabético. La localización de un elemento de una lista se llama búsqueda.

Tal operación se puede hacer de manera más eficiente después de que la lista ha sido ordenada.

Existen varios métodos para ordenamiento, clasificados en tres formas:

•  Intercambio
•  Selección
•  Inserción.

 

Elementos de un arreglo

Para referirse a un elemento individual del arreglo se utiliza su índice.

• El índice es asignado generalmente por la posición que ocupa el elemento en el arreglo. 
• Por ejemplo, para el arreglo A, cuyos datos son:

A [3, -6, 1, 24, 8]

Si nos queremos referir al segundo elemento del arreglo, es decir, el que está en la posición 2, diríamos A [2], que se lee: “A de 2” o “A subíndice 2”, en el cual está almacenado el -6.

Las operaciones básicas que realiza un arreglo son:

• Asignación
• Lectura
• Escritura
• Recorrido
• Búsqueda
  
• Actualización (borra, insertar)
• Ordenación

Características de los arreglos

Tienen un único nombre de variable, que representa todos los elementos.

• Contienen un índice o subíndice, los cuales diferencian a cada elemento del arreglo.
• Se pueden realizar ciertas operaciones como son: recorridos, ordenaciones y búsquedas de elementos.
• El número total de elementos del arreglo (NTE) es igual al límite superior (LS), menos límite inferior (LI).
  
  

NTE = LS -LI + 1

• El tipo de índice puede ser cualquier tipo ordinal (carácter, entero, enumerado).
• El tipo de los componentes puede ser cualquiera (entero, real, cadena de caracteres, etc.).

• Se utilizan [ ] para indicar el índice de un arreglo. Entre los [ ] se debe escribir un valor ordinal.

• Cada elemento se puede procesar como si fuese una variable simple ocupando una posición de memoria.

Por ejemplo, podemos almacenar en un arreglo que consta de 6 elementos, los nombres de los coches de mis vecinos. Este vector sería de la siguiente manera:

 

Definición

Un arreglo (array en inglés) es una colección finita, homogénea y ordenada de elementos del mismo tipo. La propiedad ordenada significa que el elemento primero, segundo, hasta el n-ésimo de un arreglo puede ser identificado.

La propiedad homogénea significa que todos los elementos de un arreglo son del mismo tipo de datos.

Los arreglos se clasifican en:

·         Unidimensionales (vector)

·         Bidimensionales (Tablas o matriz)

·         Multidimensionales

Un arreglo sirve Cuando se cuenta con un gran número de datos, que requieren ser procesados, esto es, sumados, ordenados, etc., se puede utilizar un arreglo para almacenarlos, en lugar de muchas variables independientes. Por ejemplo:

·         Almacenar el sueldo de varios trabajadores y luego ordenarlos de mayor a menor.

·         Almacenar los nombres de alumnos, para ordenarlos en orden alfabético.

·         Almacenar la calificaciones de N alumnos y luego obtener el promedio.