Ċ½ilvinas Ċ½ilvinas - 1 month ago 19
C Question

If entered an even number of integers in bubble sort program a random number is inserted in the middle

I have a task to sort negative and positive numbers while using dynamic memory, therefore in this case I used calloc and bubble sort to arrange negative numbers first while not changing their order. The problem is when I enter an even number of integers, in the middle of the result some random negative number of 10 digits appears. The same doesn't happen with odd number of integers. What seems to be the problem?

#include <stdio.h>
#include <stdlib.h>

#define SIZE 1000

void swap(int *arr, int n) {
int i, j, temp;
for (i = 0; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (arr[j] < 0) {
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
printf("sorted integers to negative and positive: \n");
for (i = 0; i < n; i++) {
printf("%i ", arr[i]);
}
}

int main() {
int n;
int i, *sk;
printf("Enter integer: \n");
scanf("%d", &n);
printf("Enter %i integers: \n", n);
sk = (int*)calloc(sizeof(int), n);
for (i = 0; i < n; i++) {
scanf("%d", sk + i);
}
swap(sk, n);
return 0;
}

Answer

You have 2 classic bugs in your for loops:

for (i = 0; i <= n; i++) is almost always wrong because the loop is run n + 1 times, where it should only enumerate index values from 0 to n - 1.

You have the same off by one error in the second loop: the test j <= n makes you go one step too far and read beyond the end of the array. Some random value gets shuffled into the array, but this undefined behavior could have worse consequences.

Furthermore, your comparison test is incorrect, it should be if (arr[j] < arr[j-1]).

As a rule of thumb, whenever you see the <= operator in a loop test, look again, it is probably a bug.

Here is a corrected version:

void swap(int *arr, int n) {
    int i, j, temp;
    for (i = 0; i < n; i++) {
        for (j = 1; j < n; j++) {
            if (arr[j] < arr[j - 1]) {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
    }
    printf("sorted integers to negative and positive: \n");
    for (i = 0; i < n; i++) {
        printf("%i ", arr[i]);
    }
    printf("\n");
}