implementación merge sort en C++

Question

He estudiado la teoría del tipo de fusión, pero no tengo idea de cómo implementarlo en C++. Mi pregunta es, merge sort crea matrices en recursión. Pero al implementarlo, ¿cómo creamos arreglos en tiempo de ejecución? o ¿cuál es el enfoque general para esto?

Gracias.

Answer 1

Basado en el código aquí: http://cplusplus.happycodings.com/algorithms/code17.html

// Merge Sort 

#include <iostream> 
using namespace std; 

int a[50]; 
void merge(int,int,int); 
void merge_sort(int low,int high) 
{ 
int mid; 
if(low<high) 
{ 
    mid = low + (high-low)/2; //This avoids overflow when low, high are too large 
    merge_sort(low,mid); 
    merge_sort(mid+1,high); 
    merge(low,mid,high); 
} 
} 
void merge(int low,int mid,int high) 
{ 
int h,i,j,b[50],k; 
h=low; 
i=low; 
j=mid+1; 

while((h<=mid)&&(j<=high)) 
{ 
    if(a[h]<=a[j]) 
    { 
    b[i]=a[h]; 
    h++; 
    } 
    else 
    { 
    b[i]=a[j]; 
    j++; 
    } 
    i++; 
} 
if(h>mid) 
{ 
    for(k=j;k<=high;k++) 
    { 
    b[i]=a[k]; 
    i++; 
    } 
} 
else 
{ 
    for(k=h;k<=mid;k++) 
    { 
    b[i]=a[k]; 
    i++; 
    } 
} 
for(k=low;k<=high;k++) a[k]=b[k]; 
} 
int main() 
{ 
int num,i; 

cout<<"******************************************************************* 
*************"<<endl; 
cout<<"        MERGE SORT PROGRAM 
"<<endl; 

cout<<"******************************************************************* 
*************"<<endl; 
cout<<endl<<endl; 
cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort [THEN 
PRESS 
ENTER]:"<<endl; 
cin>>num; 
cout<<endl; 
cout<<"Now, Please Enter the ("<< num <<") numbers (ELEMENTS) [THEN 
PRESS ENTER]:"<<endl; 
for(i=1;i<=num;i++) 
{ 
    cin>>a[i] ; 
} 
merge_sort(1,num); 
cout<<endl; 
cout<<"So, the sorted list (using MERGE SORT) will be :"<<endl; 
cout<<endl<<endl; 

for(i=1;i<=num;i++) 
cout<<a[i]<<" "; 

cout<<endl<<endl<<endl<<endl; 
return 1; 

} 

Answer 2

Para responder a la pregunta: Creación de matrices de tamaño dinámicamente en tiempo de ejecución se realiza mediante std::vector<T>. Idealmente, obtendrá su aporte usando uno de estos. Si no, es fácil convertirlos. Por ejemplo, podría crear dos matrices de la siguiente manera:

template <typename T> 
void merge_sort(std::vector<T>& array) { 
    if (1 < array.size()) { 
     std::vector<T> array1(array.begin(), array.begin() + array.size()/2); 
     merge_sort(array1); 
     std::vector<T> array2(array.begin() + array.size()/2, array.end()); 
     merge_sort(array2); 
     merge(array, array1, array2); 
    } 
} 

Sin embargo, la asignación de matrices dinámicas es relativamente lenta y por lo general debe evitarse siempre que sea posible. Para ordenar por fusión, puede ordenar las subsecuencias de la matriz original y fusionarlas in situ. Parece que std::inplace_merge() pide iteradores bidireccionales.

Answer 3

He reorganizado la respuesta seleccionada, los punteros utilizados para las matrices y la entrada del usuario para el recuento de números no está predefinido.

#include <iostream> 

using namespace std; 

void merge(int*, int*, int, int, int); 

void mergesort(int *a, int*b, int start, int end) { 
    int halfpoint; 
    if (start < end) { 
    halfpoint = (start + end)/2; 
    mergesort(a, b, start, halfpoint); 
    mergesort(a, b, halfpoint + 1, end); 
    merge(a, b, start, halfpoint, end); 
    } 
} 

void merge(int *a, int *b, int start, int halfpoint, int end) { 
    int h, i, j, k; 
    h = start; 
    i = start; 
    j = halfpoint + 1; 

    while ((h <= halfpoint) && (j <= end)) { 
    if (a[h] <= a[j]) { 
     b[i] = a[h]; 
     h++; 
    } else { 
     b[i] = a[j]; 
     j++; 
    } 
    i++; 
    } 
    if (h > halfpoint) { 
    for (k = j; k <= end; k++) { 
     b[i] = a[k]; 
     i++; 
    } 
    } else { 
    for (k = h; k <= halfpoint; k++) { 
     b[i] = a[k]; 
     i++; 
    } 
    } 

    // Write the final sorted array to our original one 
    for (k = start; k <= end; k++) { 
    a[k] = b[k]; 
    } 
} 

