Solved

Bubble Sort needs a modification

Posted on 2008-10-30
4
717 Views
Last Modified: 2008-10-30
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

0
Comment
Question by:Doomtomb
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
4 Comments
 
LVL 53

Accepted Solution

by:
Infinity08 earned 500 total points
ID: 22845317
You only have to change the upper limit of the inner loop. Use the current value of 'pass' for that ...
0
 

Author Comment

by:Doomtomb
ID: 22845396
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
 

Author Comment

by:Doomtomb
ID: 22845417
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
 
LVL 53

Expert Comment

by:Infinity08
ID: 22845436
>> 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

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

707 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question