Bubble Sort needs a modification

I have a bubble sort script. It compares values after the first pass, the largest number is guaranteed to be in the highest -numbered element of the array; after the second pass, the two highest numbers are "in place", and so on. Instead of making nine comparisons on every pass, I need to modify the bubble sort to make eight comparisons on the second pass, seven on the third pass, and so on.

The code is attached, thank you.
#include <stdio.h>
#define SIZE 10
 
/* function main begins program execution */
int main( void )
{
	/* initialize a */
	int a[SIZE] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
	int pass; /* passes counter */
	int i; /* comparison counter */
	int hold; /* temporary location used to swap array elements */
 
	printf( "Data items in original order\n" );
 
	/* output original array */
	for ( i = 0; i < SIZE; i++ ) {
		printf( "%4d", a[ i ] );
	} /* end for */
 
	/* bubble sort */
	/* loop to control number of passes */
	for ( pass = 1; pass < SIZE; pass++ ) {
 
		/* loop to control number of comparisons per pass */
		for ( i = 0; i < SIZE - 1; i++ ) {
 
			/* compare adjacent elements and swap them if first element is greater than second element */
			if ( a[ i ] > a[ i + 1 ] ) {
				hold = a[ i ];
				a[ i ] = a[ i + 1 ];
				a[ i + 1 ] = hold;
			} /* end if */
 
		} /* end inner for */
 
	} /* end outer for */
 
	printf( "\nData items in ascending order\n" );
 
	/* output sorted array */
	for ( i = 0; i < SIZE; i++ ) {
		printf( "%4d", a[ i ] );
	} /* end for */
 
	printf( "\n" );
 
	return 0; /* indicates successful termination */
}

Open in new window

DoomtombAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Infinity08Commented:
You only have to change the upper limit of the inner loop. Use the current value of 'pass' for that ...
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
DoomtombAuthor Commented:
Ok, I think I got it, now I have one last modification I have to make:

The data in the array may already be in the proper order or near-proper order, so why make nine passes if fewer will suffice? Modify the sort to check at the end of each pass whether any swaps have been made. If none are made, then the data must already be in the proper order, so the program should end. If swaps have been made, then at least one more pass is needed.

(yes this is for a class)

I have attached the new script, all that's changed from the original is on the inner loop "i = 0" to "i = pass - 1"
/* Program 8: Due 10/31/08 
Description: Bubble Sort
for Sandra Jeffers
Engineering Programming EG1304
10:20am Mon-Wed-Fri */
#include <stdio.h>
#define SIZE 10
 
/* function main begins program execution */
int main( void )
{
	/* initialize a */
	int a[SIZE] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
	int pass; /* passes counter */
	int i; /* comparison counter */
	int hold; /* temporary location used to swap array elements */
	int swap;
 
	printf( "Data items in original order\n" );
 
	/* output original array */
	for ( i = 0; i < SIZE; i++ ) {
		printf( "%4d", a[ i ] );
	} /* end for */
 
	/* bubble sort */
	/* loop to control number of passes */
	for ( pass = 1; pass < SIZE; pass++ ) {
 
		/* loop to control number of comparisons per pass */
		for ( i = pass - 1; i < SIZE - 1; i++ ) {
 
			/* compare adjacent elements and swap them if first element is greater than second element */
			if ( a[ i ] > a[ i + 1 ] ) {
				hold = a[ i ];
				a[ i ] = a[ i + 1 ];
				a[ i + 1 ] = hold;
				swap++;
			} /* end if */
 
		} /* end inner for */
 
		if ( swap == 0 )
			break;
 
	} /* end outer for */
 
	printf( "\nData items in ascending order\n" );
 
	/* output sorted array */
	for ( i = 0; i < SIZE; i++ ) {
		printf( "%4d", a[ i ] );
	} /* end for */
 
	printf( "\n" );
 
	return 0; /* indicates successful termination */
}

Open in new window

0
DoomtombAuthor Commented:
NVMD I GOT this working, sorry, I stared at this for like 30 mins and had no clue and then in like 5 mins i tried just a couple things and it worked, sorry for wasting your time, ill award points.
0
Infinity08Commented:
>> all that's changed from the original is on the inner loop "i = 0" to "i = pass - 1"

Since you do your bubble sort starting from the back (ie. the last value is put in place first), it's better to change the upper limit, rather than the lower limit like you did ;)
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.