Distribución Simple

Métodos De Ordenamiento Por Distribución

Distribución Simple

                               Descripción

Ordena el vector tomando cada número e insertándolo en la posición que toma su valor, es decir, si tengo un cinco en el arreglo; lo pongo en la posición cinco, es decir, lo que vale el elemento es la posición en la que se coloca. Por supuesto, no se podrán ordenar los arreglos que tengan valores repetidos y el vector necesita estar del tamaño del número más grande que se encuentre en él.

                             Algoritmo

Método Gráfico

Métodos De Ordenamiento Por Distribución

Método Gráfico

                             Descripción

•        Un grafo es un diagrama que consiste de puntos (llamados nodos) unidos por líneas (llamadas arcos). Cada arco en un grafo se especifica por medio de un par de nodos.
•        Según la figura anterior, los nodos serian (A,B,C,D,F) y los arcos[(A,B),(A,C),(A,D),(C,D),(C,F)]. Si los pares de nodos que conforman los arcos son pares ordenados, el grafo se denomina grafo directo o dígrafo.
•        La cabeza de cada flecha representa el segundo nodo en el par de nodos ordenados que hacen un arco, mientras que la cola de la flecha representa el primer nodo en el par.
•        Un nodo n se dice que es incidente a un arco x, si n es uno de los dos nodos en el par ordenado de nodos que componen x. (también se dice que x es incidente a n). El grado de un nodo es el número de arcos incidentes a él.
•        Un nodo n es adyacente al nodo n si existe un arco de m a n.
•        Una relación R en un conjunto A es un grupo de pares ordenados de elementos de A. Si (x,y) es un miembro de la relación R, entonces x se dice que está relacionado con y en R.
•        Una relación se puede representar por un grafo en el cuál los nodos representan el conjunto fundamental y los arcos representan los pares ordenados de la relación.

                               Algoritmo

Método De Ordenamiento Base RADIX

Métodos De Ordenamiento Por Distribución

Método De Ordenamiento Base RADIX

                                Descripción

Este algoritmo está basado en los valores  reales de  los dígitos  de acuerdo a la posición que ocupan los  números que  son  ordenados.  Para  cada dígito de las cifras a ordenar se efectúan  los  siguientes pasos, comenzando con el dígito menos significativo y  terminando con el dígito más significativo.  Se toma  cada número  en el orden  original y se coloca en una de las 10 colas dependiendo  del  valor  del  dígito que  se  esté procesando, después comenzando con la cola de los números con dígitos  0 y  terminando con los de dígito 9 se regresan al arreglo original. Cuando se efectúa este proceso para cada dígito  al arreglo  está ordenado.  M es el número de dígitos que forman las cifras a ordenar.

                              Algoritmo

Inicio

ArregloRadix A[], n, d)

para i 1 hasta <=d i--

A=CountingShort (A, n, 10,i)

Fin RadixShort 

CountingShort (A[ ], n, k,digit)

C[ ] =0

PARA J = 1 HASTA J<=N j++

C[ A[j][digit]]

PARA k = 2 HASTA k<=N j++

C[i]+=C[i - 1]

para j=n hasta >=1 j--

e=A[j][digit]

B[C[e]]= A[j]

C[e] --

RETORNAR B

Fin CountingShort

                                   Código:

public class Radix 

//Se declara la funcion principal del metodo 