int main(int argc, char** argv) { 
    int num; 
    cout << "How many numbers do you want to sort: "; 
    cin >> num; 
    int a[num]; 
    int b[num]; 
    for (int i = 0; i < num; i++) { 
    cout << (i + 1) << ": "; 
    cin >> a[i]; 
    } 

    // Start merge sort 
    mergesort(a, b, 0, num - 1); 

    // Print the sorted array 
    cout << endl; 
    for (int i = 0; i < num; i++) { 
    cout << a[i] << " "; 
    } 
    cout << endl; 

    return 0; 
} 

Answer 4

Sé que esta pregunta ya ha sido respondida, pero decidí agregar mis dos centavos. Aquí hay un código para un tipo de fusión que solo usa espacio adicional en la operación de fusión (y ese espacio adicional es un espacio temporal que se destruirá cuando se salte la pila). De hecho, verá en este código que no hay uso de operaciones de pila (no se declara new en ninguna parte).

Espero que esto ayude.

void merge(int *arr, int size1, int size2) { 
     int temp[size1+size2]; 
     int ptr1=0, ptr2=0; 
     int *arr1 = arr, *arr2 = arr+size1; 

     while (ptr1+ptr2 < size1+size2) { 
      if (ptr1 < size1 && arr1[ptr1] <= arr2[ptr2] || ptr1 < size1 && ptr2 >= size2) 
       temp[ptr1+ptr2] = arr1[ptr1++]; 

      if (ptr2 < size2 && arr2[ptr2] < arr1[ptr1] || ptr2 < size2 && ptr1 >= size1) 
       temp[ptr1+ptr2] = arr2[ptr2++]; 
     } 

     for (int i=0; i < size1+size2; i++) 
      arr[i] = temp[i]; 
    } 

    void mergeSort(int *arr, int size) { 
     if (size == 1) 
      return; 

     int size1 = size/2, size2 = size-size1; 
     mergeSort(arr, size1); 
     mergeSort(arr+size1, size2); 
     merge(arr, size1, size2); 
    } 

    int main(int argc, char** argv) { 
     int num; 
     cout << "How many numbers do you want to sort: "; 
     cin >> num; 
     int a[num]; 
     for (int i = 0; i < num; i++) { 
      cout << (i + 1) << ": "; 
      cin >> a[i]; 
     } 

     // Start merge sort 
     mergeSort(a, num); 

     // Print the sorted array 
     cout << endl; 
     for (int i = 0; i < num; i++) { 
      cout << a[i] << " "; 
     } 
     cout << endl; 

     return 0; 
    } 

Answer 5

#include <iostream> 
using namespace std; 

template <class T> 
void merge_sort(T array[],int beg, int end){ 
    if (beg==end){ 
     return; 
    } 
    int mid = (beg+end)/2; 
    merge_sort(array,beg,mid); 
    merge_sort(array,mid+1,end); 
    int i=beg,j=mid+1; 
    int l=end-beg+1; 
    T *temp = new T [l]; 
    for (int k=0;k<l;k++){ 
     if (j>end || (i<=mid && array[i]<array[j])){ 
      temp[k]=array[i]; 
      i++; 
     } 
     else{ 
      temp[k]=array[j]; 
      j++; 
     } 
    } 
    for (int k=0,i=beg;k<l;k++,i++){ 
     array[i]=temp[k]; 
    } 
    delete temp; 
} 

int main() { 
    float array[] = {1000.5,1.2,3.4,2,9,4,3,2.3,0,-5}; 
    int l = sizeof(array)/sizeof(array[0]); 
    merge_sort(array,0,l-1); 
    cout << "Result:\n"; 
    for (int k=0;k<l;k++){ 
     cout << array[k] << endl; 
    } 
    return 0; 
} 

Answer 6

Aquí está una manera de ponerlo en práctica, utilizando sólo las matrices.

#include <iostream> 
using namespace std; 

//The merge function 
void merge(int a[], int startIndex, int endIndex) 
{ 

int size = (endIndex - startIndex) + 1; 
int *b = new int [size](); 

int i = startIndex; 
int mid = (startIndex + endIndex)/2; 
int k = 0; 
int j = mid + 1; 

while (k < size) 
{ 
    if((i<=mid) && (a[i] < a[j])) 
    { 
     b[k++] = a[i++]; 
    } 
    else 
    { 
     b[k++] = a[j++]; 
    } 

} 

for(k=0; k < size; k++) 
{ 
    a[startIndex+k] = b[k]; 
} 

delete []b; 

} 

