MÉTODOS DE ORDENAMIENTO DE VECTORES
Por ordenar se entiende
el proceso de reorganizar un conjunto de objetos en una cierta secuencia de
acuerdo a un criterio especificado. En general, el objetivo de este proceso es
facilitar la posterior búsqueda de elementos en el conjunto ordenado.
MÉTODO: BURBUJA
El método de la burbuja es uno de
los más simples, es tan fácil como comparar todos los elementos de una lista
contra todos, si se cumple que uno es mayor o menor a otro, entonces los
intercambia de posición.
DIAGRAMA DE FLUJO
CÓDIGO EN JAVA
|
package
burbuja;
import
java.util.Scanner;
public
class Burbuja {
public
static void main(String[] args) {
System.out.println("");
Scanner
entrada=new Scanner(System.in);
int
a, vector[],i,n,j,aux;
vector=new int[100];
System.out.printf("ingrese la cantidad de numeros
que desee en el vector: ");
n=entrada.nextInt();
n=n-1;
for(i=0;i<=n;i++)
{
System.out.printf("ingrese el valor del vector[%d]:",i+1);
vector[i]=entrada.nextInt();
}
// ordenamiento
for (i=0;i<=n;i++)
{
for (j=i+1;j<=n;j++)
if (vector[i]>vector[j])
{
{
aux=vector[i];
vector[i]=vector[j];
vector[j]=aux;
}
}}
//
impression
System.out.printf("el vector ordenado es: ”);
for(i=0;i<=n;i++)
{
System.out.println(vector[i]);
}
}
}
|
METODO: INSERCIÓN
En este procedimiento se recurre
a una búsqueda binaria en lugar de una búsqueda secuencial para insertar un
elemento en la parte de arriba del arreglo, que ya se encuentra ordenado. El proceso,
al igual que en el método de inserción directa, se repite desde el segundo
hasta el n-ésimo elemento.
DIAGRAMA DE FLUJO
CÓDIGO EN JAVA
|
package inserccion;
import
java.util.Scanner;
public class
Inserccion {
public static void
main(String[] args) {
System.out.println("");
Scanner entrada=new
Scanner(System.in);
int
a,vector[],i,n,j,aux,k,m,po;
vector=new int[100];
System.out.printf("ingrese la cantidad de numeros que desee en el
vector: ");
n=entrada.nextInt();
for(i=0;i<n;i++)
{
System.out.printf("ingrese el valor del vector[%d]:",i+1);
vector[i]=entrada.nextInt();
}
// ordenamiento por
insercion
for (i=1;i<n;i++)
{
po=0;
for (j=(i-1);j>=0;j--)
{
if(vector[i]<vector[j])
{
po=po+1;
}
}
aux=vector[i];
k=i;
for (m=0;m<po;m++)
{
vector[k]=vector[k-1];
k=k-1;
}
vector[k]=aux;
}
// impresion
System.out.println("el
vector ordenado es:");
for(i=0;i<n;i++)
{
System.out.println(vector[i]);
}
}
}
|
MÉTODO: SELECCIÓN
El método se basa en buscar en
cada iteracción el mínimo elemento del “subvector” situado entre el índice i y
el final del vector e intercambiarlo con el de índice i. Tomando la dimensión
del vector n como tamaño del problema es inmediato que el bucle se repite n
veces y por tanto la función que da el número de repeticiones es de tipo lineal
(O(n)).
DIAGRAMA DE FLUJO
CÓDIGO EN JAVA
|
package
seleccion;
import
java.util.Scanner;
public
class Seleccion {
public static void main(String[] args) {
System.out.println("");
Scanner
entrada=new Scanner(System.in);
int
i,j,a[], aux,menor,n;
a=new
int[100];
System.out.printf("ingrese a cantidad de
numeros que desee en el vector: ");
n=entrada.nextInt();
n=n-1;
for(i=0;i<=n;i++)
{
System.out.printf("ingrese el valor del vector[%d]:",i+1);
a[i]=entrada.nextInt();
}
for(i=1;i<n;i++)
{
menor=i;
for(j=i+1;j<=n;j++)
{ if (a[j]<a[menor])
{
menor=j;
}
}
aux=a[i];
a[i]=a[menor];
a[menor]=aux;
}
// impresion
System.out.println("el vector ordenado es:");
for(i=0;i<n+1;i++)
{
System.out.println(a[i]);
}
}
}
|
MÉTODO: SHELLSORT
Este metodo es una mejora del
algoritmo de ordenamiento por Insercion (Insertsort). Si tenemos en cuenta que
el ordenamiento por insercion es mucho mas eficiente si nuestra lista de
numeros esta semi-ordenada y que
desplaza un valor una única posicion a la vez. Durante la ejecucion de este
algoritmo, los numeros de la lista se van casi-ordenando y finalmente, el
ultimo paso o funcion de este algoritmo es un simple metodo por insercion que,
al estar casi-ordenados los numeros, es más eficiente.
EXPLICACIÓN
CÓDIGO EN JAVA
void shellSort(int a[], int h)
{
int i;
while (h > 0)
{ for (i = h-1; i<n; i++)
{
int B = a[i];
int j = i;
for (j = i; (j >= h) && (a[j - h] > B); j -= h)
{ a[j] = a[j - h];}
a[j] = B;
}
h = h / 2;
}
}
{
int i;
while (h > 0)
{ for (i = h-1; i<n; i++)
{
int B = a[i];
int j = i;
for (j = i; (j >= h) && (a[j - h] > B); j -= h)
{ a[j] = a[j - h];}
a[j] = B;
}
h = h / 2;
}
}
METODO: QUICKSORT
Sin duda, este algoritmo es uno de los mas eficientes. Este
metodo es el mas rápido gracias a sus llamadas recursivas, basandose en la
teoria de divide y vencerás. Lo que hace este algoritmo es dividir
recurvisamente el vector en partes iguales, indicando un elemento de inicio,
fin y un pivote (o comodin) que nos permitirá segmentar nuestra lista. Una vez
dividida, lo que hace, es dejar todos los mayores que el pivote a su derecha y
todos los menores a su izq. Al finalizar el algoritmo, nuestros elementos están
ordenados
DIAGRAMA DE FLUJO
CÓDIGO EN JAVA
void ordenar (int vect[], int ind_izq, int ind_der)
{
int i, j; /* variables indice del vector */
int elem; /* contiene un elemento del vector */
i = ind_izq;
j = ind_der;
elem = vect[(ind_izq+ind_der)/2];
do
{while (vect[i] < elem) //recorrido del vector hacia la derecha
i++;
while (elem < vect[j]) // recorrido del vector hacia la izquierda
j--;
if (i <= j) /* intercambiar */
{ int aux; /* variable auxiliar */
aux = vect[i];
vect[i] = vect[j];
vect[j] = aux;
i++;
j--;
}
} while (i <= j);
if (ind_izq < j) {ordenar (vect, ind_izq, j);} //Llamadas recursivas
if (i < ind_der) {ordenar (vect, i, ind_der);}
}
{
int i, j; /* variables indice del vector */
int elem; /* contiene un elemento del vector */
i = ind_izq;
j = ind_der;
elem = vect[(ind_izq+ind_der)/2];
do
{while (vect[i] < elem) //recorrido del vector hacia la derecha
i++;
while (elem < vect[j]) // recorrido del vector hacia la izquierda
j--;
if (i <= j) /* intercambiar */
{ int aux; /* variable auxiliar */
aux = vect[i];
vect[i] = vect[j];
vect[j] = aux;
i++;
j--;
}
} while (i <= j);
if (ind_izq < j) {ordenar (vect, ind_izq, j);} //Llamadas recursivas
if (i < ind_der) {ordenar (vect, i, ind_der);}
}
