开发者社区> 问答> 正文

为什么此优化会导致我的合并排序失败?

我正在进行非递归合并排序,并且我想出了一个优化方法,可以加快它的速度。要点是,我不是先合并到一个临时缓冲区中,然后每次将其复制回数据位置,而是先在一个方向上合并,然后再在另一个方向上合并。这应该完美地工作,因为缓冲区的大小相同且数据相同。

但是,当我尝试这样做时,我的数组未完全排序。有些项目不合时宜,有时在末尾,在中间。在下面的示例中,我包括了用于测试代码的函数。

我尽了最大的努力来制作MWE,但是测试需要一些辅助功能。

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MIN(x, y) ((x) > (y) ? (y) : (x))
#define OPTIMIZE true // if true, then merge in alternating directions

void merge(int* src, int* dest, size_t start, size_t mid, size_t end);
void merge_sort(int* data, size_t length);

/* MERGESORT IMPLEMENTATION {{{1 */

void merge(int* src, int* dest, size_t start, size_t mid, size_t end) {
    int i, j, k;
    for (i = start, j = mid, k = start; i < mid && j < end; k++) {
        if (src[i] > src[j]) {
            dest[k] = src[j];
            j++;
        } else {
            dest[k] = src[i];
            i++;
        }
    }
    for (; i < mid; i++, k++) {
        dest[k] = src[i];
    }
    for (; j < end; j++, k++) {
        dest[k] = src[j];
    }
}

void merge_sort(int* data, size_t length) {
    int* buffer = malloc(length * sizeof(int));
    int swap = false;
    for (size_t i = 0; i < length; i++) {
        buffer[i] = data[i];
    }

#if OPTIMIZE
    for (size_t step = 1; step < length; step *= 2, swap = !swap) {
        int* src = swap ? buffer : data;
        int* dest = swap ? data : buffer;
        for (size_t i = 0; i < length - step; i += (step * 2)) {
            merge(src, dest, i, i + step, MIN(length, i + (step * 2)));
        }
    }
    if (swap) {
        for (size_t i = 0; i < length; i++) {
            data[i] = buffer[i];
        }
    }
#else
    for (size_t step = 1; step < length; step *= 2, swap = !swap) {
        int* src = data;
        int* dest = buffer;
        for (size_t i = 0; i < length - step; i += (step * 2)) {
            merge(src, dest, i, i + step, MIN(length, i + (step * 2)));
        }
        for (size_t i = 0; i < length; i++) {
            data[i] = buffer[i];
        }
    }
#endif

    free(

展开
收起
几许相思几点泪 2019-12-29 20:59:03 6055 0
1 条回答
写回答
取消 提交回答
  • 这似乎正在工作。注释中指出的修复:

    void merge_sort(int* data, size_t length) {
        int* buffer = malloc(length * sizeof(int));
        int swap = false;
        /*                                  ** removed the initial copy */
    
    #if OPTIMIZE
        for (size_t step = 1; step < length; step *= 2, swap = !swap) {
            int* src = swap ? buffer : data;
            int* dest = swap ? data : buffer;
            size_t i;                       /* fix, using i in 2nd loop */
            for (i = 0; i < length - step; i += (step * 2)) {  /* fix (removed size_t) */
                merge(src, dest, i, i + step, MIN(length, i + (step * 2)));
            }
            for( ; i < length; i++)         /* fix, copy single run if present */
                dest[i] = src[i];           /* fix, copy single run if present */
        }
        if (swap) {
            for (size_t i = 0; i < length; i++) {
                data[i] = buffer[i];
            }
        }
    #else
    
    

    替代修补程序:

    for (size_t step = 1; step < length; step *= 2, swap = !swap) {
         int* src = swap ? buffer : data;
         int* dest = swap ? data : buffer;
         for (size_t i = 0; i < length; i += (step * 2)) {                        /* fix */
             merge(src, dest, i, MIN(length, i+step), MIN(length, i+(step * 2))); /* fix */
         }
    
    2019-12-29 20:59:30
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载