la mise en œuvre de fusion de tri en C++

Basé sur le code ici: 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;
}

OriginalL'auteur klm123

J'ai terminé @DietmarKühl s mode de fusion de tri. Espérons que cela aide tous.

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

OriginalL'auteur Sazzad Hissain Khan

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

OriginalL'auteur João Abrantes

Voici une manière de le mettre en œuvre, en utilisant seulement des tableaux.

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

OriginalL'auteur KKP

Ce serait facile à comprendre:

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

OriginalL'auteur theCaveman