Scribd
Cargar
6 vistas2 páginas

4 Ejecicio

Este documento presenta una implementación del algoritmo de ordenación Merge Sort en C++. Incluye funciones para fusionar subarreglos ordenados y para mostrar el arreglo antes y después de la ordenación. El programa principal inicializa un arreglo desordenado, lo ordena y muestra los resultados.

Cargado por

Joa Vargas Cuevas
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como TXT, PDF, TXT o lee en línea desde Scribd
6 vistas2 páginas

4 Ejecicio

Este documento presenta una implementación del algoritmo de ordenación Merge Sort en C++. Incluye funciones para fusionar subarreglos ordenados y para mostrar el arreglo antes y después de la ordenación. El programa principal inicializa un arreglo desordenado, lo ordena y muestra los resultados.

Cargado por

Joa Vargas Cuevas
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como TXT, PDF, TXT o lee en línea desde Scribd

#include <iostream>

using namespace std;

// Función que fusiona dos subarreglos ordenados


void fusion(int arreglo[], int inicio, int medio, int fin) {
int n1 = medio - inicio + 1;
int n2 = fin - medio;

// Arreglos temporales
int izquierda[n1], derecha[n2];

// Copiar los datos a los arreglos temporales


for (int i = 0; i < n1; i++)
izquierda[i] = arreglo[inicio + i];
for (int j = 0; j < n2; j++)
derecha[j] = arreglo[medio + 1 + j];

// Índices iniciales
int i = 0; // índice de la sublista izquierda
int j = 0; // índice de la sublista derecha
int k = inicio; // índice del arreglo principal

// Mezclar los arreglos


while (i < n1 && j < n2) {
if (izquierda[i] <= derecha[j]) {
arreglo[k] = izquierda[i];
i++;
} else {
arreglo[k] = derecha[j];
j++;
}
k++;
}

// Copiar los elementos restantes de izquierda[], si los hay


while (i < n1) {
arreglo[k] = izquierda[i];
i++;
k++;
}

// Copiar los elementos restantes de derecha[], si los hay


while (j < n2) {
arreglo[k] = derecha[j];
j++;
k++;
}
}

// Función principal de ordenación (divide y fusiona)


void mergeSort(int arreglo[], int inicio, int fin) {
if (inicio < fin) {
int medio = inicio + (fin - inicio) / 2; // evitar desbordamiento

// Ordenar la primera y segunda mitad


mergeSort(arreglo, inicio, medio);
mergeSort(arreglo, medio + 1, fin);
// Fusionar las dos mitades ordenadas
fusion(arreglo, inicio, medio, fin);
}
}

// Función para imprimir el arreglo


void mostrarArreglo(int arreglo[], int tam) {
for (int i = 0; i < tam; i++)
cout << arreglo[i] << " ";
cout << endl;
}

// Programa principal
int main() {
int arreglo[] = {8, 3, 5, 2, 9, 1};
int tam = sizeof(arreglo) / sizeof(arreglo[0]);

cout << "Arreglo original: ";


mostrarArreglo(arreglo, tam);

mergeSort(arreglo, 0, tam - 1);

cout << "Arreglo ordenado: ";


mostrarArreglo(arreglo, tam);

return 0;
}

También podría gustarte