//The recursive merge sort function 
void merge_sort(int iArray[], int startIndex, int endIndex) 
{ 
int midIndex; 

//Check for base case 
if (startIndex >= endIndex) 
{ 
    return; 
} 

//First, divide in half 
midIndex = (startIndex + endIndex)/2; 

//First recursive call 
merge_sort(iArray, startIndex, midIndex); 

//Second recursive call 
merge_sort(iArray, midIndex+1, endIndex); 

merge(iArray, startIndex, endIndex); 

} 



//The main function 
int main(int argc, char *argv[]) 
{ 
int iArray[10] = {2,5,6,4,7,2,8,3,9,10}; 

merge_sort(iArray, 0, 9); 

//Print the sorted array 
for(int i=0; i < 10; i++) 
{ 
    cout << iArray[i] << endl; 
} 

return 0;  
} 

Answer 7

He completado la forma de combinación de @ DietmarKühl. Espero que ayude a todos.

template <typename T> 
void merge(vector<T>& array, vector<T>& array1, vector<T>& array2) { 
    array.clear(); 

    int i, j, k; 
    for(i = 0, j = 0, k = 0; i < array1.size() && j < array2.size(); k++){ 
     if(array1.at(i) <= array2.at(j)){ 
      array.push_back(array1.at(i)); 
      i++; 
     }else if(array1.at(i) > array2.at(j)){ 
      array.push_back(array2.at(j)); 
      j++; 
     } 
     k++; 
    } 

    while(i < array1.size()){ 
     array.push_back(array1.at(i)); 
     i++; 
    } 

    while(j < array2.size()){ 
     array.push_back(array2.at(j)); 
     j++; 
    } 
} 

template <typename T> 
void merge_sort(std::vector<T>& array) { 
    if (1 < array.size()) { 
     std::vector<T> array1(array.begin(), array.begin() + array.size()/2); 
     merge_sort(array1); 
     std::vector<T> array2(array.begin() + array.size()/2, array.end()); 
     merge_sort(array2); 
     merge(array, array1, array2); 
    } 
} 

Answer 8

Esto sería fácil de entender:

#include <iostream> 

using namespace std; 

void Merge(int *a, int *L, int *R, int p, int q) 
{ 
    int i, j=0, k=0; 
    for(i=0; i<p+q; i++) 
    { 
     if(j==p)      //When array L is empty 
     { 
      *(a+i) = *(R+k); 
      k++; 
     } 
     else if(k==q)     //When array R is empty 
     { 
      *(a+i) = *(L+j); 
      j++; 
     } 
     else if(*(L+j) < *(R+k)) //When element in L is smaller than element in R 
     { 
      *(a+i) = *(L+j); 
      j++; 
     } 
     else //When element in R is smaller or equal to element in L 
     { 
      *(a+i) = *(R+k); 
      k++; 
     } 
    } 
} 

void MergeSort(int *a, int len) 
{ 
    int i, j; 
    if(len > 1) 
    { 
     int p = len/2 + len%2;  //length of first array 
     int q = len/2;    //length of second array 
     int L[p];     //first array 
     int R[q];     //second array 
     for(i=0; i<p; i++) 
     { 
      L[i] = *(a+i);  //inserting elements in first array 
     } 
     for(i=0; i<q; i++) 
     { 
      R[i] = *(a+p+i); //inserting elements in second array 
     } 
     MergeSort(&L[0], p); 
     MergeSort(&R[0], q); 
     Merge(a, &L[0], &R[0], p, q); //Merge arrays L and R into A 
    } 
    else 
    { 
     return;  //if array only have one element just return 
    } 
} 

int main() 
{ 
    int i, n; 
    int a[100000]; 
    cout<<"Enter numbers to sort. When you are done, enter -1\n"; 
    i=0; 
    while(true) 
    { 
     cin>>n; 
     if(n==-1) 
     { 
      break; 
     } 
     else 
     { 
      a[i] = n; 
      i++; 
     } 
    } 
    int len = i; 
    MergeSort(&a[0], len); 
    for(i=0; i<len; i++) 
    { 
     cout<<a[i]<<" "; 
    } 

    return 0; 
} 

Answer 9

El problema con la combinación de una especie es la combinación, si es que en realidad no necesita implementar la fusión, entonces es bastante simple (para una vector de ints):

#include <algorithm> 
#include <vector> 
using namespace std; 

typedef vector<int>::iterator iter; 

void mergesort(iter b, iter e) { 
    if (e -b > 1) { 
     iter m = b + (e -b)/2; 
     mergesort(b, m); 
     mergesort(m, e); 
     inplace_merge(b, m, e); 
    } 
}