Page 1 of 1

BUBBLE SORT C SORT TUTORIAL PART 2 Rate Topic: -----

#1 Elcric  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 101
  • View blog
  • Posts: 453
  • Joined: 02-May 09

Posted 20 July 2010 - 11:32 AM

BUBBLE SORT
C SORT TUTORIAL
PART 2

CONTENTS
• I. INTRODUCTION
• II. BUBBLE SORT
• III. EXAMPLE PROGRAM ANALYSIS
• IV. EXAMPLE PROGRAM
• V. REFERENCES


I. INTRODUCTION

Hello; nice to meet you. Welcome to “Bubble Sort - C Sort Tutorial Part 2.”

II. BUBBLE SORT

Sorting, is arranging the elements of an array in ascending or descending order. When you bubble sort you compare adjacent elements of an array and swap them if they are not in the proper order. After the bubble sort program completes a pass through the array it starts the process all over again. The bubble sort program needs one complete pass through the array without any swap to “know” it has sorted the array.

III. EXAMPLE PROGRAM ANALYSIS

Given the following two-dimensional array a[4][2]:

66 45
33 18
12 84
22 44

The array a[4][2] would be stored in computer memory linearly as follows:

66 45 33 18 12 84 22 44
..0..1...2...3..4...5..6...7 <= Linear index

The example bubble sort program is preceeded by a conversion of the two-dimensional array into a one-dimensional array. The conversion is not part of the bubble sort. However, the one-dimensional arrray closely mimics the way the two-dimensional array is stored in memory and will make it easier for me to describe the execution of the bubble sort program.

The example bubble sort program documentation explains the bubble sort process in detail.

The program does the comparison in pairs from right to left.

/* Compare */
printf("  If (( a[ %d ] = %d )  >  ( a[ %d ] =  %d )); then swap!\n\n", (j-1), a[j-1], j, a[j]);
if(a[ j - 1 ] > a[ j ])



For example, the first comparison asks if index 6 is greater than index 7; in other words, is 22 > 44?

66 45 33 18 12 84 22 44
..0...1..2...3...4..5...6...7 <= Linear index

The answer is no; therefore, the index moves one to the left and the new comparison asks if index 5 is greater than index 6; in other words, is 84 > 22?

66 45 33 18 12 84 22 44
..0...1..2...3...4..5...6...7 <= Linear index

66 45 33 18 12 22 84 44 <= Total Swaps equals 1
..0...1..2...3...4..5...6...7 <= Linear index

The answer is yes; therefore, 84 and 22 swap places, the index moves one to the left, and Total Swaps equals 1.

The new comparison asks if index 4 is greater than index 5, in other words is 12 > 22?

66 45 33 18 12 22 84 44
..0...1..2...3...4..5...6...7 <= Linear index

The answer is no; therefore, the index moves one to the left and the new comparison asks if index 3 is greater than index 4; in other words, is 18 > 12?

66 45 33 18 12 22 84 44
..0...1..2...3...4..5...6...7 <= Linear index

66 45 33 12 18 22 84 44 <= Total Swaps equals 2
..0...1..2...3...4..5...6...7 <= Linear index

The answer is yes; therefore, 18 and 12 swap places, the index moves one to the left, and Total Swaps equals 2.

The new comparison asks if index 2 is greater than index 3, in other words is 33 > 12?

66 45 33 12 18 22 84 44
..0...1..2...3...4..5...6...7 <= Linear index

66 45 12 33 18 22 84 44 <= Total Swaps equals 3
..0...1..2...3...4..5...6...7 <= Linear index

The answer is yes; therefore, 33 and 12 swap places, the index moves one to the left, and Total Swaps equals 3.

The new comparison asks if index 1 is greater than index 2, in other words is 45 > 12?

66 45 12 33 18 22 84 44
..0...1..2...3...4..5...6...7 <= Linear index

66 12 45 33 18 22 84 44 <= Total Swaps equals 4
..0...1..2...3...4..5...6...7 <= Linear index

The answer is yes; therefore, 45 and 12 swap places, the index moves one to the left, and Total Swaps equals 4.

The new comparison asks if index 0 is greater than index 1, in other words is 66 > 12?

66 12 45 33 18 22 84 44
..0...1..2...3...4..5...6...7 <= Linear index

12 66 45 33 18 22 84 44 <= Total Swaps equals 5
..0...1..2...3...4..5...6...7 <= Linear index

The answer is yes; therefore, 66 and 12 swap places and Total Swaps equals 5.

After the bubble sort program completes a pass through the array it starts the process all over again.

The new comparison asks if index 6 is greater than index 7, in other words is 84 > 44?

66 12 45 33 18 22 84 44
..0...1..2...3...4..5...6...7 <= Linear index

12 66 45 33 18 22 44 84 <= Total Swaps equals 6
..0...1..2...3...4..5...6...7 <= Linear index

The answer is yes; therefore, 84 and 44 swap places, the index moves one to the left, and Total Swaps equals 6.

As you can see, when you bubble sort you compare adjacent elements of an array and swap them if they are not in the proper order. After the bubble sort program completes a pass through the array it starts the process all over again. The bubble sort program needs one complete pass through the array without any swap to “know” it has sorted the array.


IV. EXAMPLE PROGRAM

/* ***************************
   BUBBLE SORT
   C SORT TUTORIAL
   PART 2
   *************************** */
