bubble sort ideone time limit exceeded

问题:

#include <stdio.h>

int main(void) {

    int a[5]={1,2,0,5,4},i,j,c;
    for(i=0;i<5;i++)    
    {
        for(j=0;j<5-i;j++){
            if(a[j]>a[j+1])
            {
                c=a[j];
                a[j]=a[j+1];
                a[j+1]=c;
            }
        }
    }
    for(i=0;i<5;i++)
    {
    printf("%d",a[i]);
    }
    return 0;
}

ideone says "Time limit exceeded time: 5 memory: 2048 signal:24"

but it works fine on turbo compiler

回答1:

for(j=0;j<5-i;j++){
            if(a[j]>a[j+1])

a[j+1] is array out of bound access which will lead to undefined behavior

回答2:

Try this for bubble sort..Machine cycle will not be hampered in any compilers..

for (i = 0; i < count -1; i++)
      for (j = 0; j < ((count - 1) - i); j++) {
          if (memptr[j]>memptr[j+1]) {
              temp = memptr[j];
              memptr[j] = memptr[j + 1];
              memptr[j + 1] = temp;
          }
      }

回答3:

int a[5]={1,2,0,5,4}

So, for the following index you will get the following content:

index   ->| 0 | 1 | 2 | 3 | 4 |
content ->| 1 | 2 | 0 | 5 | 4 |

Now In your outer loop for(i=0;i<5;i++), for the first iteration i = 0, then the inner loop breaking condition will be,

for(j=0;j<5-i;j++)

or,

for(j=0;j<5-0;j++)

Hence the value of j will increase 0 to 4.

Now think what will happen a[j+1], when j = 4!

You are trying to access, a[4+1] or, a[5] where the index of array a is defined up to 4.

So at a[5], you will get Undefined behavior.

Try:

for(j=0; j<5 -i -1; j++)