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.