VS 2010 C++ CST 280 Week 13 a and B - 57951

Solution Posted by
jordanblink

jordanblink

Rating : (19)A+
Solution Detail
Price: $10.00
Request Description

CST 280 In-Class Practice – Week 13

Manually determine the configuration of the priority queue (stored as a heap) created

by the following operations. Trace the following logic and define the output:

enqueue(7);

enqueue(17);

enqueue(2);

enqueue(5);

enqueue(22);

enqueue(19);

enqueue(6);

enqueue(11);

enqueue(13);

write the queue contents

dequeue and write front item

enqueue(15);

enqueue(8);

dequeue and write front item

dequeue and write front item

enqueue(24);

enqueue(14);

write the queue contents

Part 2

Then, verify the output by implementing the algorithm by rewriting the priority

queue demonstration program discussed in class. Files needed:

testPQueue.cpp pqType.h heap.cpp

Deliverables

• This cover sheet (with your names on it)

• Driver source code and output for verification program exectution.

 

 

CST 280 In-Class Practice – Week 13

Use this page as a worksheet to sketch the progression of the elements up to the first

split for the QuickSort algorithm. Use the middle array element as the split value:

15 34 99 42 11 41 66 23 55 93 48

Next, access the file quickSort.cpp from the course web page. Tailor the program

by entering the array values above in place of the integer values used for an in-class

demonstration. Be sure to adjust the index range to match the size of this array.

Remember that the parameters to the QuickSort algorithm are starting and ending index

values, not the size of the array.

Next, insert code to demonstrate the state of the array after the first split. This should

verify what you did by hand above. Insert the following code at various points within

the partition function to “see” the array at various stages of processing:

for (int i = start; i <= end; i++) // <== ADD

cout << set[i] << ' ';

cout << endl;

Insert the code at these positions:

int partition(int set[], int start, int end)

{

int pivotValue, pivotIndex, mid;

mid = (start + end) / 2;

swap(set[start], set[mid]);

pivotIndex = start;

pivotValue = set[start];

ç? HERE

for (int scan = start + 1; scan <= end; scan++)

{

if (set[scan] < pivotValue)

{

pivotIndex++;

swap(set[pivotIndex], set[scan]);

}

ç? HERE

}

swap(set[start], set[pivotIndex]);

ç? HERE

return pivotIndex;

}

Finally, identify the line that matches what you concluded above.

Deliverables:

Deliver the following for this assignment:

• This work sheet with a sketch of the array first split

• Program source code with required change

• Program output demonstrating array configuration after first split

Solution Description

VS 2010 C++ CST

Attachments
CPPCST280W13.zip
CPPCST280W13.zi...
CST 280 W13 B.docx
CST 280 W13 B.d...
CST 280w13a.docx
CST 280w13a.doc...