Sorting problem: We are given a sequence of numbers x_1, x_2,..., x_n. We scan t

Question

Sorting problem: We are given a sequence of numbers x_1, x_2,..., x_n. We scan these numbers from left to right, and put x_i to left of x_i if x_i is smaller than x_i = 1. In other words, we continuously move x_i to the left until the numbers to its left are all smaller than or equal to it. Design an algorithm to resolve this sorting problem. Please analyze the time complexity of your above designed algorithm, in terms of both the best case and worst case complexities. Rank finding problem: In the 2-dimension space, we shall say that a point A = (a_1, a_2) dominates a point B = (b_1, b_2) if and only if a_1 > b_1 and a_2 > b_2. For the points in Figure 1, we have the following relation: B, C and D dominates A. D dominates A, B and C Figure 1: A case of showing the dominance relation Given a set of n points, the rank of a point X is the number of points dominated by X. Design algorithm to find the rank of every point.

Explanation / Answer

1. Answer for first problem is below i.e bubble sort..

#include <stdio.h>
#define MAXSIZE 10

void main()
{
int array[MAXSIZE];
int i, j, num, temp;

printf("Enter the value of num ");
scanf("%d", &num);
printf("Enter the elements one by one ");
for (i = 0; i < num; i++)
{
scanf("%d", &array[i]);
}
printf("Input array is ");
for (i = 0; i < num; i++)
{
printf("%d ", array[i]);
}
/* Bubble sorting begins */
for (i = 0; i < num; i++)
{
for (j = 0; j < (num - i - 1); j++)
{
if (array[j] > array[j + 1])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
printf("Sorted array is... ");
for (i = 0; i < num; i++)
{
printf("%d ", array[i]);
}
}

2. Time Complexities for above problem is below:

Best: O(n), Worst:O(N^2)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.