Foro sobre Java SE > Duda sencilla sobre arrays.
Puestos a desarrollar, creo que usar lo que ya existe en el JDK es lo más sencillo, y lo más rápido.
public class Test {
public static void main(String[] args) {
// números diferentes
final Map<Integer, Void> numeros = new TreeMap<>();
numeros.put(8, null);
numeros.put(2, null);
numeros.put(7, null);
numeros.put(5, null);
for (Iterator<Integer> it = numeros.keySet().iterator(); it.hasNext();) {
System.out.println("número= " + it.next());
}
final Set<Integer> set = numeros.keySet();
final Integer[] array = set.toArray(new Integer[set.size()]);
System.out.println("array: " + Arrays.toString(array));
}
// números duplicados
final List<Integer> numeros2 = new ArrayList<>();
numeros2.add(8);
numeros2.add(2);
numeros2.add(7);
numeros2.add(5);
numeros2.add(2);
numeros2.add(7);
Collections.sort(numeros2);
for (Iterator<Integer> it = numeros2.iterator(); it.hasNext();) {
System.out.println("número2= " + it.next());
}
final Integer[] array2 = numeros2.toArray(new Integer[numeros2.size()]);
System.out.println("array2: " + Arrays.toString(array2));
}
choces
Muchas gracias por contestar...
la solución de usar estructuras dinámincas la tengo clara...lo que pasa que sólo podemos usar estructuras estáticas (docencia) para aprender bien el uso de las estáticas....
Lo del índice lo había pensado....pero mi inquietud era con el algoritmo de ordenación por inserción...definido en wikipedia...y muchas páginas....ellos parten con el array vacío y conforme vas insertando van viendo su posición correcta...pero al tener inicializado el vector a 0....falla....
Si véis cualquier libro que hable sobre dicho algoritmo veréis lo mismo..un array vacío y va insertando elementos en la posición que toca...por eso se llama inserción....
en la wikipedia pone lo mismo...se parte de un array con un elemento....aquí tenemos n elementos (tamaño del array) y además con valor 0....pues no me gusta la verdad...dicho algoritmo así falla...
La solución con Integer la había pensado...así tengo el array con elementos null, así más sencillo.
Gracias.
Saludos.
shao
Aquí siguen varios ejemplos de implementación de este algoritmo en Java.
http://www.roseindia.net/java/beginners/arrayexamples/insertionsort.shtml
http://en.literateprograms.org/Insertion_sort_(Java)
https://gist.github.com/2044143
http://www.cs.washington.edu/education/courses/cse373/01wi/slides/Measurement/sld010.htm
http://www.brilliantsheep.com/insertion-sort-java-implementation/
Podría seguir así hasta cansarme. Esa insistencia tuya en que se parte de un array "vacío" no tiene nada que ver con el Insertion Sort.
Lo que sigue está tomado de la página de Wikipedia que mencionas:
int temp, j;
for (int i=1; i < vector.length; i++){
temp = vector[i];
j = i-1;
while (j >= 0 && vector[j] > temp){
vector[j + 1] = vector[j];
j--;
}
vector[j+1] = temp;
}
¿Me puedes decir dónde está ese array "vacío"?
choces
Os pongo una foto de cómo lo explica el libro de texto mediante un ejemplo...doy a entender que el array está vacío....
http://img837.imageshack.us/img837/9902/insertionsort.jpg
Saludos y disculpar mi insistencia..pero este libro me ha dado a entender eso....
shao
Disculpar...no me había dado cuenta de la imagen...se ve bastante mal..os la vuelvo a pegar pero mejor ....
http://img72.imageshack.us/img72/9902/insertionsort.jpg
Saludos.
shao
Eso no es el Algoritmo de Ordenación por Inserción. Es otra cosa diferente.
No entiendo qué pretende enseñar con ese ejemplo, porque lo habitual en la vida real es que se tenga un array con datos cualesquiera, y se desee ordenarlos de acuerdo con un criterio de ordenación determinado. Ahí es dónde el Algoritmo de Ordenación por Inserción tiene su razón de ser; lo mismo que otros algoritmos más eficientes.
Dado un array tal como el que sigue:
private final int[] numeros = {4,7,3,6,2};
Si se aplica el algoritmo, tal y como se detalla en los enlaces de más arriba, a numeros, se obtiene un array ordenado.
Lo mismo que si se hace, simplemente, Arrays.sort(numeros);
Lo que acaba pasando al final, es que se "aprenden" muchos "algoritmos", y se desconoce cómo resolver problemas reales, con los medios que proporciona Java.
choces
No sé a qué se referirá...pero aquí parece que pretenden hacer parecido...o no especifican muy claro si ya están o no los datos:
http://www.mcgraw-hill.es/bcv/guide/capitulo/8448198441.pdf
Pero yo le veo sentido...a mi me gustaría que conforme estoy leyendo datos...ya sea de teclado, de un fichero o de donde sea..me los vaya insertando ordenadamente..y no insertarlos desordenadamente y luego proceder a ordenarlos...
shao
bueno, estaba leyendo el algoritmo de ordenacion por inserción, como yo soy amante de conocer la esencia del algoritmo antes que la implementacion del mismo en un lenguaje.
segun entiendo el algoritmo se basa, en buscar la posicion correcta del nuevo elemento de tal forma que al ser insertado, el vector siga insertado,
la imagen que proporciono @shao, creo que explica muy bien este hecho solo que @shao lo malinterpretastes. lo que dice esa imagen es:
si no hay elementos inserte al inicio
si hay elementos busque la posicion que debe ir el nuevo elemento
acomode los nuevos elementos para dejar espacio al nuevo elemento.
inserte el elemento.
la clase que envie unos post atras hace esto mismo.
como te dije la base de este algoritmo son 2 acciones buscar la posicion, y mover
los elementos, para hacer espacio tal y como esta en la imagen.
explico un poco mi codigo.
public int buscarCasilla(int data[], int tope, int dato) {
//la data es el vector en que se va insertar el elemento
//tope es el limite superior hasta donde se hara la busqueda
//dato es el elemento a insertar
for (int i = 0; i < tope; i++) {
if (data[i] > dato) {
//como es ordenamiento ascedente verifico si el valor en la casilla i es mayor que dato
//si quisiera descedente usaria el operador de comparacion menor que
return i;
}
}
//si dato es mayor que todos los valores anteriores
//se inserta en el limite superior
return tope;
}
ahora la otra funcion desplazar, como vistes @shao en la imagen que pasastes los elementos siempre se desplazan una casilla hacia la derecha (->) dejando espacio para el nuevo elemento y es lo que hace esto
public void desplazarDerecha(int inicio, int ultimo, int data[]) {
//inicio, posicion del vector de donde debe enpesarse a mover
//ultimo, posicion del vector del ultimo elemento a mover
int copy[] = new int[data.length];//array que nos servira para hacer el desplazamiento
System.arraycopy(data, 0, copy, 0, copy.length);//se copia el vector original a la copia
System.arraycopy(copy, inicio, data, inicio + 1, ultimo - inicio);
//en el vector original se pega la porcion de datos a mover desplazado
//una casilla a la derecha
}
bueno ya de ultimo se inserta el valor dado por posocion
datos[posicion] = dato;
//y se aumenta el indice
indice++;
@shao, probalo, se que no es la mejor implementacion pero creo que te dara varias pistas para entender el algoritmo.
Lo que tienes que tener claro que el algoritmo solo mueve los elementos insertados no los otros es decir el autor puso las casillas en blanco pero bien les pudo poner el valor de 0 por ejemplo que no afecta al algoritmo, así que usar una variable para contar los elementos insertados es indispensable.
porque de otra manera tendras el problema expuesto, incluso no solo en java en cualquier lenguaje
porque cuando haces esto int v[]=new int[n]; lo que estas diciendo es que se reserve n casillas continuas de tamaño del tipo de dato en este caso int.
java pone en estas casillas valores de 0 otros lenguajes dejan lo que están como el lenguaje c que si declaras un vector podias tener esto cuando lo corrieras sin inicializae
{-1,-86,189} y en otra corrida con el mismo programa tendrias {0,3,-19}. es conclusión sea cual sea el lenguaje que declares un vector siempre las casillas tendra un valor comunmente se llama basura.
bueno espero verte ayudado.
saludos.
jhosep
Si te fijas en el apartado 10.4.2 del libro, "... el array a[] que se va a ordenar crecientemente y el número de elementos n."
Si lees la lógica con atención, verás que direcciona en todo momento los elementos existentes en el array. En ningún momento se asignan valores externos a ninguna posición del array.
El problema es que la explicación inicial, con esos gráficos, es confusa: quiere detallar lo que hace el algoritmo, pero da la impresión de que cada elemento que se inserta procede "de algún sitio" ajeno al propio array.
Los datos se insertan en las estructuras, por defecto de manera desordenada (excepto en los TreeMap y LinkedHashMap) y se ordenan solo si es necesario. En lo referente al JDK actual.
No hay nada que impida crear una clase que maneje colecciones de otra manera, tal y como dices, por ejemplo, usando una List<E> como ésta:
public class SortedList<E> extends AbstractList<E> {
private ArrayList<E> internalList = new ArrayList<E>();
// Note that add(E e) in AbstractList is calling this one
@Override
public void add(int position, E e) {
internalList.add(e);
Collections.sort(internalList, null);
}
@Override
public E get(int i) {
return internalList.get(i);
}
@Override
public int size() {
return internalList.size();
}
}
Que no caben muchas dudas de que es incomparablemente más lento que crear la lista desordenada, y ordenarla de una sola pasada al final.
En general, la necesidad de elementos ordenados en una List<E>, a medida que se crea, no es tan usual como para que se haya incluido en el JDK. Lo mismo puede decirse de los arrays. Para cuando la ordenación es imprescindible, se usan los métodos apropiados.
choces
lo que dice @chose es cierto, todos los algoritmos de ordenacion siempre se basan en tener un array desordenado, en el cual se realiza el trabajo, el algoritmo de ordenacion por inserccion que veo en wikipedia nos es muy distinto al conocido algoritmo de burbuja de hecho tiene la misma complejida computacional O(n^2).
pero eso no quiere decir que no se pueda armar un algoritmo para que el nuevo dato no desordene el array, el algoritmo que yo te platee revisándolo un poco es de O(n), lo que es un gran costo ya que si el array es muy grande costara más insertar un nuevo elemento, aparte que duplico el array para desplazar los elementos, realmente es algo impractico,y lo que dice @chose es peor porque el algoritmo que ofrece java para ordenar es de n*log(n), lo que haría la inserción más lenta.
asi que definitivamente estoy de acuerdo con @chose ordenar al insertar no es buena idea XD.
pero por fines educativos esta bien tener noción sobre los distinto algoritmos de ordenamiento y estructuras de datos, ya que este conocimiento nos permitirá usar de mejor manera las librerías que vienen en los lenguajes, como lo es la api collection de java. O también para que un genio logre diseñar un mejor algoritmo a los ya existentes uno nunca sabe.
asi que en conclusión @shao, el problema no es que java inicialize automáticamente a 0 las casillas de los vectores, sino que has malentendido el algoritmo.
en el libro que estas leendo no viene una implantación en pseudocodigo, diagrama de flujo, o en un lenguaje especifico de programación?, que me parece raro que los pocos libros que he leído de ese tipo siempre traen la implantación, mínimo en pseudocodigo .
Si trae deberías publicarlo aquí, así aparte que te ponemos ayudar mejor, quien quita que aprendemos algo nuevo
saludos
jhosep
En esta página hay abundante información sobre algoritmos de ordenación, con una representación visual animada sobre el funcionamiento de cada uno, en condiciones iniciales diversas.
http://www.sorting-algorithms.com/
choces
Muchas gracias por contestar...
Entiendo que con un array desordenador va perfectamente...pensaba que este algoritmo al llamarse insercion...cada vez que insertabas un elemento lo insertaba en la posición adecuada...y al ver dicho gráfico del libro...así lo entendí...pero veo que no..que inicialmente hay un array con valores y te los ordena, nada de insertar un nuevo elemento de fuera...
La verdad que el libro no trae nada más...es para un Ciclo Formativo de Grado Superior y sólo te los nombra y cuenta un poco....sólo da el código del de la burbuja...
Muchas gracias de nuevo por vuestra aportación...asi da gusto comentar temas en foros...gracias!
Saludos.
shao
me alegro mucho @shao que te haya servido lo que se aporto.
saludos.
jhosep
bueno se me olvidaba la salida del programa con los datos de prueba es esta
como se esperaba:
{9}
{9,10}
{6,9,10}
{6,7,9,10}
{-1,6,7,9,10}
{-2,-1,6,7,9,10}
{-2,-1,5,6,7,9,10}
{-2,-1,5,6,7,9,10,14}
{-2,-1,5,6,7,9,10,14,15}
{-2,-1,5,6,7,9,10,11,14,15}
esos numeros son los datos que tiene el vector en cada inserción, solo se imprime los datos hasta donde esta indice.
saludos