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

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

插入排序不适合在数组上使用，因为必须执行数组的昂贵 re-arrangement。插入排序应该用在链表上。在数组上，一个类似但更好的算法是选择排序。当然分而治之算法如快速排序或归并排序也不错。

Answer 2

您的实现中效率最低的部分是对 malloc() 和 free() 的不必要调用，它们应该只需要调用一次，然后在算法中的每个交换中重复使用。这是一个可能的实现：

void isort(void* ptr, size_t count, size_t size, int (*comp)(const void*, const void*))
{
    size_t i;
    size_t j;
    bool sorted;
    void* a;
    void* b;
    void* t;

    // don't allocate temporary memory when unneeded
    if (count == 0) return;
    t = malloc(size);

    for (i = 0; i < count; ++i)
    {
        sorted = false;

        for (j = i - 1; j >= 0 && !sorted; --j)
        {
            sorted = true;
            a = (char*)ptr + size * j;
            b = (char*)ptr + size * (j + 1);

            if (comp(a, b) > 0)
            {
                memcpy(t, a, size);
                memcpy(a, b, size);
                memcpy(b, t, size);
                sorted = false;
            }
        }
    }

    free(t);
}

Try it on godbolt

Answer 3

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

#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 循环 breaking 来避免它并可能削减几个周期。

你问：

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() 开始，因为它更清晰。不要在没有测试各种情况以确定它是否真正提供任何改进的情况下使用内部循环。

但是，您不一定需要一次将元素移动一个位置。相反，在每次 outer-loop 迭代中，您可以在不移动任何东西的情况下定位插入位置，然后通过单个 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);
            }
        }

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

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

Is there a better way to do Insertion Sort?

c

algorithm

sorting

memcpy

insertion-sort