implementazione di merge sort in C++

Question

Ho studiato la teoria dell'ordinamento di unione ma non ho idea di come implementarlo in C++. La mia domanda è, unire ordina crea array in ricorsione. Ma quando si implementa, come possiamo creare array in runtime? o qual è l'approccio generale per questo?

Grazie.

Answer 1

In base al codice qui: 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

di rispondere alla domanda: Creazione di array di dimensioni dinamicamente a run-time viene fatto utilizzando std::vector<T>. Idealmente, otterresti il ​​tuo input usando uno di questi. In caso contrario, è facile convertirli. Ad esempio, è possibile creare due array come questo:

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); 
    } 
} 

Tuttavia, l'assegnazione array dinamici è relativamente lento e, in generale dovrebbe essere evitato quando possibile. Per l'unisci sort puoi semplicemente ordinare le sottosequenze dell'array originale e unarle sul posto. Sembra, std::inplace_merge() chiede iteratori bidirezionali.

Answer 3

Ho riarrangiato la risposta selezionata, i puntatori usati per gli array e l'input dell'utente per il conteggio dei numeri non sono predefiniti.

#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

So che questa domanda ha già avuto risposta, ma ho deciso di aggiungere i miei due centesimi. Ecco il codice per un ordinamento di tipo merge che utilizza solo uno spazio aggiuntivo nell'operazione di unione (e che lo spazio aggiuntivo è lo spazio temporaneo che verrà distrutto quando viene eseguito il popping dello stack). Infatti, in questo codice vedrai che non esiste l'uso delle operazioni heap (nessuna dichiarazione new ovunque).

Spero che questo aiuti.

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

Ecco un modo per implementare, utilizzando solo gli array.

#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

Ho completato il metodo di unione di DietmarKühl. Spero che aiuti tutti

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

Questo sarebbe facile da capire:

#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

Il problema di merge sort è l'unione, se in realtà non è necessario implementare l'unione, allora è abbastanza semplice (per un vector of 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); 
    } 
}