#include<ctype.h>     /*  Character Class Tests  */
#include<math.h>      /*  Math Header.           */
#include<stdio.h>     /*  Standard I/O.          */
#include<stdlib.h>    /*  Utility Functions.     */

#define HEADER \
    "\n\n  BUBBLE SORT\n" \
	"  C SORT TUTORIAL\n" \
	"  PART 2\n\n" \

#define SIZE 8

/*  Converting two-dimensional array to one-dimensional array.  */
void arrayToArray( int bb[][2], int rr, int cc, int a[8] );

/*  Converting one-dimensional array to two-dimensional array.  */
void arrayConversion( int aa[][2], int rr, int cc, int a[8] );  

int main( int argc, char* argv[] )
{

	int r = 4;  /*  Rows.     */
	int c = 2;  /*  Columns.  */
	
	char nxt;
	int  u    = 0;
	int  i    = 0;
	int  j    = 0;
	int  s    = 0;
	int  temp = 0;
	int  swap = 0;

	/*  Declaration of array aa[ 4 ][ 2 ].  */
	int aa[][2] = { { 66, 45 },
				    { 33, 18 },
				    { 12, 84 },
				    { 22, 44 } };

	/*  Declaration of array a[8].  */
	int a[8];

	printf( HEADER );
	
	/*  Converting two-dimensional array to one-dimensional array.  */
	arrayToArray( aa, r, c, a );     
	
	for(i = 1; i < SIZE; ++i)
	{
		printf("  (( i = %d )  <  ( SIZE = %d )).\n\n", i, SIZE);
				
		for(j = (SIZE-1); j >= i; --j)
		{
			printf("  (( j = %d )  >=  ( i = %d )).\n\n", j, i);
						
			/* Compare */
			printf("  If (( a[ %d ] = %d )  >  ( a[ %d ] =  %d )); then swap!\n\n", (j-1), a[j-1], j, a[j]);
			if(a[ j - 1 ] > a[ j ])
			{
				/* Swap */
				temp = a[ j - 1];
				a[ j - 1] = a[ j ];
				a[ j ] = temp;
				swap++;

				for(s = 0; s < SIZE; s++) printf("  %d", a[s]);
				printf("\n\n");

				printf("  Total Swaps: %d\n", swap);
				printf("\n  ********************************\n\n");
				printf( "  Press any key to continue:  ");
				nxt = getchar();
				printf("\n\n");
		    }
		}
	}
	
	/*  Display sorted array.  */
	printf("\n  SORTED LINEAR ONE-DIMENSIONAL ARRAY:\n\n  ");
    for(s = 0; s < SIZE; s++) printf("%d  ", a[s]);

	printf("\n\n");
	printf( "  Press any key to continue:  ");
				
	nxt = getchar();
	printf("\n\n");

	arrayConversion( aa, r, c, a );

	printf("\n\n");
	printf( "  Press any key to EXIT:  ");
				
	nxt = getchar();

	return 0;
}

/*  Converting two-dimensional array to one-dimensional array.  */
/*  rr rows, cc columns  */
void arrayToArray( int bb[][2], int rr, int cc, int a[8] )   
{
	int i = 0;
	int j = 0;
	int k = 0;
	int l = 0;
	int u = 0;

	//int aaa[8];
	
	printf( "\n\n  UNSORTED TWO-DIMENSIONAL ARRAY:.\n\n" );
	for( i=0; i<rr; i++ )
	{
		printf( "     %5d  %5d \n", bb[i][0], bb[i][1] );
	}

	for (j = 0; j < rr; j++)
	{
		for (k = 0; k < cc; k++)
		{
		a[l] = bb[j][k];
		l++;
		}
	}

	/*  Display unsorted array.  */
	printf("\n\n  UNSORTED LINEAR ONE-DIMENSIONAL ARRAY:\n\n  ");
	for(u = 0; u < SIZE; u++) printf("%d  ", a[u]);
	printf("\n   0   1   2   3   4   5   6   7 <= Index\n");
	printf("\n\n  ********************************\n\n");

	return;
}

/*  Converting one-dimensional array to two-dimensional array.  */
/*  rr rows, cc columns  */
void arrayConversion( int aa[][2], int rr, int cc, int a[8] )   
{
	int i = 0;
	int j = 0;
	int k = 0;
	int l = 0;
	int u = 0;

	for (j = 0; j < rr; j++)
	{
		for (k = 0; k < cc; k++)
		{
		aa[j][k] = a[l];
		l++;
		}
	}

	/*  Display sorted array.  */
	printf("\n\n  SORTED TWO-DIMENSIONAL ARRAY:\n\n");
	for( i=0; i<rr; i++ )
	{
		printf( "     %5d  %5d \n", aa[i][0], aa[i][1] );
	}
	printf("\n\n  ********************************\n\n");

	return;
}



V. REFERENCES

The C Programming Language by Brian Kernighan and Dennis Ritchie (Englewood Cliffs, N.J.: Prentice-Hall, 1978).

The C Programming Language Second Edition by Brian Kernighan and Dennis Ritchie (Upper Saddle River, N.J.: Prentice-Hall PTR, 1988).


Is This A Good Question/Topic? 3
  • +

Replies To: BUBBLE SORT

#2 harris2107  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 17-August 10

Posted 17 August 2010 - 12:36 PM

thnks nice post.....
i got it
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1