Las listas doblemente enlazadas son estructuras de datos semejantes a las listas enlazadas simples.
La asignación de memoria es hecha al momento de la ejecución.
las listas doblemente enlazadas a diferencia de la listas simples, contienen dos punteros. uno que apunta la nodo siguiente y el otro apunta al nodo anterior
¿que es el ordenamiento por inserción?:
es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria.
este algoritmo consiste en ir escogiendo cada número y compararlo con el anterior de derecha a izquierda, si el número de la derecha es mayor que el de la izquierda entonces los números cambiaran de lugar hasta que el arreglo se encuentre completamente ordenado.
 |
| imagen tomada de wikipedia |
código de ordenamiento insert sort arreglos:
este código se realizo en netBeans 8.2
package ejemplometododeinsercion;
import java.util.Scanner;
import javax.swing.JOptionPane;
public class EjemploMetodoDeInsercion {
public static void main(String[] args) {
Scanner entrada = new Scanner(System.in);
int arreglo[];
int nElementos, pos, aux;
nElementos = Integer.parseInt(JOptionPane.showInputDialog("INGRESE EL NUMERO DE ELEMENTOS: "));
arreglo = new int[nElementos];
System.out.print("DIGITE EL ARREGLO: \n");
for (int i = 0; i < nElementos; i++) {
System.out.print((i + 1) + ".DIGITE UN NUMERO: ");
arreglo[i] = entrada.nextInt();
}
//ORDENAMIENTO POR INSERCION
for (int i = 0; i < nElementos; i++) {
pos = i;
aux = arreglo[i];
while ((pos > 0) && (arreglo[pos - 1] > aux)) {
arreglo[pos] = arreglo[pos - 1];
pos--;
}
//ACTUALIZAR EL NUMERO
arreglo[pos] = aux;
}
System.out.print("\nORDEN ASCENDENTE: ");
for (int i = 0; i < nElementos; i++) {
System.out.print(arreglo[i] + " , ");
}
System.out.print("");
System.out.print("\nORDEN DESENDENTE: ");
for (int i = (nElementos - 1); i >= 0; i--) {
System.out.print(arreglo[i] + " , ");
}
System.out.print("");
}
}
código de ordenamiento por insert sort para listas dobles
public void InserSort(){
nodo p = this.cab.getSig(); // nodo p se ubica un posición después de la cabeza
nodo m = p.getSig(); //nodo m se ubica una posición después de nodo p
while(p != null){ //si la lista no esta vacía que entre a ordenar
while(p.getAnt().getId > p.getId() && p.getAnt() != null){ //p en posición anterior en mayor a ID y si p en su posición anterior es diferente de null p sera igual a la posición anterior
p = this.exchange(p.getAnt(), p); // se llama al método exchange para mover los nodos
} //el proceso se repite hasta que p ya no tenga datos los cuales intercambiar
}
p = m; // p y m sseran iguales cuando se haya terminado todo el intercambio de datos
if(p != null)
}
¿que es el ordenamiento por shaker sort ?
El algoritmo de ordenación por el método Shaker, también conocido como "Cocktail" o "Sacudida" es una mejora del método de la burbuja en la cual el proceso se realiza tanto desde la primera posición a la última del arreglo como en sentido inverso, evitando así que los elementos más pequeños tarden un mayor tiempo en "ascender" a las posiciones superiores.
Este método permite organizar, ordenamiento e intercambio directo de elementos del arreglo. Prácticamente la idea básica de este algoritmo cociste en intercambiar, mezclar. existen dos formas en que se pueda realizar este algoritmo cada pasada tiene 2 pasadas.En la primera pasada, es de derecha a izquierda se trasladan los elementos mas pequeños hacia la izquierda del arreglo (almacenando la posición del ultimo elemento intercambiado) en la segunda pasada de izquierda a derecha se trasladan los elementos mas grandes hacia la derecha del arreglo almacenando en otra variable la posición del ultimo elemento intercambiado. Este método de ordenamiento permite visualizar la forma, en la cual se puede organizar datos desordenados que al final serán ordenados de una forma secuencial.
código de ordenamiento shaker sort arreglos:
presentado por: Cristhian Sanchez y Angel Diaz
código de ordenamiento por insert sort para listas dobles
nodo p = this.cab.getSig(); // nodo p se ubica un posición después de la cabeza
nodo m = p.getSig(); //nodo m se ubica una posición después de nodo p
while(p != null){ //si la lista no esta vacía que entre a ordenar
while(p.getAnt().getId > p.getId() && p.getAnt() != null){ //p en posición anterior en mayor a ID y si p en su posición anterior es diferente de null p sera igual a la posición anterior
p = this.exchange(p.getAnt(), p); // se llama al método exchange para mover los nodos
} //el proceso se repite hasta que p ya no tenga datos los cuales intercambiar
}
p = m; // p y m sseran iguales cuando se haya terminado todo el intercambio de datos
if(p != null)
}
¿que es el ordenamiento por shaker sort ?
El algoritmo de ordenación por el método Shaker, también conocido como "Cocktail" o "Sacudida" es una mejora del método de la burbuja en la cual el proceso se realiza tanto desde la primera posición a la última del arreglo como en sentido inverso, evitando así que los elementos más pequeños tarden un mayor tiempo en "ascender" a las posiciones superiores.
Este método permite organizar, ordenamiento e intercambio directo de elementos del arreglo. Prácticamente la idea básica de este algoritmo cociste en intercambiar, mezclar. existen dos formas en que se pueda realizar este algoritmo cada pasada tiene 2 pasadas.En la primera pasada, es de derecha a izquierda se trasladan los elementos mas pequeños hacia la izquierda del arreglo (almacenando la posición del ultimo elemento intercambiado) en la segunda pasada de izquierda a derecha se trasladan los elementos mas grandes hacia la derecha del arreglo almacenando en otra variable la posición del ultimo elemento intercambiado. Este método de ordenamiento permite visualizar la forma, en la cual se puede organizar datos desordenados que al final serán ordenados de una forma secuencial.
 | |
