CS101 - LAB ACTIVITY 11

This week's lab deals with sorting, which is an interesting problem on its own but more importantly, it is an essential part of MP2. 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

Learn how to use the qsort function
Learn how to write a comparison auxiliary function for qsort.

References

Lecture 19 and 20 on sorting
Manual page for standard library string functions
qsort manual page

Part 1: 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 following program: sort
To run this program:

Open a Terminal window (Go to Applications, Utilities, Terminal
Type: cd directory_where_you_saved_sort
For example, if you saved the file to Desktop, type: cd Desktop
Make the program executable. Type:
chmod u+x sort
Type: ./sort

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)

The name of the array to be sorted. In our program in lab11, nums is the name of the array.
The number of elements in the array. In our case, the number of elements in the array is 10 but we will use the constant ARRAY_SIZE which is defined as having the value 10.
The size, in bytes, of each element in the array. Since each element of the array is an integer we will use sizeof(int) (which equals 4 on our lab machines since an integer takes 4 bytes of memory). If our array was of datatype double then we would have used sizeof(double) which is 8 on our lab machine since a variable of datatype double takes 8 bytes of memory.
A function name. You will have to write the auxiliary functions named compAsc and compDesc. The compAsc or compDesc function each has two parameters, both are pointers to an array element. The function compAsc should return a positive integer (say 1) if the thing that the first parameter points to(the element of the array) is greater than the the thing the second pointer points to (another element of the array). The function compAsc should return a negative integer if the thing the first pointer points to is smaller than the thing the second pointer points to. And compAsc should return 0 if they're equal.

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:

print the following menu (copy and paste into a printf)
   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:

read the value the user types (either 1 or 2) into an integer variable named choice declared in the menu function
return 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:

Generate an array of random integers
Call the menu function, assigning the value it returns to an integer variable named response
Print the array (unsorted)
Use a switch statement on the variable named response declared in main. In case 1: call the qsort function using compAsc. In case 2: call the qsort function using compDesc
Print the sorted array

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

We will use eclipse to do this lab.

Use eclipse to create one new Managed C Project called "lab11" as your starting point.
Use eclipse to create lab11.c

You need to include some header files and define some constants. The beginning of your program should look like this:
```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARRAY_SIZE 10
#define MAX_NUM 20
```

Write code for the menu function (see pseudo-code above).

Write code for the compAsc and compDesc functions (see pseudo-code above).

Now we shall give some details on how to write our main function. Within the main function, create an integer array, and call it nums. It should have ARRAY_SIZE elements.

Next write a for loop to initialize every element of nums to a random number from 1 to MAX_NUM. Use i as your loop counter (don't forget to declare it!). Your loop should look like this:

srand(time(NULL));
    
/* Replace this comment with the beginning of your loop... */
    	nums[i] = (rand() % MAX_NUM) + 1;
	
/* Replace this comment with the end of your loop... */

Next, write another loop to print all the numbers. The numbers should be separated by a space. After the loop, print a "\n\n" to make a blank line.

Now it's time to check your program up to this point. Save, compile, and run your program. When you run your program, you should see a list of 10 positive integers that looks something like this: (the values won't be the same since we are generating the values randomly)
```
  11 15 8 4 17 16 13 10 9 10
```

If everything looks good (ask your lab TA if you can't fix any compile or run-time errors), we next add the switch statement to main (see pseudo-code above)

Finally, you should write a loop to have your program print out the sorted values. You can copy and paste the loop you have written previously.
5. Run the code
Compile and run the program, making sure it works properly. 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
```
Show the sort program to your TA and get his/her signature on the answer sheet.

Part 2: 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.
- Use eclipse to create one new Managed C Project called "sortwords" as your starting point.
- Use eclipse to create sortwords.c
- Copy the content of downloaded sortwords.c into the sortwords.c you created in eclipse.
- Fill in the blanks.
- Open a Terminal window
- Type: cd "full_path_for_the_project_directory" For example, if your sortwords project directory is workspace/sortwords, you can type: cd workspace/sortwords
- Download the data file: hoax.txt to the sorwords project directory
- Compile the program
- In the Terminal, type: sortwords < hoax.txt
That's all folks! Hand in your answer sheet to your TA.