Ошибка при сортировке пузырьков

Question

Я хочу сортировать матрицу 2 * n, n указывается на входе. Сделайте программу для вывода матрицы. Здесь требование:

1. первый столбец должен быть отсортирован в ASC и
2. второго столбца в DESC, если это возможно.

Например, пусть п = 5, а матрица

3 4 
1 2 
3 5 
1 6 
7 3 

Результат должен быть

1 6 
1 2 
3 5 
3 4 
7 3 

Так я записываю код, как это. Первая строка вводит значение 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; 
} 

Но в НКУ, выход

1 6 
3 5 
3 4 
1 2 
7 3 

Более того, когда первая строка изменяется на «1 2», а второй изменяется на «3 4» на входе, результат также изменился.

В чем проблема с моим кодом?

Дополнительная информация:

Я использую z[] потому что я использую функцию, которая удовлетворяет требованиям этой проблемы, так что я могу просто отсортировать их. И vec[] хранит исходный индекс, потому что перемещение массивов может стоить много времени. Таким образом, v[vec[i]][0] означает элемент «нового» массива i. Обратите внимание, что v [0] НЕ используется. n меньше 100000, не равно.

Answer 1

Вы сравниваете значения, хранящиеся в z[], но заменяя элементы vec. Так что, когда в begginig у вас есть:

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

После для, например, замена 2 с 3

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

вы будете иметь неправильное отображение между vec и z.

Итак, в другой итерации вы снова сравните z[2] с z[3] и снова вам придется поменять элементы vec.Вот почему вы должны, по крайней мере, также поменять местами элементы z или индексных элементов г с использованием элементов 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] 
... 

Добавление этого следует сделать трюк

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

Answer 2

индекс массива начинается с 0, поэтому ваш для cicles должен начинаться от 0

if (z[j] > z[i]): вы хотите отсортировать v но вы сравниваете z и сортировки vec. Сортировка vec и сравнение z bubble sort не может работать. Вы должны использовать тот же массив.