稳定标准库的qsort？ [英] Stabilizing the standard library qsort?

问题描述

我假设在STDLIB历久弥新qsort函数并不稳定，因为男人页面没有说什么。这就是我说的功能：

 的#include＆LT;＆stdlib.h中GT;
   无效的qsort（无效*基地​​，为size_t nmemb个，为size_t大小，
              INT（* COMPAR）（常量无效*，常量无效*））;
 

我认为如果我改变我的比较功能，还包括对那些为我比较地址，这将是稳定的。那是对的吗？

例如：

  INT compareFoos（常量无效* pA的，常量无效* PB）{
    美孚* pFooA =（美孚*）pA的;
    美孚* pFooB =（美孚*）PB;    如果（pFooA-＆GT; ID＆LT; pFooB-＆GT; ID）{
        返回-1;
    }如果别人（pFooA-＆GT; ID＆GT; pFooB-＆GT; ID）{
        返回1;
    }否则如果（PA＆LT; PB）{
        返回-1;
    }否则如果（PB＆GT; PA）{
       返回1;
    }其他{
       返回0;
    }
}
 

解决方案

没有，你不能依赖于不幸。让我们假设你有阵列（每个记录两个字段用于检查，但用于排序仅第一场​​）：

  BBBB，1
BBBB，2
AAAA，3
 

快速排序可以比较BBBB，1 AAAA，3和交换它们，赠送：

  AAAA，3
BBBB，2
BBBB，1
 

如果下一个步骤是比较BBBB，2 BBBB，1，密钥将是相同的，而且由于BBBB，2具有的地址小于BBBB，1，没有交换将发生。对于一个稳定的排序，你应该已经结束了：

  AAAA，3
BBBB，1
BBBB，2
 

要做到这将是附加的启动的指针的地址（而不是它的电流的地址）和排序使用以及其他键的唯一途径。这样一来，原来的地址变成了排序键的小部分，使 BBBB，1 BBBB之前将最终结束了，2 无论在分拣过程中，两个 BBBB 线去哪里。

I'm assuming that the good old qsort function in stdlib is not stable, because the man page doesn't say anything about it. This is the function I'm talking about:

   #include <stdlib.h>
   void qsort(void *base, size_t nmemb, size_t size,
              int(*compar)(const void *, const void *));

I assume that if I change my comparison function to also include the address of that which I'm comparing, it will be stable. Is that correct?

Eg:

int compareFoos( const void* pA, const void *pB ) {
    Foo *pFooA = (Foo*) pA;
    Foo *pFooB = (Foo*) pB;

    if( pFooA->id < pFooB->id ) {
        return -1;
    } else if( pFooA->id > pFooB->id ) {
        return 1;
    } else if( pA < pB ) {
        return -1;            
    } else if( pB > pA ) {
       return 1;
    } else {
       return 0;
    }
}

解决方案

No, you cannot rely on that unfortunately. Let's assume you have the array (two fields in each record used for checking but only first field used for sorting):

BBBB,1
BBBB,2
AAAA,3

Quicksort may compare BBBB,1 with AAAA,3 and swap them, giving:

AAAA,3
BBBB,2
BBBB,1

If the next step were to compare BBBB,2 with BBBB,1, the keys would be the same and, since BBBB,2 has an address less than BBBB,1, no swap will take place. For a stable sort, you should have ended up with:

AAAA,3
BBBB,1
BBBB,2

The only way to do it would be to attach the starting address of the pointer (not its current address) and sort using that as well as the other keys. That way, the original address becomes the minor part of the sort key so that BBBB,1 will eventually end up before BBBB,2 regardless of where the two BBBB lines go during the sorting process.

这篇关于稳定标准库的qsort？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！