Problem 3. (25 points) Describe and analyze an algorithm that takes an unsorted

Question

Problem 3. (25 points) Describe and analyze an algorithm that takes an unsorted array A of n integers (in an unbounded range) and an integer k, and divides A into k equal-sized groups, such that the integers in the first group are lower than the integers in the second group, and the integers in the second group are lower than the integers in the third group, and so on. For instance if A {4.12.3.8.7.9. 10. 20.5) and k-3, one possible solution would be Ai = {4.3.5), A2-18, 7,9), A3-{12.10, 20). Sorting A in 0(n log n)-time would solve the problem, but we want a faster solution. The running time of your solution should be bounded by O(nk). For simplicity, you can assume that is n a multiple of k, and that all the elements are distict. Note: k is an input to the algorithm, not a fixed constant.

Explanation / Answer

Dear student,

Sorting is one of the solution to the problem.

Another solution I am providing you below:

The algorithm using min heap is defined below:

Time complexity: O(k + (n-k)Logk) without sorted output for extracting each K elements of given array

so final time complexity will be O(k + (n-k)Logk) * ((n-k)/k) which is almost equivalent to O(nk).

Given below is helpful function to built code.

void swap(float *x, float *y) {
*x= *x + *y;
*y = *x - *y;
*x = *x - *y;
}

void minHeapify(float a[], int size, int i) {
int l = 2* i ;
int r = 2* i + 1;
int smallest = i;
if (l < size && a[l] < a[smallest])
smallest = l;
if (r < size && a[r] < a[smallest])
smallest = r;
if (smallest != i) {
swap(&a[i], &a[smallest]);
minHeapify(a, size, smallest);
}

}

void buildMinimumHeap(float a[], int size) {
int i;
for (i = size / 2; i >= 0; --i)
minHeapify(a, size, i);

}

int kthLargest(float a[], int size, int k) {
int i;

float minHeap[k];  

for (i = 0; i < k; i++)
minHeap[i] = a[i];
buildMinimumHeap(minHeap, k);
for (i = k; i < size; i++) {
if (a[i] > minHeap[0]) {
minHeap[0] = a[i];
minHeapify(minHeap, k, 0);
}
}
return minHeap[0];
}

void find_k_max(float a[], int size, int k, int indexs[]) {
float kith = kthLargest(a, size, k);
int j = 0;
for (i=0; i < size; ++i)
if (a[i] >= kith)
indexs[j++] = i;
}

Thanks !!!

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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