CS101 - LAB ACTIVITY 11

This week's lab deals with sorting. In the first part, you will use the standard library function qsort to sort an array of integers. In the second part, we will sort strings instead of integers.

Objectives

References

Part 1: Prelab

The following exercises are about pointers in C and should help prepare you for future lab activities MP2 and the Final Exam.

In this prelab, you'll demonstrate your knowledge regarding,





  1. Write the output when the following program executes. 

     #include <stdio.h>
  
 int i = -12; /* global variable */
 
 int function2(int x) 
  {
     int i = -10; /* another variable named i  */
     
     printf(" %i \n", i);
     return x * i;
 }
 
 void main(void) 
  {
     printf(" %i \n", function2(i));
     printf(" %i\n", i);
   }

  2. Write the output of the following code. You may have to compile and run this program.

    #include <stdio.h>
void main(void)
{
        int x;
        int * ptr;  /* ptr is a "pointer" variable. Assign only computer memory addresses to ptr !!! */
        x = 20;
        
        printf("x is %i\n", x);
        
        ptr = &x;  /* ptr now points to x , &x means... address of x */
        *ptr = 50;  /* * operator (dereferencing operator), *ptr means ... the thing ptr points to (which is x in this example)*/ 
        printf("x is %i\n", x);
        
        -x;
        printf("*ptr = %i \n", *ptr);    /* so using *ptr is like using x */
        --(*ptr);    /* has same effect as --x */
        printf("x = %i\n",x); 
}

  3. Write the output when the following program executes. See lecture 19&20 slide #21.

     #include <stdio.h>
 
 void main(void) 
  {   
     char str[] = "crown";
     char * ptrA = "royal";   /* note that ptrA is a pointer, it won't hold data of type char, it holds addresses */
     char * ptrB = str;       /* the name of an array holds the address of the first byte of an array */
                              /* so an array name is a pointer (its value can't be changed however) */
     printf(" %s ", str);
     printf(" %s ", ptrA);   
     printf(" %s \n", ptrB);
     printf("%c %c \n", ptrA[2], *ptrB);  /* if the name of an array is a pointer conversely a pointer can be used */
                                          /* an array name */
 }

  4. Write the output of the following program. 

    #include <stdio.h>

void swap1(int a,int b) 
{
  int temp = b;
  b = a;
  a = temp;
}
void swap2(int *a,int *b) 
{
  int temp = *a;
  *a = *b;
  *b = temp;
}
void swap3(int * x) 
{
  int temp = x[0];
  x[0] = x[1];
  x[1] = temp;
}
void main(void) 
{
  int a = 5, b = 10;
  int c[2];
  printf("%i %i\n",a,b);
  swap1(a,b);
  printf("%i %i\n",a,b);
  swap2(&a,&b);
  printf("%i %i\n",a,b);
  c[0] = a - b; c[1] = b + a;
  
  /* 'c' is the name of an array therefore c is a constant pointer */
  /* see lecture 19&20 slide #18 */
  
  swap3(c);
  printf("%i %i\n",c[0],c[1]);
}

  5. Write the output of the following code. It might help to draw a picture of memory. Remember, if p2 is a pointer then p2[0] means *(p2 + 0).

    #include <stdio.h>
void main(void)
{
  int x[2]={2,1};
  int *p1, *p2;
  int a = 30, b = 10;
  printf("%i %i \n",x[0],x[1]);
  p1 = x;
  printf("%i %i \n",p1[0],p1[1]);
  p2 = &p1[1];
  printf("%i \n",p2[0]);
  *p1 = a * b;
  *p2 = b / a;
  printf("%i %i \n",p1[0],p1[1]);
  printf("%i \n",p2[0]);
}


Part 2: Using QuickSort

1. Requirements Specification (Problem Definition)

In this part, we're going to generate an array of 10 integers at random. First we display the list of 10 integers. Then we will ask the user if they want to have the integers sorted in ascending or descending order. We will use the function named qsort found in the standard library (#include <stdlib.h>) to sort integers.
To see a demo of the program you will download the file named sort(see instructions below).
To run this program:



2. Analysis---Refine, Generalize, Decompose the problem definition

Our program will have four functions: main , menu , compAsc , compDesc .


In main we will need to call the qsort function. qsort takes four parameters, in this particular order :

qsort(name of the array to be sorted, number of elements in the array, size in number of bytes of each element of the array, comparison function name)

3. Design---Develop Algorithm

You will need to code four functions: main, menu, compAsc and compDesc.

menu function
The menu function has no input arguments and it returns an integer. So its code looks like:
int menu(void)
{


}
Here is the algorithm for the menu function in pseudo-code:

Enter your choice:

compAsc function
We will give you the code for the compAsc function:
int compAsc( int * ptr1 , int * ptr2)
{
return *ptr1 - *ptr2 ;
}

compDesc function
The code for the compDesc function is almost identical to the code for the compAsc function except that it returns an integer value of the opposite sign. Copy and paste the code for the compAsc function and change its name to compDesc and make the necessary changes.




main function
Here is the algorithm for main in pseudo-code:

4. Implementation --- Write the "Program" (Code)



5. Run the program

At the Unix prompt type:
gcc lab11.c -o lab11
./lab11

Note: If you see any warnings about the fourth argument of qsort, you may safely ignore them.


For example, you may get something like the following as output from your program: 

  11 15 8 4 17 16 13 10 9 10

Enter your choice of sorting:
1) sort in ascending order (1 2 3 4)
2) sort in descending order (4 3 2 1)
Enter your choice: 1

   4 8 9 10 10 11 13 15 16 17



Answer question #1, and #2 on the answer sheet.



Part 3: Swapping Strings

Next, we're going to try sorting some strings instead of integers. To save you some effort, we provide you with an almost completed program to begin with.

Answer question #3, and #4 on the answer sheet.

That's all folks!