Bubble-Sort not sorting in C (Cormen's pseudocode)

Question

So I was trying to implement Cormen's pseudocode for bubble sorting but I can't seem to get it to work.

This is my approach on Cormen's pseudocode:

void BUBBLE_SORT(int a[200], int n) {
    int i, j, aux;

    for (i = 1; i <= n - 1; i++) {
        for (j = n; j < i + 1; j++) {
            if (a[j] < a[j - 1]) {
                aux = a[j];
                a[j] = a[j + 1];
                a[j + 1] = aux;
            }
        }
    }
}

I tried another piece of code found on the internet but the result was not different:

void bubbleSort(int arr[], int n) {
    int i, j;     
    for (i = 0; i < n - 1; i++)          
        for (j = 0; j < n - i - 1; j++)  
            if (arr[j] > arr[j + 1]) 
                swap(&arr[j], &arr[j + 1]);  
}

I would love to know where my comprehension failed in understanding Cormen's implementation and to get the bubble sorting to work!

Answer 1

There are at least three issues:

1. The pseudocode assumes array indices go from 1 to length. In C arrays are indexed from 0 to length-1; your code doesn't correct for that.

2. The inner loop in the pseudocode goes downto i+1, but your inner loop tries to count up:

   for(j=n;j<i+1;j++)
   

   should be

   for (j = n; j > i; j--)
   

3. The pseudocode swaps A[j] and A[j-1], but your C code swaps A[j] and A[j+1].

Answer 2

Mistakes in your implementation:

1. You start counting your array from 1th index. But in C programing a array start with 0th position. [you should right i = 0 instead of i = 1]
2. The inner loop must run from j = n-1 from j = i+1 and the value of j must be decreasing.
3. You compare a[j] with a[j-1] but u swap a[j] with a[j+1]. you should have swap a[j] with a[j-1]

See the changes in the code below. Hope it will be useful:

int i, j, aux;
for(i=0;i<n-1;i++){
    for(j=n-1;j>=i+1;j--){
        if(a[j]<a[j-1]){
            aux=a[j];
            a[j]=a[j-1];
            a[j-1]=aux;
        }
    }
}