ORDENAMIENTO DE VECTORES

El ordenamiento de un vector se logra intercambiando las componentes de manera que:

vec[0] <= vec[1] <= vec[2] etc.

El contenido de la componente vec[0] sea menor o igual al contenido de la componente vec[1] y así sucesivamente.

Si se cumple lo dicho anteriormente decimos que el vector está ordenado de menor a mayor. Igualmente podemos ordenar un vector de mayor a menor.

Se puede ordenar tanto vectores con componentes de tipo int, float como String. En este último caso el ordenamiento es alfabético.

Problema 1:

Se debe crear un vector donde almacenar 5 sueldos. Ordenar el vector sueldos de menor a mayor.

Esta primera aproximación tiene por objetivo analizar los intercambios de elementos dentro del vector.

El algoritmo consiste en comparar si la primera componente es mayor a la segunda, en caso que la condición sea verdadera, intercambiamos los contenidos de las componentes.

Vamos a suponer que se ingresan los siguientes valores por teclado:

1200 750 820 550 490

En este ejemplo: ¿es 1200 mayor a 750? La respuesta es verdadera, por lo tanto intercambiamos el contenido de la componente 0 con el de la componente 1.

Luego comparamos el contenido de la componente 1 con el de la componente 2: ¿Es 1200 mayor a 820?

La respuesta es verdadera entonces intercambiamos.

Si hay 5 componentes hay que hacer 4 comparaciones, por eso el for se repite 4 veces.

Generalizando: si el vector tiene N componentes hay que hacer N-1 comparaciones.

uando f = 0 f = 1 f = 2 f = 3 750 750 750 750 1200 820 820 820 820 1200 550 550 550 550 1200 490 490 490 490 1200

Podemos ver cómo el valor más grande del vector desciende a la última componente. Empleamos una variable auxiliar (aux) para el proceso de intercambio:

aux=sueldos[f]; sueldos[f]=sueldos[f+1]; sueldos[f+1]=aux;

Al salir del for en este ejemplo el contenido del vector es el siguiente:

750 820 550 490 1200

Analizando el algoritmo podemos comprobar que el elemento mayor del vector se ubica ahora en el último lugar.

Podemos definir otros vectores con distintos valores y comprobar que siempre el elemento mayor queda al final.

Pero todavía con este algoritmo no se ordena un vector. Solamente está ordenado el último elemento del vector.

Ahora bien, con los 4 elementos que nos quedan podemos hacer el mismo proceso visto anteriormente, con lo cual quedará ordenado otro elemento del vector. Este proceso lo repetiremos hasta que quede ordenado por completo el vector.

Como debemos repetir el mismo algoritmo podemos englobar todo el bloque en otra estructura repetitiva.

Realicemos una prueba del siguiente algoritmo:

Cuando k = 0 f = 0 f = 1 f = 2 f = 3 750 750 750 750 1200 820 820 820 820 1200 550 550 550 550 1200 490 490 490 490 1200 Cuando k = 1 f = 0 f = 1 f = 2 f = 3 750 750 750 750 820 550 550 550 550 820 490 490 490 490 820 820 1200 1200 1200 1200 Cuando k = 2 f = 0 f = 1 f = 2 f = 3 550 550 550 550 750 490 490 490 490 750 750 750 820 820 820 820 1200 1200 1200 1200 Cuando k = 3 f = 0 f = 1 f = 2 f = 3 490 490 490 490 550 550 550 550 750 750 750 750 820 820 820 820 1200 1200 1200 1200

¿Porque repetimos 4 veces el for externo?

Como sabemos cada vez que se repite en forma completa el for interno queda ordenada una componente del vector. A primera vista diríamos que deberíamos repetir el for externo la cantidad de componentes del vector, en este ejemplo el vector sueldos tiene 5 componentes.

Si observamos, cuando quedan dos elementos por ordenar, al ordenar uno de ellos queda el otro automáticamente ordenado (podemos imaginar que si tenemos un vector con 2 elementos no se requiere el for externo, porque este debería repetirse una única vez)

Una última consideración a este ALGORITMO de ordenamiento es que los elementos que se van ordenando continuamos comparándolos.

Ejemplo: En la primera ejecución del for interno el valor 1200 queda ubicado en la posición 4 del vector. En la segunda ejecución comparamos si el 820 es mayor a 1200, lo cual seguramente será falso.

Podemos concluir que la primera vez debemos hacer para este ejemplo 4 comparaciones, en la segunda ejecución del for interno debemos hacer 3 comparaciones y en general debemos ir reduciendo en uno la cantidad de comparaciones.

