Ordenamiento con mergesort
El método Merge Sort consiste en partir una estructura en mitades, ordenar cada mitad y luego intercalar ordenadamente ambas mitades. Cada mitad se ordena aplicando el mismo método.
https://www.youtube.com/watch?v=ACFZn_xQcz8
public class MergeSort {
public static void main(String args[]){
int vec[]={45,17,23,67,21};
System.out.println("Vector original");
imprimirVector(vec);
System.out.println("\\nVector ordenado");
ordenacionMergeSort(vec);
imprimirVector(vec);
}
public static void ordenacionMergeSort(int vec[]){
if(vec.length<=1) return;
int mitad= vec.length/2;
int izq[]=Arrays.copyOfRange(vec, 0, mitad);
int der[]=Arrays.copyOfRange(vec, mitad, vec.length);
ordenacionMergeSort(izq);
ordenacionMergeSort(der);
combinarVector(vec, izq, der);
}
public static void combinarVector(int v[], int izq[],int der[]){
int i=0;
int j=0;
for(int k=0;k<v.length;k++){
if(i>=izq.length){
v[k]=der[j];
j++;
continue;
}
if(j>=der.length){
v[k]=izq[i];
i++;
continue;
}
if(izq[i]<der[j]){
v[k]=izq[i];
i++;
}else{
v[k]=der[j];
j++;
}
}
}
public static void imprimirVector(int vec[]){
for(int i=0;i<vec.length;i++){
System.out.print(vec[i]+" ");
}
}
}
/*
* Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
* Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Main.java to edit this template
*/
package ordenamiento;
/**
*
* @author LAB-USR-CHIM-A0202
*/
public class Nuevoorden {
public static void main(String[] args) {
Nuevoorden mergeSort = new Nuevoorden();
int arr[] = {5, 26, 12, 6, 1, 4, 7};
int n = arr.length;
System.out.println("Array original:");
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i] + " ");
}
System.out.println();
System.out.println("Array ordenado:");
mergeSort.sort(arr, 0, n - 1);
mergeSort.printArray(arr);
}
public void sort(int arr[], int left, int right) {
if (left < right) {
//Encuentra el punto medio del vector.
int middle = (left + right) / 2;
//Divide la primera y segunda mitad (llamada recursiva).
sort(arr, left, middle);
sort(arr, middle + 1, right);
//Une las mitades.
unir(arr, left, middle, right);
}
}
public void unir(int arr[], int left, int middle, int right) {
//Encuentra el tamaño de los sub-vectores para unirlos.
int n1 = middle - left + 1;
int n2 = right - middle;
//Vectores temporales.
int leftArray[] = new int[n1];
int rightArray[] = new int[n2];
//Copia los datos a los arrays temporales.
for (int i = 0; i < n1; i++) {
leftArray[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
rightArray[j] = arr[middle + j + 1];
}
/* Une los vectorestemporales. */
//Ãndices inicial del primer y segundo sub-vector.
int i = 0, j = 0;
//Ãndice inicial del sub-vector arr[].
int k = left;
//Ordenamiento.
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
}//Fin del while.
/* Si quedan elementos por ordenar */
//Copiar los elementos restantes de leftArray[].
while (i < n1) {
arr[k] = leftArray[i];
i++;
k++;
}
//Copiar los elementos restantes de rightArray[].
while (j < n2) {
arr[k] = rightArray[j];
j++;
k++;
}
}
public void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i) {
System.out.println(arr[i] + " ");
}
System.out.println();
}
}
Metodo mergesort explicado:
Para encontrar un dato dentro de un arreglo, para ello existen diversos algoritmos que varían en complejidad, eficiencia, tamaño del dominio de busqueda.
Los algoritmos dde busqueda tiene dos tipos de busqueda;
/*
* Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
* Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Main.java to edit this template
*/
package busqueda.secuencial;
/**
*
* @author LAB-USR-CHIM-A0202
*/
public class BusquedaSecuencial {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int vector[] = {45, 17, 23, 67, 21, 55, 8, 18, 21, 26, 58};
System.out.println("Vector original");
for (int i = 0; i < vector.length; i++) {
System.out.print(vector[i] + " ");
}
int dato = 21;
int posicion = 0;
for (int i = 0; i < vector.length; i++) {//recorremos todo el arreglo
if (vector[i] == dato) {//comparamos el elemento en el arreglo con el buscado
posicion = i;//Si es verdadero guardamos la posicion
System.out.println(" ");
System.out.println("Valor ubicado -->" + posicion);
System.out.println("");
break;//Para el ciclo
}
if (posicion!=1) {
System.out.println("No existe valor");
}
}
}
}