Massachusetts Institute of Technology
Department of Electrical Engineering and Computer Science
6.087: Practical Programming in C
IAP 2010
Problem Set 4
Pointers. Arrays. Strings. Searching and sorting algorithms.
Out: Friday, January 15, 2010. Due: Tuesday, January 19, 2010.
Problem 4.1
Consider the insertion sort algorithm described in Lecture 5 In this problem, you will re-implement
the algorithm using pointers and pointer arithmetic.
(a) The function shift element() takes as input the index of an array element that has been
determined to be out of order. The function shifts the element towards the front of the array,
repeatedly swapping the preceding element until the out-of-order element is in the proper
location. The implementation using array indexing is provided below for your reference:
/∗ move p r e v i o u s e l e m e n t s down u n t i l
i n s e r t i o n p o i n t r e a c h e d ∗/
void s h i f t e l e m e n t ( unsigned i n t i ) {
int i v a l u e ;
/∗ guard a g a i n s t g o i n g o u t s i d e a r r a y ∗/
f o r ( i v a l u e = a r r [ i ] ; i && a r r [ i −1] > i v a l u e ; i −−)
a r r [ i ] = a r r [ i − 1 ] ; /∗ move e l e m e n t down ∗/
a r r [ i ] = i v a l u e ; /∗ i n s e r t e l e m e n t ∗/
}
Re-implement this function using pointers and pointer arithmetic instead of array indexing.
/∗ i n t ∗ pElement − p o i n t e r t o t h e e l e m e n t
i n a r r ( typ e i n t [ ] ) t h a t i s out−o f −p l a c e ∗/
void s h i f t e l e m e n t ( i n t ∗ pElement ) {
/∗ i n s e r t code h e r e ∗/
}
(b) The function insertion sort() contains the main loop of the algorithm. It iterates through
elements of the array, from the beginning, until it reaches an element that is out-of-order. It
calls shift element() to shift the offending element to its proper location earlier in the array
and resumes iterating until the end is reached. The code from lecture is provided below:
/∗ i t e r a t e u n t i l out−o f −o r d e r e l e m e n t found ;
s h i f t t h e element , and c o n t i n u e i t e r a t i n g ∗/
void i n s e r t i o n s o r t ( void ) {
unsigned i nt i , l e n = a r r a y l e n g t h ( a r r ) ;
f o r ( i = 1 ; i < l e n ; i ++)
i f ( a r r [ i ] < a r r [ i −1])
shift element ( i );
}
Re-implement this function using pointers and pointer arithmetic instead of array indexing.
Use the shift element() function you implemented in part (a).
1
Department of Electrical Engineering and Computer Science
6.087: Practical Programming in C
IAP 2010
Problem Set 4
Pointers. Arrays. Strings. Searching and sorting algorithms.
Out: Friday, January 15, 2010. Due: Tuesday, January 19, 2010.
Problem 4.1
Consider the insertion sort algorithm described in Lecture 5 In this problem, you will re-implement
the algorithm using pointers and pointer arithmetic.
(a) The function shift element() takes as input the index of an array element that has been
determined to be out of order. The function shifts the element towards the front of the array,
repeatedly swapping the preceding element until the out-of-order element is in the proper
location. The implementation using array indexing is provided below for your reference:
/∗ move p r e v i o u s e l e m e n t s down u n t i l
i n s e r t i o n p o i n t r e a c h e d ∗/
void s h i f t e l e m e n t ( unsigned i n t i ) {
int i v a l u e ;
/∗ guard a g a i n s t g o i n g o u t s i d e a r r a y ∗/
f o r ( i v a l u e = a r r [ i ] ; i && a r r [ i −1] > i v a l u e ; i −−)
a r r [ i ] = a r r [ i − 1 ] ; /∗ move e l e m e n t down ∗/
a r r [ i ] = i v a l u e ; /∗ i n s e r t e l e m e n t ∗/
}
Re-implement this function using pointers and pointer arithmetic instead of array indexing.
/∗ i n t ∗ pElement − p o i n t e r t o t h e e l e m e n t
i n a r r ( typ e i n t [ ] ) t h a t i s out−o f −p l a c e ∗/
void s h i f t e l e m e n t ( i n t ∗ pElement ) {
/∗ i n s e r t code h e r e ∗/
}
(b) The function insertion sort() contains the main loop of the algorithm. It iterates through
elements of the array, from the beginning, until it reaches an element that is out-of-order. It
calls shift element() to shift the offending element to its proper location earlier in the array
and resumes iterating until the end is reached. The code from lecture is provided below:
/∗ i t e r a t e u n t i l out−o f −o r d e r e l e m e n t found ;
s h i f t t h e element , and c o n t i n u e i t e r a t i n g ∗/
void i n s e r t i o n s o r t ( void ) {
unsigned i nt i , l e n = a r r a y l e n g t h ( a r r ) ;
f o r ( i = 1 ; i < l e n ; i ++)
i f ( a r r [ i ] < a r r [ i −1])
shift element ( i );
}
Re-implement this function using pointers and pointer arithmetic instead of array indexing.
Use the shift element() function you implemented in part (a).
1