|
package ventanas;
import javax.swing.JOptionPane;
public class ShakerSort7 {
// Se declara las variables las cuales van a ser utilizadas en el metodo
public static int derecha, izquierdo, ultimo;
//declaracion del arreglo
int numeros[] = new int[6];
//se inicializa la posicion del arreglo
int pos = 0;
//creamos un metodo que permita guardar numeros
public void guardarNumero() {
//se llaman los datos de entrada que ingresa el usuario el la ventana
String numerSt = VentanaShaker.jTextFieldNumero.getText();
int n = Integer.parseInt(numerSt);
//donde se guarda los numeros ingresados
numeros[pos] = n;
//incrementa o pasa a la siguiente posicion del arreglo para guardar
pos++;
// mensaje que informa que dicho numero ingresado es guardado
JOptionPane.showMessageDialog(null, "numero Agregado Exitosamente!!!");
//llama al metodo siguiente
imprimirNumeros();
}
//metodo para listar el arreglo en el area de texto
public void imprimirNumeros() {
//String se la crea para mostrar los datos o concardenarlos
String cad = "";
// El for de imprimir desodenados
for (int i = 0; i < numeros.length; i++) {
cad = cad + numeros[i] + "\t";
}
cad += "\n";
//dentro del jTexArea se van a mostrar los datos desordenados o ingresados por el usuario
VentanaShaker.jTextAreaDatos.setText(cad);
}
//se crea un nuevo metodo que permita recorrer el arreglo para empezar a ordenar
public void recoorer() {
izquierdo = 1;
derecha = numeros.length;
ultimo = numeros.length - 1;
do {
for (int i = numeros.length - 1; i > 0; i--) {
//permite recorer el arreglo de derecha a izquierda
if (numeros[i - 1] > numeros[i]) {
//La variable auxiliar es a que permite hacer el intercambio de posicion
int aux = numeros[i];
numeros[i] = numeros[i - 1];
numeros[i - 1] = aux;
ultimo = 1;
}
}
izquierdo = ultimo + 1;
for (int k = 1; k < numeros.length; k++) {
//permite hacer el recorrico o sacudida de izquierda a derecha
if (numeros[k - 1] > numeros[k]) {
int aux = numeros[k];
numeros[k] = numeros[k - 1];
numeros[k - 1] = aux;
ultimo = k;
}
}
derecha = ultimo - 1;
//este ciclo permite verificar si ya esta ordenado el arreglo
} while (derecha >= izquierdo);
}
public void concardenar() {
String cad = "";
recoorer();
//el for nuevamente recorre el arreglo para mostrar sus los datos ordenados
for (int i = 0; i < numeros.length; i++) {
cad = cad + numeros[i] + "\t";
}
cad += "\n";
//permite mostrar en el tex area los datos ordenados
VentanaShaker.Ordenador.setText(cad);
}
}
diagrama de como funciona shaker sort en listas dobles
código de ordenamiento por shaker sort para listas dobles
public void ShakerSort(){
nodo pi = this.cab; //pi se ubica en cabeza
nodo m = pi; // m si iguala a p
// evaluamos la condicion para cuando m sea diferente de null con el while
while(m.getSig() != null){
m = m.getSig();
}
while(pi != m && pi.getAnt() != m){
//nodo p lo ponemos en la posición de pi
nodo p = pi;
//hacemos la comparación para cuando se cumpla la condición del while hasta el final
while(p != m){
//ponemos la condición para cuando se cumpla la condición del while
if(p.getId() > p.getSig().getId()){
if(p == this.cab){
this.cab = p.getSig();
}
if(p == pi){
pi = p.getSig();
}
if(p.getSig() == m){
m = p;
}
//llamanos al metodo de intercambio para mover los nodos
p = this.exchange(p, p.getSig());
}
p = p.getSig();
//se termina el recorrido
}
//se inicia el otro recorrido
//ahora nos de volvemos del final hasta el inicio
m = m.getAnt();
//inicialisamos al nodo q en m
nodo q = m;
//evaluamos la condicion con el while para que haga su recorrido q
while(q != m){
// condiciones para cuando qie el while pueda mover a q
if(q.getId() < q.getAnt().getId()){
if(q == m){
m = q.getAnt();
}
if(q.getAnt() == this.cab){
this.cab = q;
}
if(q.getAnt() == pi){
pi=q;
}
//llamamos el metodo de intercambio
q = this.exchange(q.getAnt(), q);
}else{
q = q.getAnt();
}
}
pi = pi.getSig();
}
}
}
public void ShakerSort(){
nodo pi = this.cab; //pi se ubica en cabeza
nodo m = pi; // m si iguala a p
// evaluamos la condicion para cuando m sea diferente de null con el while
while(m.getSig() != null){
m = m.getSig();
}
while(pi != m && pi.getAnt() != m){
//nodo p lo ponemos en la posición de pi
nodo p = pi;
//hacemos la comparación para cuando se cumpla la condición del while hasta el final
while(p != m){
//ponemos la condición para cuando se cumpla la condición del while
if(p.getId() > p.getSig().getId()){
if(p == this.cab){
this.cab = p.getSig();
}
if(p == pi){
pi = p.getSig();
}
if(p.getSig() == m){
m = p;
}
//llamanos al metodo de intercambio para mover los nodos
p = this.exchange(p, p.getSig());
}
p = p.getSig();
//se termina el recorrido
}
//se inicia el otro recorrido
//ahora nos de volvemos del final hasta el inicio
m = m.getAnt();
//inicialisamos al nodo q en m
nodo q = m;
//evaluamos la condicion con el while para que haga su recorrido q
while(q != m){
// condiciones para cuando qie el while pueda mover a q
if(q.getId() < q.getAnt().getId()){
if(q == m){
m = q.getAnt();
}
if(q.getAnt() == this.cab){
this.cab = q;
}
if(q.getAnt() == pi){
pi=q;
}
//llamamos el metodo de intercambio
q = this.exchange(q.getAnt(), q);
}else{
q = q.getAnt();
}
}
pi = pi.getSig();
}
}
}
presentado por: Cristhian Sanchez y Angel Diaz
No hay comentarios.:
Publicar un comentario