What is the solution to this problem? Thanks! What is the solution to this probl

Question

What is the solution to this problem? Thanks!

What is the solution to this problem? 2. (10 points) You are asked to sort a set of numbers using a Max Priority Queue. The data will arrive relatively slowly, but you should he prepared to provide the sorted numbers very quickly when they are requested. A. Given an array-based implementation of the Max Priority Queue, should you choose to have the internal implementation keep the elements sorted or unsorted? Why? B. What is the big-0 running time to add ''N'' numbers to this queue? C. What is the big-O running time to remove N numbers from this queue? D. What is the overall big-O running time for the sorting procedure using this method? E. What sorting algorithm is this method closest to? (circle one)

Explanation / Answer

A)

The internal implementation of queue is:

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

#define MAX 5

void insert_by_priority(int);
void delete_by_priority(int);
void create();
void check(int);
void display_pqueue();

int pri_que[MAX];
int front, rear;

void main()
{
int n, ch;

printf(" 1 - Insert an element into queue");
printf(" 2 - Delete an element from queue");
printf(" 3 - Display queue elements");
printf(" 4 - Exit");

create();

while (1)
{
printf(" Enter your choice : ");
scanf("%d", &ch);

switch (ch)
{
case 1:
printf(" Enter value to be inserted : ");
scanf("%d",&n);
insert_by_priority(n);
break;
case 2:
printf(" Enter value to delete : ");
scanf("%d",&n);
delete_by_priority(n);
break;
case 3:
display_pqueue();
break;
case 4:
exit(0);
default:
printf(" Choice is incorrect, Enter a correct choice");
}
}
}

/* Function to create an empty priority queue */
void create()
{
front = rear = -1;
}

/* Function to insert value into priority queue */
void insert_by_priority(int data)
{
if (rear >= MAX - 1)
{
printf(" Queue overflow no more elements can be inserted");
return;
}
if ((front == -1) && (rear == -1))
{
front++;
rear++;
pri_que[rear] = data;
return;
}
else
check(data);
rear++;
}

/* Function to check priority and place element */
void check(int data)
{
int i,j;

for (i = 0; i <= rear; i++)
{
if (data >= pri_que[i])
{
for (j = rear + 1; j > i; j--)
{
pri_que[j] = pri_que[j - 1];
}
pri_que[i] = data;
return;
}
}
pri_que[i] = data;
}

/* Function to delete an element from queue */
void delete_by_priority(int data)
{
int i;

if ((front==-1) && (rear==-1))
{
printf(" Queue is empty no elements to delete");
return;
}

for (i = 0; i <= rear; i++)
{
if (data == pri_que[i])
{
for (; i < rear; i++)
{
pri_que[i] = pri_que[i + 1];
}

pri_que[i] = -99;
rear--;

if (rear == -1)
front = -1;
return;
}
}
printf(" %d not found in queue to delete", data);
}

/* Function to display queue elements */
void display_pqueue()
{
if ((front == -1) && (rear == -1))
{
printf(" Queue is empty");
return;
}

for (; front <= rear; front++)
{
printf(" %d ", pri_que[front]);
}

front = 0;
}

There is no need to enter elements in sorted or unsorted manner.A Queue is a representation FIFO(First In first Out) which accept data in any manner i.e. sorted or unsorted

B)

If f(x) = x, we can see that if g(x) = x, then the Big-O condition holds. Thus O(n) = O(n). This rule is general for the various asymptotic notations.

C)
Big O running time to remove N numbers from the queue is O(2n)=O(n)

D)

There are two for loops, that each iterate n times, so the running time is clearly O(2n), where 2 is a constant variable.so,
Big O running time to sorting procedure is O(2n)=O(n).

E)
Insertion Sort

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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