氣泡排序的一個錯誤

我想排序一個2 * n矩陣，n在輸入中給出。製作一個程序來輸出一個矩陣。這裏是要求：氣泡排序的一個錯誤

第一列必須在ASC進行排序，並
在DESC如果可能的第二列。

例如，令n = 5，並且矩陣是

結果應該是

所以我寫下這樣的代碼。第一行輸入值n，然後輸入如上所示的行。

#include <stdio.h> 
#define TWO_16 65536 
#define TWO_15 32768 

int v[100000][2]; 
int z[100000]; 
int vec[100000]; 
int n; 


int main() 
{ 
    int i, j; 
    scanf ("%d", &n); // give the value of n; 
    for (i = 1; i <= n; i++) // filling the matrix; 
    { 
     scanf ("%d%d", &v[i][0], &v[i][1]); 
     z[i] = TWO_16 * v[i][0] + TWO_15 - v[i][1]; 
     vec[i] = i; 
    } 
    for (i = 1; i <= n; i++) 
     for (j = 1; j <= i; j++) 
     { 
      if (z[j] > z[i]) 
      { 
       int t = vec[i]; 
       vec[i] = vec[j]; 
       vec[j] = t; 
      } 
     } 

    for (i = 1; i <= n; i++) // output the matrix 
     printf("%d %d\n",v[vec[i]][0],v[vec[i]][1]); 
    return 0; 
}

但在GCC，輸出是

更重要的是，當第一行被改變爲「1 2」，第二個是在輸入變爲「3 4」，結果也改變了。

我的代碼有什麼問題？

其他信息：

我使用z[]因爲我用的是滿足這個問題的需求的功能，這樣我就可以簡單地對它們進行排序。並且vec[]存儲原始索引，因爲移動數組可能會花費大量時間。所以v[vec[i]][0]意味着'新'陣列的項目i。請注意，不使用v [0]。 n小於100000，不等於。

來源

2013-10-03 Alogfans

*「但是在GCC，輸出爲」 *就好像它甚至有可能是gcc的錯誤......不應該使用gcc標記，而是使用c標記。 –

不明白爲什麼這會被downvoted，至少不會處於當前編輯狀態。 –

整個'z []'事物不屬於佈雷分類算法。見http://en.wikipedia.org/wiki/Bubble_sort – vines

您正在比較存儲在z[]中的值，但交換了vec的元素。所以當begginig您有：

i vec  z 
------------------ 
1 1  z[1] 
2 2  z[2] 
3 3  z[3] 
...

用於例如後3

i vec  z 
------------------ 
1 1  z[1] 
2 3  z[2] 
3 2  z[3] 
...

交換2，你將有vec和z之間存在不正當的映射。

因此，在另一次迭代中，您將再次將z[2]與z[3]進行比較，並且您將不得不交換vec的元素。這就是爲什麼你應該至少還掉的vec

i vec  z 
------------------ 
1 1 z[vec[1]] = z[1] 
2 3 z[vec[2]] = z[3] 
3 2 z[vec[3]] = z[2] 
...

添加這應該做的伎倆使用z元素的z或索引元素的元素

... 
int t = vec[i]; 
vec[i] = vec[j]; 
vec[j] = t; 
//Add this also when swapping vec 
t = z[i]; 
z[i] = z[j]; 
z[j] = t; 
...

來源

2013-10-03 10:49:48 zoska

數組索引從0開始，所以你的圈子中，必須從0

if (z[j] > z[i])開始：要排序v但你比較z和排序vec。通過排序vec和比較z冒泡排序不起作用。你必須使用相同的數組。

來源

2013-10-03 09:27:53 Federico

氣泡排序的一個錯誤

回答

相關問題