Assignment 8

Suppose that we have a linked list of points in the X-Y plane. We want to sort the list simultaneously with respect the X-coordinates and with respect to the Y-coordinates. To achieve this goal, we maintain two pointers in each node. One set of these pointers is used to sort the list with respect to the X-values, the other with respect to the Y-values. The following figure demonstrates this concept.

In view of this representation, we declare some relevant data types as follows.

   typedef struct _node {
      int x;
      int y;
      struct _node *nextx;
      struct _node *nexty;
   } node;

   typedef node *list;

First, generate a random list of points with integer coordinates. At this point, you do not worry about sorting of the elements, but insert every new element at the end of the new list with respect to both the nextx and nexty pointers. A function to do that is given below.

   #include <stdio.h>
   #include <stdlib.h>
   #include <time.h>

   list genRandList ( int n )
   {
      list L;
      node *p, *q;
      int i;

      /* Create dummy header */
      L = (list)malloc(sizeof(node));
      L -> x = L -> y = 0;
      L -> nextx = L -> nexty = NULL;

      /* Insert random elements at the end of the list */
      srand((unsigned int)time(NULL));
      p = L;
      for (i=0; i<n; ++i) {
         q = (node *)malloc(sizeof(node));
         q -> x = 1000 + rand() % 9000;
         q -> y = 1000 + rand() % 9000;
         q -> nextx = q -> nexty = NULL;
         p -> nextx = p -> nexty = q;
         p = q;
      }

      return L;
   }

Write a function with the following prototype:

   void printList ( list L, int flag );

This function prints the list headed by the pointer L. Now, each node has two pointers. The flag indicates whether the list is to be traversed along the nextx pointers, or along the nexty pointers.

Write two functions with the following prototypes:

   void bubbleSortX ( list L );
   void bubbleSortY ( list L );

The first function is meant for bubble-sorting the list headed by L with respect to the x-values, and the second with respect to the y-values. You are not supposed to separate the x and y coordinates of a point. This means that a swap in only the x-values or only the y-values in two nodes is not permitted. If you swap both the x and y values together, you disturb the order in the values with respect to which you are not sorting. So you must adjust the relevant pointers in the nodes in order to effect two independent sorting of the same list.

Your functions should be compatible with the following main() function.

   #define N 100
   #define WRT_X 0
   #define WRT_Y 1

   int main ()
   {
      list L;

      L = genRandList(N);
      printf("\nInitial list with respect to x pointers:\n"); printList(L,WRT_X);
      printf("\nInitial list with respect to y pointers:\n"); printList(L,WRT_Y);
      bubbleSortX(L);
      bubbleSortY(L);
      printf("\nFinal list with respect to x pointers:\n"); printList(L,WRT_X);
      printf("\nFinal list with respect to y pointers:\n"); printList(L,WRT_Y);
      exit(0);
   }

Report the output of your program for a random list of 100 points.

Lab Home

Submission Site

My Home