Algoritmo de mezcla natural
En cuanto a los ficheros secuenciales, el método más usado es el de mezlca natural. Es válido para ficheros de tamaño de registro variable.
Es un buen método para ordenar barajas de naipes, por ejemplo.
Cada pasada se compone de dos fases. En la primera se separa el fichero original en dos auxiliares, los elementos se direigen a uno u otro fichero separando los tramos de registros que ya estén ordenados. En la segunda fase los dos ficheros auxiliares se mezclan de nuevo de modo que de cada dos tramos se obtiene siempre uno ordenado. El proceso se repite hasta que sólo obtenemos un tramo.
Por ejemplo, supongamos los isguientes valores en un fichero de acceso secuencial, que ordenaremos de menor a mayor:
3, 1, 2 , 4 , 6, 9, 5, 8, 10, 7
Separaremos todos los tramos ordenados de este fichero:
[3], [1, 2, 4, 6, 9], [5, 8, 10], [7]
La primera pasada separará los tramos alternándolos en dos ficheros auxiliares:
aux1: [3], [5, 8. 10]
aux2: [1, 2, 4, 6, 9]
Y de mezclándolos de nuevo:
mezcla: 1, 2, 3, 4, 6, 7, 8, 9, 10
El fichero ya está ordenado, para verificarlo contaremos los tramos obtenidos después de cada proceso de mezcla, el fichero estará desordenado si nos encontramos más de un tramo.
IMPLEMENTACION EN JAVA
package metodosOrdenamiento;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.*;
public class Mezcla extends JPanel implements ActionListener{
private static final long serialVersionUID = 8865647787011721299L;
int n;
int v[];
JTextArea sal;
JPanel bot;
JButton introducir,mostrar;
public Mezcla(){
setLayout(new BorderLayout());
n=6;
v=new int[n];
interfaz();
}
public void interfaz(){
sal=new JTextArea(15,35);
sal.setBorder(BorderFactory.createTitledBorder(" ordenamiento Mezcla natural "));
sal.setEditable(false);
bot=new JPanel();
bot.setLayout(new GridLayout(2,0));
introducir=new JButton("Introducir");
introducir.setBackground(Color.BLACK);
introducir.setForeground(Color.WHITE);
introducir.addActionListener(this);
mostrar=new JButton("Mostrar");
mostrar.setBackground(Color.BLACK);
mostrar.setForeground(Color.WHITE);
mostrar.addActionListener(this);
bot.add(introducir);
bot.add(mostrar);
add(sal,BorderLayout.CENTER);
add(bot,BorderLayout.EAST);
}
public void vector(){
for(int i=0;i<v.length;i++){
try{
v[i]=Integer.parseInt
(JOptionPane.showInputDialog(null,"introduce un numero","metodo mezcla natural"
,JOptionPane.INFORMATION_MESSAGE));
}catch(Exception e){
JOptionPane.showMessageDialog(null,"introduce un valor numerico"
,"Error",JOptionPane.ERROR_MESSAGE);
}
}
}//fin vector
private static void merge(int[] fuente1, int[] fuente2, int[] dest){
// indices de los 3 array
int srcIndex1 = 0;
int srcIndex2 = 0;
int destIndex = 0;
// merge hasta que uno de los arrays fuentes este vacio
while (srcIndex1 < fuente1.length && srcIndex2 < fuente2.length){
if (fuente1[srcIndex1] < fuente2[srcIndex2]){
dest[destIndex] = fuente1[srcIndex1]; srcIndex1++;
}
else {
dest[destIndex] = fuente2[srcIndex2];
srcIndex2++;
}
destIndex++;
}
if (srcIndex1 < fuente1.length)
System.arraycopy(fuente1, srcIndex1, dest, destIndex,
fuente1.length - srcIndex1);
else
System.arraycopy(fuente2, srcIndex2, dest, destIndex,
fuente2.length - srcIndex2);
} // fin de merge();
// Ordena usando mezcla natural
// Parametros: el array a ordenar
public static void sort(int arr[]){
if (arr.length <= 1) return;
int tam1 = arr.length / 2;
int tam2 = arr.length - tam1;
int primeraMitad[] = new int[tam1];
int segundaMitad[] = new int[tam2];
System.arraycopy(arr, 0, primeraMitad, 0, tam1);
System.arraycopy(arr, tam1, segundaMitad, 0, tam2);
sort(primeraMitad);
sort(segundaMitad);
Mezcla.merge(primeraMitad, segundaMitad, arr);
}
public static void main(String [] arg){
int n = 6;
int [] v = {465,12,89,47,-3,18} ;
System.out.println("Vector antes de ordenar:");
for (int i=0; i < n; i++) {
System.out.println("v["+i+"] = "+v[i]); }
Mezcla.sort(v);
System.out.println("\nVector despues de ordenar:");
for (int i=0; i < n; i++) { System.out.println("v["+i+"] = "+v[i]); }
System.out.println("Ya he terminado.");
}//fin main
public void actionPerformed(ActionEvent ev) {
if(ev.getSource()==introducir){
sal.setText( " " );
vector();
System.out.println("fase 1");
}
if(ev.getSource()==mostrar){
sal.append("antes de ordenar:" + "\n");
for (int i=0;i < v.length;i++){
sal.append(" " + v[i] + " " + " " );
}
sal.append("\n"+"\n");
sal.append("despues de ordenar:"+"\n");
sort(v);
for (int i=0;i < v.length;i++){
System.out.print(v[i]+" ");
sal.append(" " + v[i] + " " + " " );
}
}
}//fin actionPerformed
}// fin clase