c - 快速排序和冒泡排序给出不同的结果

Question

我面临一个奇怪的问题:
我有一个大表，其中内容是很多数字对。我必须按降序对它们进行排序。我编写了一个冒泡排序程序并且工作正常，但完成其工作非常慢。所以我使用了 QuickSort 过程并且...排序后数组内部的数据发生了变化!
所以我尝试使用一个示例表，具有相似的尺寸和“易于编写”的内容，基本上是一个分配给的cicle

    table[i][0]=i*3 

和

    table[i][1]=i*5 

并且...工作正常。

使用的代码如下:

typedef struct MATCHES {
    short size;
    unsigned short values[10000][2];
} MATCHES;



int partition(MATCHES **data, int left, int right, int pivot, int col){
        int temp;
        int i;
        int storeIndex = left;
        int pivotVal = (**data).values[pivot][col];
        (**data).values[pivot][col] = (**data).values[right][col];
        (**data).values[right][col] = pivotVal;

        for(i = left; i < right; i++){
            if ((**data).values[i][col] >= pivotVal){ //Change this to greater then and BOOM we're done
                temp = (**data).values[i][col];
                (**data).values[i][col] = (**data).values[storeIndex][col];
                (**data).values[storeIndex][col] = temp;
                storeIndex++;
            }
        }
        temp = (**data).values[storeIndex][col];
        (**data).values[storeIndex][col] = (**data).values[right][col];
        (**data).values[right][col] = temp;
        return storeIndex;
    }

void quickSort(MATCHES **vec, int left, int right, int col) {
    int r;
      if (right > left) {
        r = partition(vec, left, right, right+1/2, col);
        quickSort(vec, left, r - 1, col);
        quickSort(vec, r + 1, right, col);
      }
    }

void sorter(MATCHES *table) {
    quickSort(&table, 0, (*table).size-1, 0);
    quickSort(&table, 0, (*table).size-1, 1);
}


int main () {
    MATCHES table;
    table.size=10000;
    int i;
    for (i=0; i<table.size; i++) {
        table.values[i][0]=i*3;
        table.values[i][1]=i*5;
    }
    printf("Unsorted\n");
    for (i=0; i<table.size; i++)
        printf("%d %d\n",table.values[i][0],table.values[i][1]);
    sorter(&table);
    printf("Sorted\n");
    for (i=0; i<table.size; i++)
        printf("%d %d\n",table.values[i][0],table.values[i][1]);
    return 0;
}

为了再次尝试，我将需要排序的数据放入该程序中，结果再次错误。

我将链接代码，因为初始化 vector 导致代码非常长。

http://pastebin.com/Ztwu6iUP

预先感谢您的帮助!

编辑:我找到了部分解决方案。我没有使用不稳定的快速排序，而是使用了合并排序。现在，当我第二次对表进行排序时，对于第二列上的每个重复项(或相同值的三倍)，在第一个列中，我将数据按升序排序。代码如下:

void merge(MATCHES *v, int i1, int i2, int fine, int col, MATCHES *vout) {
    int i=i1, j=i2, k=i1;
    while (i<=i2-1 &&  j<=fine) {
        if ((*v).values[i][col]>(*v).values[j][col]) {
            (*vout).values[k][0]=(*v).values[i][0];
            (*vout).values[k][1]=(*v).values[i][1];
            i++;
        }
        else {
            (*vout).values[k][0]=(*v).values[j][0];
            (*vout).values[k][1]=(*v).values[j][1];
            j++;
        }
        k++;
    }
    while (i<=i2-1){
        (*vout).values[k][0]=(*v).values[i][0];
        (*vout).values[k][1]=(*v).values[i][1];
        i++;
        k++;
    }
    while (j<=fine){
        (*vout).values[k][0]=(*v).values[j][0];
        (*vout).values[k][1]=(*v).values[j][1];
        j++;
        k++;
    }
    for (i=i1; i<=fine; i++) {
        (*v).values[i][0]=(*vout).values[i][0];
        (*v).values[i][1]=(*vout).values[i][1];
    }
}

void mergeSort(MATCHES *v, int iniz, int fine, int col, MATCHES *vout) {
    int mid;
    if(iniz<fine){
        mid=(fine+iniz)/2;
        mergeSort(v, iniz, mid, col, vout);
        mergeSort(v, mid+1, fine, col, vout);
        merge(v, iniz, mid+1, fine, col, vout);
    }
}

有什么提示吗？

Answer 1

为了使用快速排序获得稳定性，您需要回答以下问题。

Can I tell the difference between a1 and a2?

如果 a1 和 a2 由于有辅助字段而不同，则有一个具有快速排序的“稳定”解决方案。

如果a1和a2因为添加时间不同而不同(这个字段无关紧要)，那么排序就不稳定，有时a1在a2之前，有时在a2之后。

在您的问题中，尚不清楚这些数字是否有关联

1,9
5,8
3,7
4,6

应该去:-

1,6
3,7
4,8
5,9

或

4,6
3,7
5,8
1,9

有两种独立的排序吗？或者它是辅助字段排序。

合并代码看起来像辅助字段排序。

按辅助字段排序

要对辅助字段进行排序，比较需要如下所示:-

int compare( Atype* lhs, Atype * rhs )
{
  if( lhs->field1 < rhs->field1 ) return -1;
  if( lhs->field1 > rhs->field1 ) return  1;

  if( lhs->field2 < rhs->field2 ) return -1;
  if( lhs->field2 > rhs->field2 ) return  1;

  /* more fields can be added here */
    return 0;
}

而不是单独对列进行排序

  quickSort(&table, 0, (*table).size-1, 0);
  quickSort(&table, 0, (*table).size-1, 1);

尝试以下操作。 将排序合并为一次:-

  quickSort(&table, 0, (*table).size-1 );

更改比较以采用基本数组

 int compare( short * lhs, short * rhs ) /* sort by 1 then 0 */
 {
  if( lhs[1] < rhs[1] ) return -1;
  if( lhs[1] > rhs[1] ) return  1;


  if( lhs[0] < rhs[0] ) return -1;
  if( lhs[0] > rhs[0] ) return  1;
  return 0;

 }     

分区变为

int partition(MATCHES **data, int left, int right, int pivot, int col){
    int temp;
    int i;
    int storeIndex = left;
    short pivotVal[2];
    pivotVal[0] = (**data).values[pivot][0];
    pivotVal[1] = (**data).values[pivot][1];
     /* here you were jumbling pivot value - not keeping [0,1] together */
    (**data).values[pivot][0] = (**data).values[right][0];
    (**data).values[pivot][1] = (**data).values[right][1];
    (**data).values[right][0] = pivotVal[0];
    (**data).values[right][1] = pivotVal[1];

    for(i = left; i < right; i++){
        if ( compare( (**data).values[i] , pivotVal ) >= 0){ //Change this to greater then and BOOM we're done
            temp = (**data).values[i][0];
            (**data).values[i][0] = (**data).values[storeIndex][0];
            (**data).values[storeIndex][0] = temp;

            temp = (**data).values[i][1];
            (**data).values[i][1] = (**data).values[storeIndex][1];
            (**data).values[storeIndex][1] = temp;

            storeIndex++;
        }
    }
    temp = (**data).values[storeIndex][0];
    (**data).values[storeIndex][0] = (**data).values[right][0];
    (**data).values[right][0] = temp;

    temp = (**data).values[storeIndex][1];
    (**data).values[storeIndex][1] = (**data).values[right][1];
    (**data).values[right][1] = temp;

    return storeIndex;
}