{ void Radix (int[] arr)

{ 

//Si el arreglo se inica en cero//

if(arr.length==0)

return;

//Se declaran los arreglos y se le asignan los valores//

int[][] np = new int[arr.length][2];

int[] q = new int[0x100];

int i,j,k,l,f =0;

//Se inicia su tamaño en cero hasta cuatro//

for(k=0;k<4;k++)

{ 

//Se inicia con el elemento que este mas a la izquierda //

for(i=0;i<(np.length-1);i++)

np[i][1]= i+1;

np[i][1]=-1;

for(i=0;i<q.length;i++)

q[i]=-1;

for(f=i=0;i<arr.length;i++){

j =((0xFF<<(k<<3))&arr[i])>>(k<<3);

if(q[j]==-1)

l = q[j]= f;

else {

l = q[j];

while(np[l][1]!=-1)

l = np[l][1];

np[l][1]= f;

l = np[l][1];

}

f = np[f][1];

np[l][0]= arr[i];

np[l][1]=-1;

}

for(l=q[i=j=0];i<0x100;i++)

for(l=q[i];l!=-1;l=np[l][1])

arr[j++]= np[l][0];

} 

void main(String[] args)

{ 

//Función que me muestra el arreglo ordenado //

int i;

int[] arr = new int[15]; 

System.out.print("original: "); 

for(i=0;i<arr.length;i++)

{ 

//Funcion de arreglos aleatorios //

arr[i]=(int)(Math.random()*1024); 

System.out.print(arr[i]+" "); 

} 

Radix (arr); 

System.out.print("\nordenados: "); 

for(i=0;i<arr.length;i++) 

System.out.print(arr[i]+" "); 

System.out.println("\nHecho."); 

}

}

Métodos De Ordenamiento Por Distribución Y por Intercalación

Métodos De Ordenamiento Por Distribución Y por Intercalación

Trabajo realizado por:

Edwin H. Rubio Lozada

Carlos A. Valera Cueto

Smith Suarez Vargas

Lista de referencias

https://sites.google.com/site/estdatjiq/home/unidad-v

https://estructuradedatositp.wikispaces.com/5.2.1.+Algoritmo+de+ordenamiento+externo

+INTERCALACION

http://es.tldp.org/Tutoriales/doc-programacion-algoritmos-ordenacion/alg_orden.pdf

https://prezi.com/v1zwhdn4f4t7/algoritmo-de-ordenamiento-externo-intercalacion/

https://www.youtube.com/watch?v=lBrFTBUt9ww

Ordenamiento por Intercalación Cuadrática

Códigos del Métodos de Ordenamiento por Intercalación

Intercalación Cuadrática:

                                Descripción

La idea central de este algoritmo consiste en realizar sucesivas particiones y fusiones a un arreglo para producir secuencias ordenadas de longitud cada vez mayor. En la primera  pasada la longitud de la partición es de 1 y la fusión produce una secuencia ordenada de longitud 2. En la segunda pasada las longitudes se duplican y este proceso se repite hasta que la longitud de la secuencia de la partición sea mayor o igual que el número de elementos del arreglo original.

Algoritmo

1.- Inicio 

2.- Dividir el arrgelo en N subarreglos de tamaño 1 e intercalar pares adyacentes 

separados de los subarreglos. 

3.- Incrementar las particiones del arreglo en duplos, cuadruplos, etcetera, y asi 

sucesivamente.

4.- Repetir el proceso hasta que solo quede un arreglo de tamaño N. 


5.- Fin del algoritmo.

Código

import java.util.Scanner;  

import java.math.*;  

public class Main {  

    public static void main(String[] args) {  

      //Se declara la variable de ingreso de los valores //

      Scanner sc=new Scanner(System.in);  

      //Muestra en pantalla el dato a ingresar coeficiente cuadratico//

      System.out.println("Ingresa coeficiente cuadratico");  

      int a= sc.nextInt();  

       //Muestra en pantalla el dato a ingresar coeficiente lineal//

      System.out.println("Ingresa coeficiente lineal");  

      int b= sc.nextInt();  

      //Se ingresa el valor constante//    

      System.out.println("Ingresa constante");  

      int c= sc.nextInt();  

      //A la variable se le hace la operacion de elevarla a la potencia//

      double disc=Math.pow(b,2)-4*a*c;  

      //Se hace la validacion de la constante//

        if(a!=0){  

         //Si dicho valor es un valor negativo corresponde a numeros imaginarios// 

         if(disc<0){  

          System.out.println("Tiene raices imaginarias");  

          }else{  

          double x1=(-b+Math.sqrt(disc))/(2*a);  

          double x2=(-b-Math.sqrt(disc))/(2*a);  

          System.out.println("X1 = "+x1+" X2 = "+x2);  

        }  

      }else{  

         

      //Si cumple con la condiciones se muestra el resultado//

      System.out.println("El coeficiente cuadratico debe ser diferente de 0");  

      }        

      }  

} 

Ordenamiento por Intercalación Merge

Códigos del Métodos de Ordenamiento por Intercalación:

Intercalación Merge:

                               Descripción

Cuando se dispone de dos vectores ya ordenados y se desea obtener un tercer vector también ordenado, se puede realizar la ordenación con un método denominado Mezcla (Merge en inglés).

Supongamos que A es un vector ordenado de m elementos y B es otro vector ordenado de elementos. La operación de mezcla producirá un nuevo vector de m + n elementos. El método más sencillo, pero menos eficaz, consiste en colocar una lista detrás de la otra y luego ordenarla.

Sin embargo este método no aprovecha la propiedad de que los vectores A y B ya están ordenados, por ello debe recurrir normalmente al sistema de mezcla el cual cosiste en comparar los dos primeros elementos de los vectores (A y B) y enviar al menor al tercer vector, continuando con el elemento comparado pero no enviado con el siguiente elemento del vector que contiene al elemento menor comparado anteriormente y así sucesivamente.

Una vez que se terminaron los elementos de un vector, se procede a vaciar los elementos restantes del otro vector.

Algoritmo

1.- Inicio
2.- Dividir la secuencia A en dos mitades denominadas B y C.
3.- Mezclar B y C combinando cada elemento en pares ordenados.
4.- Llamar A a la secuencia mezclada y repetir los pasos 1 y 2, esta vez combinando los pares en cuadriples ordenados.
5.- Repetir los pasos anteriores duplicando cada vez la longitud de las secuencias combinadas hasta que quede ordenada la secuencia original.
6.- Fin del Algoritmo.

Código

import java.io.*;
public class MezclaNaturalMain {
    public static void main(String [] args)throws Exception{
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String nombreArchivo = null;
        MezclaNatural mezcla1 = new MezclaNatural();
        //Solicita el nombre de un archivo para poder ordenarlo
        System.out.println("Nombre del archivo:");
        nombreArchivo = br.readLine();
        //Despliega el contenido del archivo sin ordenar
        mezcla1.desplegar(nombreArchivo);
        //Ordena el contenido del archivo
        mezcla1.ordenar(nombreArchivo);
        //Verifica que el archivo este ordenado correctamente
        mezcla1.verificarOrdenamiento(nombreArchivo);
    }
}

Ordenamiento por Intercalación Simple

Códigos del Métodos de Ordenamiento por Intercalación

Intercalación Simple:

Descripción

Este procedimiento supone la existencia de dos vectores A y B que contienen en N y M elementos respectivamente, los intercala introduce un tercer vector ordenado llamado C que contendrá N + M elementos. Para que funcione este algoritmo los vectores A y B deben estar previamente ordenados.

Algoritmo

1.- Inicio.

2.- Inicialización de variables auxiliares: I=1, J=1, K=1.

3.- Comparar los elementos correspondientes y determinar cual elemento entra al vector

while I<=N and J<=M

if A[I]<=B[J] then

C[K]=A[I]

I=I+1

K=K+1

else

C[K]=B[J]

J=J+1

K=K+1

4.- Copiar los elementos restantes que han quedado en algun vector:

if I>N then

for X=J,J+1,...M

C[K]=B[X]

K=K+1

else

for X=I,I+1,...N

C[K]=A[X]

K=K+1

5.- Fin del algoritmo

Código:

package insersion;
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
public class inser extends JFrame{
    int a[]=new int[10];
    int i, n, j;
    int max, mayor;
    String salida1="", salida2="";
    JTextArea areaSalida=new JTextArea(6,6);
    JTextArea areaSalida2=new JTextArea(6,6);
    JTextField numero=new JTextField(15);
    public inser(){
        super("Ordenamiento por Insercion");    
        JLabel etiqueta=new JLabel("Cuantos numeros quieres?");
        JLabel etiqueta1=new JLabel("Los numeros son:");
       JButton capturar=new JButton("Capturar");
        capturar.addActionListener(
                new ActionListener(){
                    public void actionPerformed(ActionEvent evento){
                        captura();
                    }
                }
        );    
        JButton ordenar=new JButton("Ordenar");
        ordenar.addActionListener(
                new ActionListener(){
                    public void actionPerformed(ActionEvent evento){
                        insertar(a,n);                    
                    }
                }
        );    
        Container contenedor=getContentPane();
        contenedor.setLayout(new FlowLayout());    
        contenedor.add(etiqueta);
        contenedor.add(numero);
        contenedor.add(capturar);
        contenedor.add(etiqueta1);
        contenedor.add(areaSalida);
        contenedor.add(ordenar);
        contenedor.add(areaSalida2);    
        setSize(300,300);
        setVisible(true); }

    public void captura(){    
       if (numero.getText().equals("")){
       JOptionPane.showMessageDialog(null,"Escriba un nombre");
       numero.setText("");
       }    
       else{
           a[i]=Integer.parseInt(numero.getText());
           salida2+=a[i]+"\n";
           i++;
           numero.setText("");
           if (i==5){
               n=i;
               JOptionPane.showMessageDialog(null,"Fin de la captura");            
           }
           areaSalida.setText(salida2);
       }
   }
    public void muestra(int nn,int a3[]){
        for(int k=0;k<nn;k++)
            salida1+=a3[k]+"\n";
        areaSalida2.setText(salida1);
    }
    public void insertar(int lista[], int n){
        int x,i,k;
        for(i=1;i<n;i++){
           x=lista[i];
           k=i-1;
           while(k>=0 && x<lista[k]){
               lista[k+1]=lista[k];
               lista[k]=x;
               k=k-1;          
               if (k==-1) break;          
           }
           lista[k+1]=x;
        }
        muestra(i,lista);
    }
    public static void main(String[] args) {
        inser aplicacion1 = new inser();
        aplicacion1.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);    
    }
}