contestada

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-coordinates 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

Respuesta :

mateolara11

Answer:

1.

arrayIn = [(1,4), (1,2), (7,10), (7,2), (11,3), (14,1)]

arrayOut = [arrayIn[0]]

for i in range(1,len(arrayIn),1):

for j in range(len(arrayOut)):

if j == len(arrayOut)-1:

arrayOut.append(arrayIn[i])

elif arrayIn[i][0] < arrayOut[j][0]:

arrayOut.insert(j, arrayIn[i])

break

elif arrayIn[i][0] == arrayOut[j][0]:

if arrayIn[i][1] >= arrayOut[j][1]:

arrayOut.insert(j, arrayIn[i])

break

2.

Maximum running time = O(n^2)

Explanation:

  • On the first line, we create an array called arrayIn
  • On the second line we create an array called arrayOut containing the first element of arrayIn, arrayOut is going to contain the sorted array
  • On the third line, we create a for loop to iterate over the elements of arrayIn without taking the first element (is already on arrayOut)
  • On the fourth line we create a nested for loop to iterate over the elements of arrayOut, the general idea is to compare the elements of arrayIn with the sorted elements of arrayOut and organize the elements according to this comparison
  • On line number five and six we create an if statement to check if we are at the end of the arrayOut, the purpose of this statement is to add an element to the tail of arrayOut if no previous coincidences were found (Please see the others if statements to better understand this concept)
  • From line seven to nine we create an elif statement that checks if the X component of the arrayIn element that we are checking is smaller than the X component of the arrayOut element if so, we index the element in the corresponding position (lower x-coordinates come earlier) and finish the search for that element
  • On line ten we create an elif statement to checks if the X component of the arrayIn element that we are checking is equal to the X component of the arrayOut element, if so, other 'if' statement is checked (see next line)
  • From line eleven to thirteen we create an if statement that checks if the Y component of the arrayIn element that we are checking is greater or equal to the Y component of the arrayOut element, if so, we index the element in the corresponding position (larger y-coordinate come earlier) and finish the search for that element

Because we have a nested loop the worst-case time complexity will be something proportional to O(n^2)

Note: elif -> else if

Otras preguntas