CODEWITHSUNDEEP
csorting
Alogfans
Alogfans

Reputation: 43

A bug on bubble sorting

I want to sort a 2*n matrix, n is given in the input. Make a program to output a matrix. Here is the requirement:

  1. the first column MUST be sorted in ASC, and
  2. the second column in DESC if possible.

For example, let n = 5, and the matrix is

3 4
1 2
3 5
1 6
7 3

The result should be

1 6
1 2
3 5
3 4
7 3

So I write down the code like this. First line input the value n, and the following lines like above.

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

But in gcc, the output is 

1 6
3 5
3 4
1 2
7 3

What's more, when the first line is changed to "1 2" and the second is changed to "3 4" in input, the result also changed.

What's the problem of my code?

Additional information:

I use z[] because I use a function that satisfy the requirement of this problem, so I can simply sort them. And vec[] stores the original index, because moving arrays may cost lots of time. So v[vec[i]][0] means the 'new' array's item i. Note that v[0] is NOT used. n is less than 100000, not equal.

Upvotes: 1

Views: 381

Answers (2)

zoska
zoska

Reputation: 1723

You are comparing values stored in z[], but swapping elements of vec. So when in the begginig you have:

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

After for e.g. swapping 2 with 3

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

you will have improper mapping between vec and z.

So in another iteration you will again compare z[2] with z[3] and again you will have to swap elements of vec. That's why you should at least also swap elements of z or index elements of z using elements of 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]
...

Adding this should do the trick

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

Upvotes: 2

Federico
Federico

Reputation: 3892

Array index start with 0, so your for cicles must start from 0

if (z[j] > z[i]): you want to sort v but you are comparing z and sorting vec. By sorting vec and comparing z bubble sort cannot work. You must use the same array.

Upvotes: 2

Related Questions