Thread: Bubblesorting Array elements

Originally Posted by wufflz

oh my god, your right. It didnt even cross my mind (nor my eyes) to look at that.

Now it works properly, thanks for point that out to me.

Why didn't your compiler warn you? Have you got compiler warnings turned on?

Originally Posted by Hodor

Why didn't your compiler warn you? Have you got compiler warnings turned on?

I think my compiler warnings are on, im using Visual Studio 2019 (havent changed any of the settings).
I also debugged but that didnt show anything either.

The problem was this: (my code without the proper output)

Code:

printf("\nDas ist der %i. Wert bei der sortierung: %i", e + 1, e + 1, array2[e]);

The solution :

Code:

printf("\nDas ist der %i. Wert bei der sortierung: %i: %i ", e + 1, e + 1, array2[e]);

I dont know if the compiler warns for things like that since its only missing %i

@Zeus_: re Bubblesorting Array elements

That is not bubble sort, it's insertion sort.

Apart from the discussion I've had with laserlight -- and I have conceded that her point about early termination is correct -- the code in your post is still not bubble sort because in bubble sort the inner loop steps in the opposite direction to the outer loop. Both your loops start from lower array indices and work upwards. In bubble sort the loops "step" in opposite directions; e.g. if the outer loop decrements the inner loop increments. If they both step in the same direction then it's insertion sort. Not that it matters to the OP or probably anyone else because insertion sort implemented this way (i.e. not quite right) has the same O complexity as bubble sort (although maybe CPU pipelines etc etc make a difference). OP doesn't care about what it's called anyway, but still...

Originally Posted by wufflz

I dont know if the compiler warns for things like that since its only missing %i

I don't know either for Visual Studio 2019. Both gcc and clang do warn though. Maybe google for VS 2019 enable warnings? Maybe it doesn't warn but I find that hard to believe.

Originally Posted by Hodor

I don't know either for Visual Studio 2019. Both gcc and clang do warn though. Maybe google for VS 2019 enable warnings? Maybe it doesn't warn but I find that hard to believe.

I checked, its possible to change to warning lvl of the compiler (it was on 3) next step is 4 and then enable all warnings.
I tried both (with the missing %i) but it didnt show any warnings.

Originally Posted by wufflz

I checked, its possible to change to warning lvl of the compiler (it was on 3) next step is 4 and then enable all warnings.
I tried both (with the missing %i) but it didnt show any warnings.

That's weird and unfortunate

Code:

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

#define NELEMS(a) (sizeof ((a)) / sizeof (a[0]))

/* Exercise for reader to complete: Add printf()s to show the values of
 * i, j and the value of the elements being swapped. The difference between
 * dodgybubblesort() and dodgyinsertionsort() is quite apparent because of the
 * way the array is traversed.
 */


void bubblesort(int a[], size_t n)  /* Knuth's algorithm */
{
    size_t i, j;
    int has_swapped = 1;

    j = n;
    while (has_swapped) {
        has_swapped = 0;
        for (i = 1; i < j; ++i) {
            if (a[i] < a[i - 1]) {
                int t = a[i];   /* Swap */
                a[i] = a[i - 1];
                a[i - 1] = t;
                has_swapped = 1;
            }
        }
        --j;
    }
}

void dodgybubblesort(int a[], size_t n)
{
    size_t i, j;
    for(i = 1; i < n; ++i) {
        for(j = 0; j < i; ++j) {
            if(a[i] < a[j]) {
                int t = a[i];   /* Swap */
                a[i] = a[j];
                a[j] = t;
            }
        }
    }
}

void dodgyinsertionsort(int a[], size_t n)
{
    size_t i, j;
    for (i = 1; i < n; ++i) {
        for (j = 0; j < i; ++j) {
            if (a[i] < a[j]) {
                int t = a[i];   /* Swap */
                a[i] = a[j];
                a[j] = t;
            }
        }
    }
}

void printarray(int a[], size_t n)
{
    size_t i;
    for (i = 0; i < n; ++i) {
        printf("%d", a[i]);
    }
    printf("\n");
}


int main(void)
{
    /* Could use const arrays and copy but this is a quick and dirty
     * example
     */
    int a1[] = {6, 5, 4, 3, 2, 1};
    int a2[] = {6, 5, 4, 3, 2, 1};
    int a3[] = {6, 5, 4, 3, 2, 1};

    printf("bubble sorted      : ");
    bubblesort(a1, NELEMS(a1));
    printarray(a1, NELEMS(a1));

    printf("dodgy bubble sorted: ");
    dodgybubblesort(a2, NELEMS(a2));
    printarray(a2, NELEMS(a2));

    printf("dodgy insert sorted: ");
    dodgyinsertionsort(a3, NELEMS(a3));
    printarray(a3, NELEMS(a3));

    return 0;
}

