REVISED: Sunday, March 15, 2015
CONTENTS:
• I. C BUBBLE SORT INTRODUCTION
• II. C BUBBLE SORT
• III. C BUBBLE SORT EXAMPLE PROGRAM ANALYSIS
• IV. C BUBBLE SORT EXAMPLE PROGRAM SOURCE CODE
• V. C BUBBLE SORT REFERENCES
YOU WILL LEARN:
1. C bubble sort.
2. How to write a C bubble sort program.
I. C BUBBLE SORT INTRODUCTION
Welcome to the “C Bubble Sort Tutorial.”
II. C 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. C BUBBLE SORT 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?
..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. C BUBBLE SORT EXAMPLE PROGRAM SOURCE CODE
/****************************
C BUBBLE SORT
****************************/
#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" \
" \n" \
" \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;
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. C BUBBLE SORT 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).
YOU HAVE LEARNED:
1. C bubble sort.
2. How to write a C bubble sort program.
Elcric Otto Circle
-->
-->
How to Link to My Home Page
It will appear on your website as:"Link to ELCRIC OTTO CIRCLE's Home Page"
No comments:
Post a Comment