Introduction to Computing – B142L
B142L Computing practical – Introduction to algorithms with insertion and bubble sort
Academic year
2009/10
Learning outcomes
- Practice using pseudo code and D structures to document program design.
- Practice implementation of algorithms to sort basic data types.
Typical problem solving steps:
- Identify and understand the problem
- Ask clarification questions
- Confirm assumptions
- Confirm the range of acceptable inputs
- Confirm the output requirements
- Document possible error conditions
- Identify possible solutions
- Sources of possible solutions:
- Prior knowledge and experience
- Experimentation
- Research
- Identify and describe each possible solutions
- There are 2 types of solutions:
- Algorithmic solutions use a series of steps that generally occur in the same order.
- Heuristic solutions require a series of steps that do not always occur in the same order.
- Select best or appropriate solution from alternatives
- Identify the key reason(s) for selecting a particular solution
- Implement the selected solution
- Use and evaluate the solution
- Select suitable inputs for testing the solution
- Be prepared to adjust the solution based on test results
- Be prepared to use a different solution if the test results are not satisfactory
An algorithm is a list of steps for solving a problem which is suited for computer implementation. This includes algorithmic and heuristic solutions.
- A solution is a list of all the steps required to solve a problem.
- A result is one output or answer produced by using the steps in the solution.
- A program is the source code which implements the steps in the solution.
Exercise 1: Examples of algorithms
Microsoft Excel macros are excellent examples of algorithms that are widely used by many people.
What are other examples of algorithms that are commonly used on a daily basis?
Exercise 2: Practice with numeric arrays
Write a C program that uses an array to store up to
15 input floating point numbers. The program should:
- Display to output each number received as input
- Stop if an input number is negative
- Stop after 15 input numbers have been received
#include <stdio.h>
int main
( void )
{
float numbers
[ 15 ];
int counter;
for ( counter =
0; counter <
15; counter++
)
{
scanf
( "%f", &
( numbers
[ counter
] ) );
if ( numbers
[ counter
] <
0 ) break;
else printf( "%.2f ", numbers
[ counter
] );
}
}
Exercise 3: Practice with character arrays
Write a C program that accepts a text string input of up to
64 characters. The program should:
- Display to output each character received as input
- Stop if an input character is not alphanumeric
- Stop after 64 input characters have been received
#include <stdio.h>
#include <ctype.h>
int main
( void )
{
char text
[ 65 ];
int counter;
scanf
( "%64c", text
);
for ( counter =
0; counter <
64; counter++
)
{
if ( isalnum
( text
[ counter
] ) ) printf( "%c", text
[ counter
] );
else break;
}
printf( " %d", counter
);
}
Insertion sort algorithm
Read the description of the algorithm on Wikipedia:
Additionally, the following images and animation from Wikipedia may be useful:
Insertion sort program
The following program implements insertion sorting for a fixed array of numbers.
#include <stdio.h>
#define QUANTITY 10
int main
( void )
{
int numbers
[ QUANTITY
] =
{ 4,
7,
1,
94,
23,
56,
81,
12,
37,
46 };
int outside, inside, display, temp;
for ( outside =
1; outside < QUANTITY; outside++
)
{
for ( inside = outside; inside >
0; inside--
)
{
if ( numbers
[ inside
] < numbers
[ inside -
1 ] )
{
temp = numbers
[ inside
];
numbers
[ inside
] = numbers
[ inside -
1 ];
numbers
[ inside -
1 ] = temp;
}
else
break;
}
for ( display =
0; display < QUANTITY; display++
)
printf( "%d ", numbers
[ display
] );
printf( "\n" );
}
}
Exercise 4: Insertion sort program
Write a C program that uses an array to store up to
10 input integer numbers. The program should:
- Use insertion sort algorithm to sort the numbers in ascending order.
- Display the sorted output.
#include <stdio.h>
#define QUANTITY 15
int main
( void )
{
int numbers
[ QUANTITY
];
int outside, inside, counter, temp;
/* Obtain input numbers */
for ( counter =
0; counter < QUANTITY; counter++
)
scanf
( "%d", &
( numbers
[ counter
] ) );
/* Sort numbers */
for ( outside =
1; outside < QUANTITY; outside++
)
{
for ( inside = outside; inside >
0; inside--
)
{
if ( numbers
[ inside
] < numbers
[ inside -
1 ] )
{
temp = numbers
[ inside
];
numbers
[ inside
] = numbers
[ inside -
1 ];
numbers
[ inside -
1 ] = temp;
}
else
break;
}
}
/* Display sorted numbers */
for ( counter =
0; counter < QUANTITY; counter++
)
printf( "%d ", numbers
[ counter
] );
}
Exercise 5: Insertion sort program using characters
Write a C program that uses an array to store up to
20 input characters. The program should:
- Use insertion sort algorithm to sort the characters in descending order.
- Display the sorted output.
#include <stdio.h>
#define QUANTITY 20
int main
( void )
{
char text
[ QUANTITY +
1 ];
int outside, inside, counter;
char temp;
/* Obtain input characters */
scanf
( "%20c", text
);
/* Sort characters */
for ( outside =
1;
( outside < QUANTITY
) &&
( outside < strlen
( text
) ); outside++
)
{
for ( inside = outside; inside >
0; inside--
)
{
if ( text
[ inside
] > text
[ inside -
1 ] )
{
temp = text
[ inside
];
text
[ inside
] = text
[ inside -
1 ];
text
[ inside -
1 ] = temp;
}
else
break;
}
}
/* Display sorted characters */
printf( "%s", text
);
}
Bubble sort algorithm
Read the description of the algorithm on Wikipedia:
Bubble sort program
The following program implements bubble sort for a fixed array of numbers.
#include <stdio.h>
#define QUANTITY 10
int main
( void )
{
int numbers
[ QUANTITY
] =
{ 4,
7,
1,
94,
23,
56,
81,
12,
37,
46 };
int outside, inside, display, temp, sorted;
sorted =
0;
for ( outside =
1;
( outside < QUANTITY
) &&
( sorted ==
0 ); outside++
)
{
sorted =
1;
for ( inside =
0; inside <
( QUANTITY - outside
); inside++
)
{
if ( numbers
[ inside
] > numbers
[ inside +
1 ] )
{
temp = numbers
[ inside
];
numbers
[ inside
] = numbers
[ inside +
1 ];
numbers
[ inside +
1 ] = temp;
sorted =
0;
}
}
for ( display =
0; display < QUANTITY; display++
)
printf( "%d ", numbers
[ display
] );
printf( "\n" );
}
}
Exercise 6: Bubble sort program
Write a C program that uses an array to store up to
10 input integer numbers. The program should:
- Use bubble sort algorithm to sort the numbers in descending order.
- Display the sorted output.
#include <stdio.h>
#define QUANTITY 10
int main
( void )
{
int numbers
[ QUANTITY
];
int outside, inside, counter, temp, sorted;
/* Obtain input numbers */
for ( counter =
0; counter < QUANTITY; counter++
)
scanf
( "%d", &
( numbers
[ counter
] ) );
/* Sort numbers */
sorted =
0;
for ( outside =
1;
( outside < QUANTITY
) &&
( sorted ==
0 ); outside++
)
{
sorted =
1;
for ( inside =
0; inside <
( QUANTITY - outside
); inside++
)
{
if ( numbers
[ inside
] < numbers
[ inside +
1 ] )
{
temp = numbers
[ inside
];
numbers
[ inside
] = numbers
[ inside +
1 ];
numbers
[ inside +
1 ] = temp;
sorted =
0;
}
}
}
/* Display sorted numbers */
for ( counter =
0; counter < QUANTITY; counter++
)
printf( "%d ", numbers
[ counter
] );
}
Exercise 7: Bubble sort program using characters
Write a C program that uses an array to store up to
20 input characters. The program should:
- Use bubble sort algorithm to sort the characters in ascending order.
- Display the sorted output.
#include <stdio.h>
#define QUANTITY 20
int main
( void )
{
char text
[ QUANTITY +
1 ];
int outside, inside, sorted;
char temp;
/* Obtain input characters */
scanf
( "%20c", text
);
/* Sort characters */
sorted =
0;
for ( outside =
1;
( outside < QUANTITY
) &&
( sorted ==
0 ); outside++
)
{
sorted =
1;
for ( inside =
0; inside <
( QUANTITY - outside
); inside++
)
{
if ( text
[ inside
] > text
[ inside +
1 ] )
{
temp = text
[ inside
];
text
[ inside
] = text
[ inside +
1 ];
text
[ inside +
1 ] = temp;
sorted =
0;
}
}
}
/* Display sorted characters */
printf( "%s", text
);
}
