I've started learning C last month and I am stuck with a question, my bubble sort algorithm is somehow producing duplicate values and I can't figure out why?

#include <stdio.h>

void BubbleSort(int numarr[]) {
    int j, k, t;
    for (j = 20; j > 1; j--) {
        for (k = 0; k < j - 1; k  ) {
            if (numarr[k] > numarr[k   1]) {
                t = numarr[k]; numarr[k   1] = numarr[k]; numarr[k   1] = t;
            }            
        }
    }
}

int main() {
    int numarr[] = {
         2,  3,  5,  7, 12, 11, 13, 24, 17, 19,
        36, 23, 29, 52, 31, 37, 68, 41, 43, 84
    };
    BubbleSort(numarr);
    for (int i = 0; i < 20; i  ) {
        printf("%d\n", numarr[i]);
    }
}

This is the output I am getting is:

2
3
5
7
12
12
13
24
24
24
36
36
36
52
52
52
68
68
68
84.

Can you guys help me?

CodePudding user response：

The swap code isn't right. The posted code is:

t = numarr[k];numarr[k 1] = numarr[k];numarr[k 1] = t;

It should be:

t = numarr[k];numarr[k] = numarr[k 1];numarr[k 1] = t;

This might be more clearly written as:

t = numarr[k];
numarr[k] = numarr[k 1];
numarr[k 1] = t;

CodePudding user response：

The bug comes from your swapping code: you update numarr[k 1] twice and do not change numarr[k].

It is recommended to write a single statement per line, and it would have made the mistake more obvious.

Note also that you should pass the number of elements of the array to the BubbleSort function, instead of hard coding a length of 20.

Here is a modified version:

#include <stdio.h>

void BubbleSort(int numarr[], int len) {
    for (int j = len; j > 1; j--) {
        for (int k = 0; k < j - 1; k  ) {
            if (numarr[k] > numarr[k   1]) {
                int t = numarr[k];
                numarr[k] = numarr[k   1];
                numarr[k   1] = t;
            }            
        }
    }
}

int main() {
    int numarr[] = {
         2,  3,  5,  7, 12, 11, 13, 24, 17, 19,
        36, 23, 29, 52, 31, 37, 68, 41, 43, 84
    };
    int len = sizeof(numarr) / sizeof(numarr[0]);
    BubbleSort(numarr, len);
    for (int i = 0; i < len; i  ) {
        printf("%d\n", numarr[i]);
    }
    return 0;
}