合并排序算法中的引用数组产生原始数组中不存在的值
reference array in mergesort algorithm produces values that were not existent in the original array
我的合并排序算法工作正常，即它对输入数组中的值进行排序。但是，用于控制数组是否真正排序的引用数组产生的值不在应排序的原始数组中，因此编译器会抛出错误。我该怎么做才能解决这个问题？
我已经配置了程序，以便它对一个特定的数组进行排序，它有 103 个值，我尝试减小大小但程序成功运行。
这是输入数组：
[1919243808,365,372,383,394,404,413,170931,667182,540028976,741551154,774455913,774778478,778265971,840969273,892416309,942815278,1292503603,1667851881,1869182049,1919243808,35,20,20,50,50,52,53,54,54,55,55,58,63,64,64,65,388,401,65,71,73,73,74,75,75,77,289,290,290,292,300,303,308,308,308,267,312,312,314,314,315,323,323,325,330,332,333,338,339,347,347,361,221,372,383,394,404,331,331,413,2,741551154,892416309,875310137,808531502,540028976,778265971,1919243808,1667851881,1869182049,774778478,1292503603,774455913,667182,356,359,361,362,363,364,365,741684787]
保存在程序开头的引用数组中。为了控制此时是否发生变化，我打印了参考数组，它仍然与输入数组相同。
然后合并排序算法在输入数组上运行。
它给出了输出数组：
[2,20,20,35,50,50,52,53,54,54,55,55,58,63,64,64,65,65,71,73,73,74,75,75,77,221,267,289,290,290,292,300,303,308,308,308,312,312,314,314,315,323,323,325,330,331,331,332,333,338,339,347,347,356,359,361,361,362,363,364,365,365,372,372,383,383,388,394,394,401,404,404,413,413,170931,667182,667182,540028976,540028976,741551154,741551154,741684787,774455913,774455913,774778478,774778478,778265971,778265971,808531502,840969273,875310137,892416309,892416309,942815278,1292503603,1292503603,1667851881,1667851881,1869182049,1869182049,1919243808,1919243808,1919243808]
我用一个帮助程序检查了输出数组是否排序，它真的排序了。
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/time.h>
#include <iostream>
int arraySortedCheck(int arr[], int n){
for (int i = 0; i < n; ++i){
//when an array is not in sorted order
if(arr[n-1] < arr[n-2])
return 0;
}
//all elements are checked and
//all are in sorted order
return 1;
}
int main(int argc, char const *argv[]){
int arr[103]{2,20,20,35,50,50,52,53,54,54,55,55,58,63,64,64,65,65,71,73,73,74,75,75,77,221,267,289,290,290,292,300,303,308,308,308,312,312,314,314,315,323,323,325,330,331,331,332,333,338,339,347,347,356,359,361,361,362,363,364,365,365,372,372,383,383,388,394,394,401,404,404,413,413,170931,667182,667182,540028976,540028976,741551154,741551154,741684787,774455913,774455913,774778478,774778478,778265971,778265971,808531502,840969273,875310137,892416309,892416309,942815278,1292503603,1292503603,1667851881,1667851881,1869182049,1869182049,1919243808,1919243808,1919243808};
int n = sizeof(arr)/sizeof(arr[0]);
if(arraySortedCheck(arr, n)){
printf("Array is in sorted order\n");
}
else
printf("Array is not in sorted order\n");
return 0;
}
排序检查输出：
Array is in sorted order
在我的程序的验证阶段，参考数组使用库函数进行排序，然后与归并排序算法的输出数组进行比较，但是这个排序后的参考数组具有之前不存在的值
“排序参考数组”
[2,20,20,35,50,50,52,53,54,54,55,55,58,63,64,64,65,65,71,73,73,74,75,75,77,221,267,289,290,290,292,300,303,308,308,308,312,312,314,314,315,323,323,325,330,331,331,332,333,338,339,347,347,356,359,361,361,362,363,364,365,365,372,372,383,383,388,394,394,401,404,404,413,413,170931,667182,667182,540028976,540028976,741551154,741551154,774455913,774455913,774778478,774778478,778265971,778265971,808531502,840969273,875310137,892416309,892416309,942815278,959515229,1292503603,1292503603,1667851881,1667851881,1869182049,1869182049,1919243808,1919243808,959527217]
新值例如 959527217 或 959515229
因此验证表明数组不是排序的输入数组，即使它是
这是代码：
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/time.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <omp.h>
// Constants.h
#if !defined(MYLIB_CONSTANTS_H)
#define MYLIB_CONSTANTS_H 1
#endif
//Takes a sorted list of size n and a value, puts the value in one of n+1 possible positions,
//if value is same to an element of the list take the position before the first occurence of the same element
binarysearchfindlowerrank(int *in,int n,int value,int projection){
int* array= in+projection;
int L=0;
int R=n;
printf("\nLowerBinarysearchrankfinder: [");
for(int i=0;i<n; i++){
printf("%d,",array[i]);
}
printf("]\n");
while(R-L>1){
int middle = (R+L)/2;
printf("L:%d,middle:%d,R:%d,value:%d\n",L,middle,R,value);
if(array[middle]==value){
while(array[middle]==value&&middle>0){
middle=middle-1;
}
if(middle==0&&array[middle]>=value){
return 0;
}
else{
printf("L:%d,middle:%d,R:%d,result:%d,index:%d\n",L,middle,R,(middle+1),(middle+1+projection));
return middle+1;
}
}
if(array[middle]<value){
L=middle;
}
if(array[middle]>value){
R=middle;
}
}
printf("L:%d,R:%d,value:%d\n",L,R,value);
if(n==1){
if(array[0]>=value){
return 0;
}
else return 1;
}
if(L==0&&array[L]>value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,0,0+projection);
return 0;
}
if(R==n && array[R-1]< value){
printf("!!L:%d,R:%d,result:%d,index:%d\n",L,R,n,n+projection);
return n;
}
if(R==n&& array[R-1]>=value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,R-1,(R-1+projection));
return R-1;
}
if(array[R]<value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,R+1,(R+1+projection));
return R+1;
}
if(array[L]<value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,R,(R+projection));
return R;
}
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,L,(L+projection));
return L;
}
//Takes a sorted list of size n and a value, puts the value in one of n+1 possible positions,
//if value is same to an element of the list take the position after the last occurence of the same element
binarysearchfinduperrank(int *in,int n,int value, int projection){
int* array= in+projection;
int L=0;
int R=n;
printf("\nUpperBinarysearchrankfinder [");
for(int i=0;i<n; i++){
printf("%d,",array[i]);
}
printf("]\n");
while(R-L>1){
int middle = (R+L)/2;
printf("L:%d,middle:%d,R:%d,value:%d\n",L,middle,R,value);
if(array[middle]==value){
while(array[middle]==value&&middle<n){
middle=middle+1;
}
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,middle,middle+projection);
return middle;
}
if(array[middle]<value){
L=middle;
}
if(array[middle]>value){
R=middle;
}
}
printf("L:%d,R:%d,value:%d\n",L,R,value);
if(n==1){
if(array[0]> value){
printf(" result:0\n,index:%d\n",0+projection);
return 0;
}
else{
printf(" result:1,index:%d\n",1+projection);
return 1;
}
}
if(L==0&&array[L]>value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,0,projection);
return 0;
}
if(R==n && array[R-1]<= value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,n,n+projection);
return n;
}
if(R==n&& array[R-1]>value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,R-1,((R-1)+projection));
return R-1;
}
if(array[R]<=value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,R+1,(R+1+projection));
return R+1;
}
if(array[L]<=value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,R,R+projection);
return R;
}
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,L,L+projection);
return L;
}
/**
* helper routine: check if array is sorted correctly
*/
bool isSorted(int ref[], int data[], const size_t size){
std::sort(ref, ref + size);
for (size_t idx = 0; idx < size; ++idx){
if (ref[idx] != data[idx]) {
printf("\nFalscher Index:%d\n",idx);
return false;
}
}
return true;
}
/**
* sequential merge step (straight-forward implementation)
*/
void MsMergeSequential(int *out, int *in, long begin1, long end1, long begin2, long end2, long outBegin,int *data,int *tmp) {
if(begin1==end2){
out[begin1]=in[begin1];
printf("\n[%d]\n",out[begin1]);
}
if(begin1==begin2||begin2==end2){
out[begin1+binarysearchfinduperrank(in,1,in[end2],begin1)]=in[end2];
out[begin1+binarysearchfindlowerrank(in,1,in[begin1],end2)]=in[begin1];
printf("\n[%d,%d]\n",out[begin1],out[end2]);
printf("\nDATA:n[");
for (size_t idx = 0; idx < 103; ++idx){
printf("%d,",data[idx]);
}
printf("]\n");
printf("\nTMP:[");
for (size_t idx = 0; idx < 103; ++idx){
printf("%d,",tmp[idx]);
}
printf("]\n");
}
else{
printf("begin:%d,middle1:%d:,middle2:%d,end:%d\n",begin1,end1,begin2,end2);
for(int i=0;i<(end2-begin2);i++){
out[begin1+i+binarysearchfinduperrank(in,(end1-begin1),in[begin2+i],begin1)]=in[begin2+i];
}
for(int i=0;i<(end1-begin1);i++){
out[begin1+i+binarysearchfindlowerrank(in,(end2-begin2),in[begin1+i],begin2)]=in[begin1+i];
}
printf("\n[");
for(int i=0;i<(end2-begin1);i++){
printf("%d,",out[i+begin1]);
}
printf("]\n");
printf("\nDATA:[");
for (size_t idx = 0; idx < 11; ++idx){
printf("%d,",data[idx]);
}
printf("]\n");
printf("\nTMP:[");
for (size_t idx = 0; idx < 11; ++idx){
printf("%d,",tmp[idx]);
}
printf("]\n");
}
}
bool myfunc (long i , long j){return (i<j);}
/**
* sequential MergeSort
*/
void MsSequential(int *array, int *tmp, bool inplace, long begin, long end) {
if (begin < (end - 1)) {
long half =(begin+end) / 2;
MsSequential(array, tmp, !inplace, begin, half);
MsSequential(array, tmp, !inplace, half, end);
if (inplace){
MsMergeSequential(array, tmp, begin, half, half, end, begin,array,tmp);
}
else {
MsMergeSequential(tmp, array, begin, half, half, end, begin,array,tmp);
}
}
else if (!inplace) {
tmp[begin] = array[begin];
printf("\n[%d]\n",tmp[begin]);
printf("\nDATA:[");
for (size_t idx = 0; idx < 11; ++idx){
printf("%d,",array[idx]);
}
printf("]\n");
printf("\nTMP:[");
for (size_t idx = 0; idx < 11; ++idx){
printf("%d,",tmp[idx]);
}
printf("]\n");
}
}
/**
* Serial MergeSort
*/
void MsSerial(int *array, int *tmp, const size_t size) {
MsSequential(array, tmp, true, 0, size);
}
/**
/**
* @brief program entry point
*/
int main(int argc, char* argv[]) {
// variables to measure the elapsed time
struct timeval t1, t2;
double etime;
// expect one command line arguments: array size
if (argc != 2) {
printf("Usage: MergeSort.exe <array size> \n");
printf("\n");
return EXIT_FAILURE;
}
else {
size_t stSize = strtol(argv[1], NULL, 10);
int *data2 = (int*) malloc(stSize * sizeof(int));
int *tmp = (int*) malloc(stSize * sizeof(int));
int *ref = (int*) malloc(stSize * sizeof(int));
printf("Initialization...\n");
srand(95);
for (size_t idx = 0; idx < stSize; ++idx){
data2[idx] = (int) (stSize * (double(rand()) / RAND_MAX));
}
stSize=103;
int data[103]{1919243808,365,372,383,394,404,413,170931,667182,540028976,741551154,774455913,774778478,778265971,840969273,892416309,942815278,1292503603,1667851881,1869182049,1919243808,35,20,20,50,50,52,53,54,54,55,55,58,63,64,64,65,388,401,65,71,73,73,74,75,75,77,289,290,290,292,300,303,308,308,308,267,312,312,314,314,315,323,323,325,330,332,333,338,339,347,347,361,221,372,383,394,404,331,331,413,2,741551154,892416309,875310137,808531502,540028976,778265971,1919243808,1667851881,1869182049,774778478,1292503603,774455913,667182,356,359,361,362,363,364,365,741684787};
std::copy(data, data + stSize, ref);
printf("START");
printf("\n[");
for (size_t idx = 0; idx < stSize; ++idx){
printf("%d,",ref[idx]);
}
printf("]\n");
printf("]");
double dSize = (stSize * sizeof(int)) / 1024 / 1024;
printf("Sorting %zu elements of type int (%f MiB)...\n", stSize, dSize);
gettimeofday(&t1, NULL);
MsSerial(data, tmp, stSize);
gettimeofday(&t2, NULL);
etime = (t2.tv_sec - t1.tv_sec) * 1000 + (t2.tv_usec - t1.tv_usec) / 1000;
etime = etime / 1000;
printf("done, took %f sec. Verification...", etime);
printf("\n[");
for (size_t idx = 0; idx < stSize; ++idx){
printf("%d,",ref[idx]);
}
printf("]\n");
printf("\n[");
for (size_t idx = 0; idx < stSize; ++idx){
printf("%d,",data[idx]);
}
printf("]\n");
if (isSorted(ref, data, stSize)) {
printf(" successful.\n");
}
else {
printf(" FAILED.\n");
}
printf("\n[");
for (size_t idx = 0; idx < stSize; ++idx){
printf("%d,",ref[idx]);
}
printf("]\n");
free(data2);
//delete[] data;
free(tmp);
//delete[] tmp;
free(ref);
//delete[] ref;
}
return EXIT_SUCCESS;
}
数组 ref 具有数组 data2 的大小，因此数组 ref 中的值多于数组 data 中的值，因此在对数组 ref 进行排序时，它还会查看与输入数组不同的其他值
我的合并排序算法工作正常，即它对输入数组中的值进行排序。但是，用于控制数组是否真正排序的引用数组产生的值不在应排序的原始数组中，因此编译器会抛出错误。我该怎么做才能解决这个问题？
我已经配置了程序，以便它对一个特定的数组进行排序，它有 103 个值，我尝试减小大小但程序成功运行。
这是输入数组：
[1919243808,365,372,383,394,404,413,170931,667182,540028976,741551154,774455913,774778478,778265971,840969273,892416309,942815278,1292503603,1667851881,1869182049,1919243808,35,20,20,50,50,52,53,54,54,55,55,58,63,64,64,65,388,401,65,71,73,73,74,75,75,77,289,290,290,292,300,303,308,308,308,267,312,312,314,314,315,323,323,325,330,332,333,338,339,347,347,361,221,372,383,394,404,331,331,413,2,741551154,892416309,875310137,808531502,540028976,778265971,1919243808,1667851881,1869182049,774778478,1292503603,774455913,667182,356,359,361,362,363,364,365,741684787]
保存在程序开头的引用数组中。为了控制此时是否发生变化，我打印了参考数组，它仍然与输入数组相同。
然后合并排序算法在输入数组上运行。
它给出了输出数组：
[2,20,20,35,50,50,52,53,54,54,55,55,58,63,64,64,65,65,71,73,73,74,75,75,77,221,267,289,290,290,292,300,303,308,308,308,312,312,314,314,315,323,323,325,330,331,331,332,333,338,339,347,347,356,359,361,361,362,363,364,365,365,372,372,383,383,388,394,394,401,404,404,413,413,170931,667182,667182,540028976,540028976,741551154,741551154,741684787,774455913,774455913,774778478,774778478,778265971,778265971,808531502,840969273,875310137,892416309,892416309,942815278,1292503603,1292503603,1667851881,1667851881,1869182049,1869182049,1919243808,1919243808,1919243808]
我用一个帮助程序检查了输出数组是否排序，它真的排序了。
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/time.h>
#include <iostream>
int arraySortedCheck(int arr[], int n){
for (int i = 0; i < n; ++i){
//when an array is not in sorted order
if(arr[n-1] < arr[n-2])
return 0;
}
//all elements are checked and
//all are in sorted order
return 1;
}
int main(int argc, char const *argv[]){
int arr[103]{2,20,20,35,50,50,52,53,54,54,55,55,58,63,64,64,65,65,71,73,73,74,75,75,77,221,267,289,290,290,292,300,303,308,308,308,312,312,314,314,315,323,323,325,330,331,331,332,333,338,339,347,347,356,359,361,361,362,363,364,365,365,372,372,383,383,388,394,394,401,404,404,413,413,170931,667182,667182,540028976,540028976,741551154,741551154,741684787,774455913,774455913,774778478,774778478,778265971,778265971,808531502,840969273,875310137,892416309,892416309,942815278,1292503603,1292503603,1667851881,1667851881,1869182049,1869182049,1919243808,1919243808,1919243808};
int n = sizeof(arr)/sizeof(arr[0]);
if(arraySortedCheck(arr, n)){
printf("Array is in sorted order\n");
}
else
printf("Array is not in sorted order\n");
return 0;
}
排序检查输出：
Array is in sorted order
在我的程序的验证阶段，参考数组使用库函数进行排序，然后与归并排序算法的输出数组进行比较，但是这个排序后的参考数组具有之前不存在的值
“排序参考数组”
[2,20,20,35,50,50,52,53,54,54,55,55,58,63,64,64,65,65,71,73,73,74,75,75,77,221,267,289,290,290,292,300,303,308,308,308,312,312,314,314,315,323,323,325,330,331,331,332,333,338,339,347,347,356,359,361,361,362,363,364,365,365,372,372,383,383,388,394,394,401,404,404,413,413,170931,667182,667182,540028976,540028976,741551154,741551154,774455913,774455913,774778478,774778478,778265971,778265971,808531502,840969273,875310137,892416309,892416309,942815278,959515229,1292503603,1292503603,1667851881,1667851881,1869182049,1869182049,1919243808,1919243808,959527217]
新值例如 959527217 或 959515229
因此验证表明数组不是排序的输入数组，即使它是
这是代码：
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/time.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <omp.h>
// Constants.h
#if !defined(MYLIB_CONSTANTS_H)
#define MYLIB_CONSTANTS_H 1
#endif
//Takes a sorted list of size n and a value, puts the value in one of n+1 possible positions,
//if value is same to an element of the list take the position before the first occurence of the same element
binarysearchfindlowerrank(int *in,int n,int value,int projection){
int* array= in+projection;
int L=0;
int R=n;
printf("\nLowerBinarysearchrankfinder: [");
for(int i=0;i<n; i++){
printf("%d,",array[i]);
}
printf("]\n");
while(R-L>1){
int middle = (R+L)/2;
printf("L:%d,middle:%d,R:%d,value:%d\n",L,middle,R,value);
if(array[middle]==value){
while(array[middle]==value&&middle>0){
middle=middle-1;
}
if(middle==0&&array[middle]>=value){
return 0;
}
else{
printf("L:%d,middle:%d,R:%d,result:%d,index:%d\n",L,middle,R,(middle+1),(middle+1+projection));
return middle+1;
}
}
if(array[middle]<value){
L=middle;
}
if(array[middle]>value){
R=middle;
}
}
printf("L:%d,R:%d,value:%d\n",L,R,value);
if(n==1){
if(array[0]>=value){
return 0;
}
else return 1;
}
if(L==0&&array[L]>value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,0,0+projection);
return 0;
}
if(R==n && array[R-1]< value){
printf("!!L:%d,R:%d,result:%d,index:%d\n",L,R,n,n+projection);
return n;
}
if(R==n&& array[R-1]>=value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,R-1,(R-1+projection));
return R-1;
}
if(array[R]<value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,R+1,(R+1+projection));
return R+1;
}
if(array[L]<value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,R,(R+projection));
return R;
}
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,L,(L+projection));
return L;
}
//Takes a sorted list of size n and a value, puts the value in one of n+1 possible positions,
//if value is same to an element of the list take the position after the last occurence of the same element
binarysearchfinduperrank(int *in,int n,int value, int projection){
int* array= in+projection;
int L=0;
int R=n;
printf("\nUpperBinarysearchrankfinder [");
for(int i=0;i<n; i++){
printf("%d,",array[i]);
}
printf("]\n");
while(R-L>1){
int middle = (R+L)/2;
printf("L:%d,middle:%d,R:%d,value:%d\n",L,middle,R,value);
if(array[middle]==value){
while(array[middle]==value&&middle<n){
middle=middle+1;
}
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,middle,middle+projection);
return middle;
}
if(array[middle]<value){
L=middle;
}
if(array[middle]>value){
R=middle;
}
}
printf("L:%d,R:%d,value:%d\n",L,R,value);
if(n==1){
if(array[0]> value){
printf(" result:0\n,index:%d\n",0+projection);
return 0;
}
else{
printf(" result:1,index:%d\n",1+projection);
return 1;
}
}
if(L==0&&array[L]>value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,0,projection);
return 0;
}
if(R==n && array[R-1]<= value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,n,n+projection);
return n;
}
if(R==n&& array[R-1]>value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,R-1,((R-1)+projection));
return R-1;
}
if(array[R]<=value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,R+1,(R+1+projection));
return R+1;
}
if(array[L]<=value){
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,R,R+projection);
return R;
}
printf("L:%d,R:%d,result:%d,index:%d\n",L,R,L,L+projection);
return L;
}
/**
* helper routine: check if array is sorted correctly
*/
bool isSorted(int ref[], int data[], const size_t size){
std::sort(ref, ref + size);
for (size_t idx = 0; idx < size; ++idx){
if (ref[idx] != data[idx]) {
printf("\nFalscher Index:%d\n",idx);
return false;
}
}
return true;
}
/**
* sequential merge step (straight-forward implementation)
*/
void MsMergeSequential(int *out, int *in, long begin1, long end1, long begin2, long end2, long outBegin,int *data,int *tmp) {
if(begin1==end2){
out[begin1]=in[begin1];
printf("\n[%d]\n",out[begin1]);
}
if(begin1==begin2||begin2==end2){
out[begin1+binarysearchfinduperrank(in,1,in[end2],begin1)]=in[end2];
out[begin1+binarysearchfindlowerrank(in,1,in[begin1],end2)]=in[begin1];
printf("\n[%d,%d]\n",out[begin1],out[end2]);
printf("\nDATA:n[");
for (size_t idx = 0; idx < 103; ++idx){
printf("%d,",data[idx]);
}
printf("]\n");
printf("\nTMP:[");
for (size_t idx = 0; idx < 103; ++idx){
printf("%d,",tmp[idx]);
}
printf("]\n");
}
else{
printf("begin:%d,middle1:%d:,middle2:%d,end:%d\n",begin1,end1,begin2,end2);
for(int i=0;i<(end2-begin2);i++){
out[begin1+i+binarysearchfinduperrank(in,(end1-begin1),in[begin2+i],begin1)]=in[begin2+i];
}
for(int i=0;i<(end1-begin1);i++){
out[begin1+i+binarysearchfindlowerrank(in,(end2-begin2),in[begin1+i],begin2)]=in[begin1+i];
}
printf("\n[");
for(int i=0;i<(end2-begin1);i++){
printf("%d,",out[i+begin1]);
}
printf("]\n");
printf("\nDATA:[");
for (size_t idx = 0; idx < 11; ++idx){
printf("%d,",data[idx]);
}
printf("]\n");
printf("\nTMP:[");
for (size_t idx = 0; idx < 11; ++idx){
printf("%d,",tmp[idx]);
}
printf("]\n");
}
}
bool myfunc (long i , long j){return (i<j);}
/**
* sequential MergeSort
*/
void MsSequential(int *array, int *tmp, bool inplace, long begin, long end) {
if (begin < (end - 1)) {
long half =(begin+end) / 2;
MsSequential(array, tmp, !inplace, begin, half);
MsSequential(array, tmp, !inplace, half, end);
if (inplace){
MsMergeSequential(array, tmp, begin, half, half, end, begin,array,tmp);
}
else {
MsMergeSequential(tmp, array, begin, half, half, end, begin,array,tmp);
}
}
else if (!inplace) {
tmp[begin] = array[begin];
printf("\n[%d]\n",tmp[begin]);
printf("\nDATA:[");
for (size_t idx = 0; idx < 11; ++idx){
printf("%d,",array[idx]);
}
printf("]\n");
printf("\nTMP:[");
for (size_t idx = 0; idx < 11; ++idx){
printf("%d,",tmp[idx]);
}
printf("]\n");
}
}
/**
* Serial MergeSort
*/
void MsSerial(int *array, int *tmp, const size_t size) {
MsSequential(array, tmp, true, 0, size);
}
/**
/**
* @brief program entry point
*/
int main(int argc, char* argv[]) {
// variables to measure the elapsed time
struct timeval t1, t2;
double etime;
// expect one command line arguments: array size
if (argc != 2) {
printf("Usage: MergeSort.exe <array size> \n");
printf("\n");
return EXIT_FAILURE;
}
else {
size_t stSize = strtol(argv[1], NULL, 10);
int *data2 = (int*) malloc(stSize * sizeof(int));
int *tmp = (int*) malloc(stSize * sizeof(int));
int *ref = (int*) malloc(stSize * sizeof(int));
printf("Initialization...\n");
srand(95);
for (size_t idx = 0; idx < stSize; ++idx){
data2[idx] = (int) (stSize * (double(rand()) / RAND_MAX));
}
stSize=103;
int data[103]{1919243808,365,372,383,394,404,413,170931,667182,540028976,741551154,774455913,774778478,778265971,840969273,892416309,942815278,1292503603,1667851881,1869182049,1919243808,35,20,20,50,50,52,53,54,54,55,55,58,63,64,64,65,388,401,65,71,73,73,74,75,75,77,289,290,290,292,300,303,308,308,308,267,312,312,314,314,315,323,323,325,330,332,333,338,339,347,347,361,221,372,383,394,404,331,331,413,2,741551154,892416309,875310137,808531502,540028976,778265971,1919243808,1667851881,1869182049,774778478,1292503603,774455913,667182,356,359,361,362,363,364,365,741684787};
std::copy(data, data + stSize, ref);
printf("START");
printf("\n[");
for (size_t idx = 0; idx < stSize; ++idx){
printf("%d,",ref[idx]);
}
printf("]\n");
printf("]");
double dSize = (stSize * sizeof(int)) / 1024 / 1024;
printf("Sorting %zu elements of type int (%f MiB)...\n", stSize, dSize);
gettimeofday(&t1, NULL);
MsSerial(data, tmp, stSize);
gettimeofday(&t2, NULL);
etime = (t2.tv_sec - t1.tv_sec) * 1000 + (t2.tv_usec - t1.tv_usec) / 1000;
etime = etime / 1000;
printf("done, took %f sec. Verification...", etime);
printf("\n[");
for (size_t idx = 0; idx < stSize; ++idx){
printf("%d,",ref[idx]);
}
printf("]\n");
printf("\n[");
for (size_t idx = 0; idx < stSize; ++idx){
printf("%d,",data[idx]);
}
printf("]\n");
if (isSorted(ref, data, stSize)) {
printf(" successful.\n");
}
else {
printf(" FAILED.\n");
}
printf("\n[");
for (size_t idx = 0; idx < stSize; ++idx){
printf("%d,",ref[idx]);
}
printf("]\n");
free(data2);
//delete[] data;
free(tmp);
//delete[] tmp;
free(ref);
//delete[] ref;
}
return EXIT_SUCCESS;
}
数组 ref 具有数组 data2 的大小，因此数组 ref 中的值多于数组 data 中的值，因此在对数组 ref 进行排序时，它还会查看与输入数组不同的其他值