Question

Write pseudocode to solve the following problem: You are given an array A[1 . . . n] whose each element is a point of the plane (x, y). You need to sort the array so that points with lower x-coordinate come earlier, but among points with the same x-coordinate, the ones with larger y-coordinate come earlier. So, for example if the array contains, (1, 2),(1, 4),(7, 10),(11, 3),(14, 1),(7, 2) The output in this case should be: (1, 4),(1, 2),(7, 10),(7, 2),(11, 3),(14, 1). Analyze the running time of your algorithm as a function of n.

Answer 1

Answer:

Answer explained below

Explanation:

void bubbleSort(int X[], int Y[], int n)

{

   int i, j;

   for (i = 0; i < n-1; i++)      

     

   // Last i elements are already in place

   for (j = 0; j < n-i-1; j++)

       if (X[j] > X[j+1])

{

swap(X[j],X[j+1])

swap(Y[j],Y[j+1]);

}

       if (X[j] == X[j+1]&&Y[j]<Y[j+1])

{

swap(X[j],X[j+1])

swap(Y[j],Y[j+1]);

}

}

Since the above algorithm contains 2 nested loops over n.

So, it is O(n^2)