Si bien el algoritmo planteado funciona, un algoritmo más eficiente, que se deriva del anterior es el plantear un for interno con la siguiente estructura: (f=0 ; f<4-k; f++)

Es decir restarle el valor del contador del for externo.

Programa:

import java.util.Scanner; public class PruebaVector13 { private Scanner teclado; private int[] sueldos; public void cargar() { teclado=new Scanner(System.in); sueldos=new int[5]; for(int f=0;f<sueldos.length;f++) { System.out.print("Ingrese el sueldo:"); sueldos[f]=teclado.nextInt(); } } public void ordenar() { for(int k=0;k<4;k++) { for(int f=0;f<4-k;f++) { if (sueldos[f]>sueldos[f+1]) { int aux; aux=sueldos[f]; sueldos[f]=sueldos[f+1]; sueldos[f+1]=aux; } } } } public void imprimir() { System.out.println("Sueldos ordenados de menor a mayor."); for(int f=0;f<sueldos.length;f++) { System.out.println(sueldos[f]); } } public static void main(String[] ar) { PruebaVector13 pv=new PruebaVector13(); pv.cargar(); pv.ordenar(); pv.imprimir(); } }

También podemos ordenar vectores cuyas componentes sean de tipo String. Para esto no podemos utilizar el operador > sino debemos utilizar un método de la clase String:

String cad1="juan"; String cad2="analia"; if (cad1.compareTo(cad2)>0) { System.out.println(cad1 + " es mayor alfabéticamente que " + cad2); }

El método compareTo retorna un valor mayor a cero si cad1 es mayor alfabéticamente. En este ejemplo cad1 tiene un valor alfabéticamente mayor a cad2, luego el compareTo retorna un valor mayor a cero.

Si los dos String son exactamente iguales el método compareTo retorna un cero, y finalmente si cad1 es menor alfabeticamente retorna un valor menor a cero.

Problema 2:

Definir un vector donde almacenar los nombres de 5 paises. Confeccionar el algoritmo de ordenamiento alfabético.

Programa:

import java.util.Scanner; public class PruebaVector14 { private Scanner teclado; private String[] paises; public void cargar() { teclado=new Scanner(System.in); paises=new String[5]; for(int f=0;f<paises.length;f++) { System.out.print("Ingrese el nombre del pais:"); paises[f]=teclado.next(); } } public void ordenar() { for(int k=0;k<4;k++) { for(int f=0;f<4-k;f++) { if (paises[f].compareTo(paises[f+1])>0) { String aux; aux=paises[f]; paises[f]=paises[f+1]; paises[f+1]=aux; } } } } public void imprimir() { System.out.println("Paises ordenados en forma alfabética:"); for(int f=0;f<paises.length;f++) { System.out.println(paises[f]); } } public static void main(String[] ar) { PruebaVector14 pv=new PruebaVector14(); pv.cargar(); pv.ordenar(); pv.imprimir(); } }

Definimos un vector de tipo String:

private String[] paises;

Lo creamos indicando que almacenará cinco elementos:

paises=new String[5];

Procedemos a cargar el vector:

for(int f=0;f<paises.length;f++) { System.out.print("Ingrese el nombre del pais:"); paises[f]=teclado.next(); }

Para el ordenamiento utilizamos el método compareTo para verificar si tenemos que intercambiar las componentes:

