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

Question

我面临一个单一的问题：
我有一个很大的table，内容是很多一对数字。我必须按降序对它们进行排序。我写了一个 BubbleSort 程序并且工作正常，但是完成它的工作很慢。所以我使用了一个 QuickSort 程序和...排序后数组内的数据发生变化！
所以我尝试了一个样本 table，具有相似的尺寸和 "easy-to-write" 内容，基本上是一个分配给

的圆环

    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;
}

再试一次，我把需要整理的数据放到这个程序里，结果又是错误的。

我会 link 代码，因为初始化向量很长。

http://pastebin.com/Ztwu6iUP

在此先感谢您的帮助！

编辑：我找到了部分解决方案。我没有使用 quickSort，即 unstable，而是使用了 mergeSort。现在，当我第二次对 table 进行排序时，对于第二列中的每个重复项（或相同值的三倍），在第一个列中，我将数据按升序排序。代码如下：

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 不同，因为它们有一个辅助字段，那么有一个 'stable' 快速排序的解决方案。

如果 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

是否有2个独立的排序？或者它是辅助字段排序。

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

按次要字段排序

要在辅助字段上排序，比较需要像 :-

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;
}

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

Quick sort and bubble sort give different results

c

arrays

sorting

quicksort

missing-data

按次要字段排序