Instalacion y Configuración
Metodología de Programación

Algoritmo MergeSort en C++

En este ejercicio, implementará el algoritmo MergeSort en C++. MergeSort es un algoritmo de ordenamiento altamente eficiente, basado en el principio de "dividir y vencer", que funciona dividiendo el array de entrada en dos mitades, ordenando cada mitad recursivamente y luego fusionándolas. Su complejidad temporal es de O(n log n), lo que lo convierte en una excelente opción para ordenar grandes conjuntos de datos. El algoritmo es estable, lo que significa que conserva el orden relativo de los registros con claves iguales. Implementar MergeSort le ayudará a comprender el concepto de recursión y la importancia de los algoritmos de ordenamiento eficientes.

Grupo

Algoritmos de Búsqueda y Ordenación en C++

Ojetivo

Escriba un programa en C++ que implemente el algoritmo MergeSort. El programa debe ordenar un array de enteros en orden ascendente mediante la técnica de divide y vencerás. Implemente la función de fusión para combinar dos arrays ordenados en uno solo.

Implemente el algoritmo MergeSort.

Ejemplo de Código C++

 Copiar Código C++ 
#include <iostream>  // Include the input-output stream library
#include <vector>     // Include the vector library to use dynamic arrays
using namespace std;

// Function to merge two sorted subarrays into a single sorted array
void merge(vector<int> &arr, int left, int mid, int right) {
    int n1 = mid - left + 1;  // Size of the first subarray
    int n2 = right - mid;     // Size of the second subarray

    // Create temporary arrays to hold the data
    vector<int> L(n1), R(n2);

    // Copy data to temporary arrays L[] and R[]
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    int i = 0;  // Initial index of the first subarray
    int j = 0;  // Initial index of the second subarray
    int k = left;  // Initial index of the merged subarray

    // Merge the temporary arrays back into arr[left..right]
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy any remaining elements of L[], if any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy any remaining elements of R[], if any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Function to implement MergeSort recursively
void mergeSort(vector<int> &arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;  // Find the midpoint

        // Recursively sort the first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}

int main() {
    // Define an array to be sorted
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};

    // Get the number of elements in the array
    int size = arr.size();

    // Call mergeSort to sort the array
    mergeSort(arr, 0, size - 1);

    // Display the sorted array
    cout << "Sorted array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

 Salida

Sorted array: 3 9 10 27 38 43 82

Comparte este ejercicio C++

Más ejercicios de programación C++Algoritmos de Búsqueda y Ordenación en C++

¡Explora el conjunto de ejercicios de programación en C++! Diseñados específicamente para principiantes, estos ejercicios te ayudarán a desarrollar una sólida comprensión de los fundamentos de C++. Desde variables y tipos de datos hasta estructuras de control y funciones simples, cada ejercicio está diseñado para desafiarte gradualmente a medida que adquieres confianza en la programación en C++.