KalamyQ wrote: Wed Jul 20, 2022 10:34 am
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:
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.