Code:

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

#define NELEMS(a) (sizeof ((a)) / sizeof (a[0]))

/* Exercise for reader to complete: Add printf()s to show the values of
 * i, j and the value of the elements being swapped. The difference between
 * dodgybubblesort() and dodgyinsertionsort() is quite apparent because of the
 * way the array is traversed.
 */


void bubblesort(int a[], size_t n)  /* Knuth's algorithm */
{
    size_t i, j;
    int has_swapped = 1;

    j = n;
    while (has_swapped) {
        has_swapped = 0;
        for (i = 1; i < j; ++i) {
            if (a[i] < a[i - 1]) {
                int t = a[i];   /* Swap */
                a[i] = a[i - 1];
                a[i - 1] = t;
                has_swapped = 1;
            }
        }
        --j;
    }
}

void dodgybubblesort(int a[], size_t n)
{
    size_t i, j;
    for (i = n - 1; i > 0; --i) {
        for (j = 0; j < i; ++j) {
            if (a[j + 1] < a[j]) {
                int t = a[j];   /* Swap */
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }
}

void dodgyinsertionsort(int a[], size_t n)
{
    size_t i, j;
    for (i = 1; i < n; ++i) {
        for (j = 0; j < i; ++j) {
            if (a[i] < a[j]) {
                int t = a[i];   /* Swap */
                a[i] = a[j];
                a[j] = t;
            }
        }
    }
}

void printarray(int a[], size_t n)
{
    size_t i;
    for (i = 0; i < n; ++i) {
        printf("%d", a[i]);
    }
    printf("\n");
}


int main(void)
{
    /* Could use const arrays and copy but this is a quick and dirty
     * example
     */
    int a1[] = {6, 5, 4, 3, 2, 1};
    int a2[] = {6, 5, 4, 3, 2, 1};
    int a3[] = {6, 5, 4, 3, 2, 1};

    printf("bubble sorted      : ");
    bubblesort(a1, NELEMS(a1));
    printarray(a1, NELEMS(a1));

    printf("dodgy bubble sorted: ");
    dodgybubblesort(a2, NELEMS(a2));
    printarray(a2, NELEMS(a2));

    printf("dodgy insert sorted: ");
    dodgyinsertionsort(a3, NELEMS(a3));
    printarray(a3, NELEMS(a3));

    return 0;
}

Originally Posted by laserlight

This is not a bubble sort as it does not always swap adjacent elements:

I guess that's why you call it "dodgy bubble sort", but isn't that just misleading?

Yes, it's dodgy, but I edited my original post but it came up as a new post (?)

It's dodgy only because it's missing the terminating condition (well, Knuth's terminating condition). I don't know why the "edit post" made a new post rather than correcting the original one. But the main gist of things is the direction of the loops

Edit: I'm sorry it didn't edit the original post but I *did* hit edit post... I have no idea what happened

Originally Posted by Zeus_

> That is not bubble sort, it's insertion sort.

I'm pretty sure that that is bubble sort. I looked up through three references after you said that and I can tell for sure that it is not insertion sort. In fact, I looked up GeeksforGeeks to check if my understanding of bubble and insertion sort are correct. The bubble sort code that I posted is correct and similar to the one on their website unless they're wrong too. Insertion sort looks completely different to me and the two are not different because of the direction of loop movement. Insertion finds the smallest element, finds its correct position, right shifts each array element by one place from the position determined of the current element, and then places it at that index. Bubble sort, on the other hand, compares and swaps continuously until, let's say, the heaviest element is placed at it's correct position in ascending order bubble sort.

Insertion Sort - GeeksforGeeks
Bubble Sort - GeeksforGeeks

This is what I've learnt at school too and so I don't know if I'm wrong but I'm just sharing what I know and what I've learnt

Bubble sort misconceptions

Right at the bottom of the page

I guess that since in my first post (6 minutes before my corrected "dodgy" post) I implemented the dodgybubblesort() in a not-so-dodgy way is kind of how silly and confusing it is. But if I draw the iterations and swaps on paper, the dodgybubblesort() (second post!) is certainly what Knuth calls insertion sort (albeit badly implemented) and not what he calls bubble sort.