c - 有没有更好的插入排序方法？

Question

YouTube 视频到插入排序 - https://www.youtube.com/watch?v=JU767SDMDvA

这是我用 C 实现的

void insertionSort(void *data, uint32_t length, int8_t compareTo(const void * const, const 
  void * const), const size_t bytes){
  uint32_t i;
  for(i = 0; i < length; i++){
    uint8_t isSorted;
    int32_t j;
    isSorted = 0;
    for(j = i - 1; j > -1 && !isSorted; j--){
        isSorted = 1;
        if(compareTo((int8_t *)data + j * bytes, (int8_t *)data + (j + 1) * bytes) > 0){
            uint32_t byteIndex;
            void *valCopy;
            valCopy = malloc(bytes);
            memcpy(valCopy, (int8_t *)data + j * bytes, bytes);

            for(byteIndex = 0; byteIndex < bytes; byteIndex++){
                *((int8_t *)data + (j * bytes + byteIndex)) = *((int8_t *)data + ((j + 1) * bytes + byteIndex));
                *((int8_t *)data + ((j + 1) * bytes + byteIndex)) = *((int8_t *)valCopy + byteIndex);
            }

            /**
            instead of the for loop you can replace it with this to make it look more clean
            memcpy((int8_t *)data + j * bytes, (int8_t *)data + (j + 1) * bytes, bytes);
            memcpy((int8_t *)data + (j + 1) * bytes, valCopy, bytes);
            **/

            free(valCopy);
            isSorted = 0;
      }
    }
  }
}


int8_t compareTo(const void * const val1, const void * const val2){
   if(*(const int32_t * const)val1 > *(const int32_t * const)val2)return 1;
   else if(*(const int32_t * const)val1 < *(const int32_t * const)val2)return -1;
   return 0;
}

int main(void){
   int32_t i;
   int32_t data[] = {2, 6, 5, 3, 8, 7, 1, 0};
   int32_t dataLength = sizeof(data) / sizeof(*data);

   insertionSort(data, dataLength, &compareTo, sizeof(int32_t));

   for(i = 0; i < dataLength; i++){
       printf("%d ", data[i]);
   }

   return 0;
}

我想知道是否有比每次使用 memcpy 或 for 循环复制值更有效的方法？

Answer 1

正如另一个答案已经观察到的那样，不需要为每个交换调用 malloc() 和 free() 。所有这些额外的调用确实似乎是效率低下的最大根源。您最多需要一次 malloc 和一次 free 调用，但对于不大于您选择的限制的项目大小，您可以无需任何调用。例如，

#define SMALL_ITEM_LIMIT 1024 /* for example */

// ...

void insertionSort(void *data, uint32_t length,
    int8_t compareTo(const void * const, const void * const), const size_t bytes) {
    char auto_buffer[SMALL_ITEM_LIMIT];
    char *temp;

    if (bytes > SMALL_ITEM_LIMIT) {
        temp = malloc(bytes);
        if (temp == NULL) {
            // ... handle allocation failure ...
        }
    } else {
        temp = auto_buffer;
    }

    // ... main part of the sort ...

    if (temp != auto_buffer) {
        free(temp);
    }
}

作为一个小问题，变量 isSorted 的使用是不必要的，而且有点笨拙。您可以避免这种情况，并且只需在当前元素到达其插入位置时从 j 循环中 break 就可以节省一些周期。

你问:

I was wonder if there is a more efficient way then to copy the value each time using memcpy or the for loop?

对于像这样的通用排序，如果您不知道要排序的项目的类型，则除了移动元素的大容量内存操作之外，没有其他选择。我倾向于从 memcpy() 和/或 memmove() 开始，因为它更清晰。如果没有对各种情况进行测试以确定它是否真正提供了任何改进，请勿使用内部循环。

但是，您不一定需要一次将元素移动一个位置。相反，在每次外循环迭代中，您可以在不移动任何内容的情况下找到插入位置，然后通过单个 n 元素旋转来执行插入。对于随机数据，这往往会执行更少的读取和写入。该变体可能如下所示(一些名称已更改以使它们更清晰):

void insertionSort(void *data, uint32_t item_count,
        int compare(const void *, const void *), size_t item_size) {
    char auto_buffer[SMALL_ITEM_LIMIT];
    char *temp = (item_size > SMALL_ITEM_LIMIT) ? malloc(item_size) : auto_buffer;

    if (temp) {
        char *char_data = data;  // for clarity; avoids having to cast all the time

        for (uint32_t i = 1; i < count; i++) { // no point in starting at 0
            // Find the insertion position
            for (uint32_t j = i; j > 0; j--) {
                if (compare(char_data +  j      * item_size,
                            char_data + (j - 1) * item_size) >= 0) {
                    break;
                }
            }
            // Rotate the current item into position
            if (j != i) {
                memcpy(temp, char_data + i * item_size, item_size);
                memmove(char_data +  j      * item_size,
                        char_data + (j + 1) * item_size,
                        (i - j) * item_size);
                memcpy(char_data + j * item_size, temp, item_size);
            }
        }

        if (temp != auto_buffer) {
            free(temp);
        }
    } // else memory allocation failed
}

或者，在实践中，更并行地实现轮换和比较可能会更有效，以更好地利用缓存和数据局部性。这就像每次交换只执行一半(或者可能三分之一)的交换。其排序循环将是这样的:

        for (uint32_t i = 1; i < count; i++) { // no point in starting at 0
            // store element i
            memcpy(temp, char_data + i * item_size, item_size);

            // Find the insertion position
            for (uint32_t j = i; j > 0; j--) {
                if (compare(char_data +  j      * item_size,
                            char_data + (j - 1) * item_size) < 0) {
                    // shift element j - 1 up one position
                    memcpy(char_data + (j - 1) * item_size,
                           char_data +  j      * item_size,
                           item_size);
                } else {
                    break;
                }
            }

            if (j != i) {
                // Put the erstwhile value of element i into its position
                memcpy(char_data + j * item_size, temp, item_size);
            }
        }

在任何特定情况下，哪一个实际上在实践中表现更好是一个需要通过测试来回答的问题。