C Bubble Sort

[KalamyQ]

I'm attempting to build Bubble sort in C and have gotten thus far, but it's not sorting correctly. Here, is the article I read from https://www.scaler.com/topics/c-bubble-sort/.

Code: Select all

#include<stdio.h>

int main()
{
    int n, i, j, a[5], b, temp;
    printf("Enter the number of elements to be sorted\n");
    scanf("%d", &n);
    for(i = 0; i < n; ++i)
    {
        printf("%d - Enter the elements - ", i);
        scanf("%d", &a[i]);
    }
    for(i = 0; i < n; ++i)
    {
        for(j = 0; j < n+1; ++j)
        {
            if(a[i] > a[i+1])
            {
                temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
        }
    }
    for (i = 0; i < n; ++i)
    {
        printf("%d\n", a[i]);
    }
    return 0;
}

Output:

Code: Select all

2
1
12
13

What am I missing?

[rockedge]

@misko_2083 might be able to help here. Last time I wrote a sort routine I used QuickBasic 4.5!

I didn't use a temp spot but swapped the two value's positions and continued the comparisons to get the bubble effect

[misko_2083]

I'm attempting to build Bubble sort in C and have gotten thus far, but it's not sorting correctly. Here, is the article I read from https://www.scaler.com/topics/c-bubble-sort/.

Code: Select all

#include<stdio.h>

int main()
{
    int n, i, j, a[5], b, temp;
    printf("Enter the number of elements to be sorted\n");
    scanf("%d", &n);
    for(i = 0; i < n; ++i)
    {
        printf("%d - Enter the elements - ", i);
        scanf("%d", &a[i]);
    }
    for(i = 0; i < n; ++i)
    {
        for(j = 0; j < n+1; ++j)
        {
            if(a[i] > a[i+1])
            {
                temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
        }
    }
    for (i = 0; i < n; ++i)
    {
        printf("%d\n", a[i]);
    }
    return 0;
}

Output:

Code: Select all

2
1
12
13

What am I missing?

You don't know how to use nested loops.

Code: Select all

    // i - number of passes.
    for(i = 0; i < n-1; i++)   // n-1 because arrays start with 0
    {
        for(j = 0; j < n-i-1; j++)   // iterate through each element
        {
            if(a[j] > a[j+1])  // compare current element with next, if bigger swap
            {
                // swap places
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }

The biggest element goes to the end, therefore no need to check if previous element is bigger than the last one in the next pass.
Each pass sorts less elements.
Smaller go to the

This is not optimal because it happens to repeats the loop even though array is sorted.

Code: Select all

Enter the number of elements to be sorted
4
0 - Enter the elements - 9
1 - Enter the elements - 1
2 - Enter the elements - 3
3 - Enter the elements - 7
Pass 1
 1 3 7 9    <= Already sorted on first pass
Pass 2
 1 3 7 9
Pass 3
 1 3 7 9
Final
 1 3 7 9

So you set a variable inside a loop and after each pass check if it changed.
If the variable changed you continue to run the loop.
If it didn't change that means no element has been swapped and array is sorted, so you break the loop to save some processor time.

Code: Select all

#include <stdbool.h>
...

bool c; 

    for(i = 0; i < n-1; i++)
    {
        c = true;                     // set the variable
        for(j = 0; j < n-i-1; j++)
        {
            if(a[j] > a[j+1])
            {
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                c = false;           // swap occured
            }
        }
        if (c)                   // if c == true, swap not occured, therefore array is already sorted, break the loop
            break; 

To see what's going on on each pass.

Code: Select all

#include<stdio.h>
#include <stdbool.h>

int main()
{
    int n, i, j, a[5], b, temp;
    bool c;
    printf("Enter the number of elements to be sorted\n");
    scanf("%d", &n);
    for(i = 0; i < n; i++)
    {
        printf("%d - Enter the elements - ", i);
        scanf("%d", &a[i]);
    }

    for(i = 0; i < n-1; i++)
    {
        c = true;
        for(j = 0; j < n-i-1; j++)
        {
            if(a[j] > a[j+1])
            {
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                c = false;
            }
        }

        if (c)
            break; 
            
         /* This print's out results on each pass, unused variable 'b' in your code was put to use here */
        printf("Pass %d\n", i+1);
        for (b = 0; b < n; b++)
        {
            printf(" %d", a[b]);
        }
        printf("\n");

    }
    printf("Final\n");
    for (i = 0; i < n; ++i)
    {
        printf(" %d", a[i]);
    }
    printf("\n");
    return 0;
}

Comment out next in previous code and give it a try.

Code: Select all

        if (c)
            break; 

[KalamyQ]

Thanks for the detailed clarification! I really appreciate it.

[technosaurus]

Bubble sort "bubbles" the value into the last element.
The following iteration can omit the last element (n-1) because it has been sorted already...

Code: Select all

     for (size_t i = 0; i < n; --n)

You were removing the first (unsorted) element instead of the last (sorted)

[BarryK]

@technosaurus
Hi, great to see you posting on this forum!
I greatly appreciated your contributions on the old forum.
I presume you are the same technosaurus!