if (paises[f].compareTo(paises[f+1])>0) {

En el caso que si tenemos que intercambiarla utilizamos un auxilir de tipo String:

String aux; aux=paises[f]; paises[f]=paises[f+1]; paises[f+1]=aux;

Problemas propuestos

Realizar un programa en Java que almacene en dos vectores paralelos el nombre y la venta del vendedor ,determine
1. el procedimiento para ordenar por ventas , e imprima las ventas del mejor vendedor
2. el procedimiento de ordenar alfabèticamente e imprimir la venta del primero y del ultimo vendedor
Cargar un vector de n elementos de tipo entero. Ordenar posteriormente el vector, y obtener el promedio
Programa Java que lea 10 números enteros por teclado y los guarde en un array. Calcula y muestra la media de los números que estén en las posiciones pares del array.
Declara un array tipo int (entero) denominado numerodecoches que contenga 24 variables. Declara una variable tipo int (entero) que se llame r. Establece el valor de r en 2 y el valor de numerodecoches para un localizador de valor r en 23. Procede a mostrar en pantalla un mensaje que indique cuál es la hora r y el número de coches para la hora r. Finalmente, modifica únicamente la asignación de valor a r de modo que en vez de 2 sea 21 y ejecuta de nuevo el programa

TRABAJO CON VECTORES PARALELOS

Cuando se tienen vectores paralelos y se ordena uno de ellos hay que tener la precaución de intercambiar los elementos de los vectores paralelos.

Problema 1:

Confeccionar un programa que permita cargar los nombres de 5 alumnos y sus notas respectivas. Luego ordenar las notas de mayor a menor. Imprimir las notas y los nombres de los alumnos.

Programa:

import java.util.Scanner; public class PruebaVector16 { private Scanner teclado; private String[] nombres; private int[] notas; public void cargar() { teclado=new Scanner(System.in); nombres=new String[5]; notas=new int[5]; System.out.println("Carga de nombres y notas"); for(int f=0;f<nombres.length;f++) { System.out.print("Ingese el nombre del alumno:"); nombres[f]=teclado.next(); System.out.print("Ingrese la nota del alumno:"); notas[f]=teclado.nextInt(); } } public void ordenar() { for(int k=0;k<notas.length;k++) { for(int f=0;f<notas.length-1-k;f++) { if (notas[f]<notas[f+1]) { int auxnota; auxnota=notas[f]; notas[f]=notas[f+1]; notas[f+1]=auxnota; String auxnombre; auxnombre=nombres[f]; nombres[f]=nombres[f+1]; nombres[f+1]=auxnombre; } } } } public void imprimir() { System.out.println("Nombres de alumnos y notas de mayor a menor"); for(int f=0;f<notas.length;f++) { System.out.println(nombres[f] + " - " + notas[f]); } } public static void main(String[] ar) { PruebaVector16 pv=new PruebaVector16(); pv.cargar(); pv.ordenar(); pv.imprimir(); } }

Definimos los dos vectores:

private String[] nombres; private int[] notas;

Creamos los dos vectores paralelos con cinco elementos cada uno:

nombres=new String[5]; notas=new int[5];

En el proceso de ordenamiento dentro de los dos for verificamos si debemos intercambiar los elementos del vector notas:

for(int k=0;k<notas.length;k++) { for(int f=0;f<notas.length-1-k;f++) { if (notas[f]<notas[f+1]) {

En el caso que la nota de la posición 'f' sea menor a de la posición siguiente 'f+1' procedemos a intercambiar las notas:

int auxnota; auxnota=notas[f]; notas[f]=notas[f+1]; notas[f+1]=auxnota;

y simultánemamente procedemos a intercambiar los elementos del vector paralelo (con esto logramos que los dos vectores continuen siendo vectores paralelos):

String auxnombre; auxnombre=nombres[f]; nombres[f]=nombres[f+1]; nombres[f+1]=auxnombre;

Como vemos utilizamos dos auxiliares distintos porque los elementos de los dos vectores son de distinto tipo (int y String)

Si deseamos ordenar alfabéticamente la condición dependerá del vector nombres.

Problemas propuestos

Cargar en un vector los nombres de 5 paises y en otro vector paralelo la cantidad de habitantes del mismo. Ordenar alfabéticamente e imprimir los resultados. Por último ordenar con respecto a la cantidad de habitantes (de mayor a menor) e imprimir nuevamente.

Ordenamiento por Inserción directa

El método de ordenación por inserción directa consiste en recorrer todo el array comenzando desde el segundo elemento hasta el final. Para cada elemento, se trata de colocarlo en el lugar correcto entre todos los elementos anteriores a él o sea entre los elementos a su izquierda en el array.

Dada una posición actual p, el algoritmo se basa en que los elementos A[0], A[1], ..., A[p-1] ya están ordenados.

De forma gráfica el proceso que sigue el método de inserción directa es el siguiente:

El método de Ordenamiento por inserción directa en Java es el siguiente:

public static void insercionDirecta(int A[]){

int p, j;

int aux;

for (p = 1; p < A.length; p++){ // desde el segundo elemento hasta

aux = A[p]; // el final, guardamos el elemento y

j = p - 1; // empezamos a comprobar con el anterior

while ((j >= 0) && (aux < A[j])){ // mientras queden posiciones y el

// valor de aux sea menor que los

A[j + 1] = A[j]; // de la izquierda, se desplaza a

j--; // la derecha

}

A[j + 1] = aux; // colocamos aux en su sitio

}

En el peor de los casos, el tiempo de ejecución en O(n2).

En el mejor caso (cuando el array ya estaba ordenado), el tiempo de ejecución de este método de ordenamiento es O(n).

El caso medio dependerá de cómo están inicialmente distribuidos los elementos. Cuanto más ordenada esté inicialmente más se acerca a O(n) y cuanto más desordenada, más se acerca a O(n2).

El peor caso el método de inserción directa es igual que en los métodos de burbuja y selección, pero el mejor caso podemos tener ahorros en tiempo de ejecución.