program设计程序代做、代写C++编程语言、c++程序代做

日期：2021-07-04 03:35

F. Task(s)

1. Write a program to sort an array of size 10 using both Merge and Quick sort algorithms.

Make sure that both algorithms collaborate to sort one dimensional array, i.e. if merge sort

is applied on the first part of the array then Quick sort must be applied on the other part as

shown in the following figure:

Make sure to follow the following rules:

a. You are not allowed to apply each algorithm on the entire array.

b. If one algorithm applied for one part, then the other algorithm applied to the rest of the

array. For example mergeSort(arr,0,4) then quicksort(arr,5,n-1).

c. Make sure that your code works on any input.

d. Never use any other sorting algorithms.

e. You are only allowed to apply algorithms with O(n) complexity other than Merge and

Quick sort.

f. Make sure that your final array is sorted after both Merge and Quick sort algorithms

finish.

2. Sort elements in ascending order using stack, i.e. make the smallest element to be the top

element of the stack. For example, given the stack elements (from bottom to top): 5, 2, 6,

9, sort the elements to make the stack elements become (from bottom to top): 9, 6, 5, 2.

The only data structure you can use is array-based stack. Given a stack st, use one extra

stack, tmpst, to store temporary data.

Merge sort Quick sort

Not sorted

Sorted

a. Write a C++ program to sort elements in an array-based stack in ascending order.

b. Demonstrate the sorting process with given input numbers {25, 10, 15, 20, 30}.

Algorithm:

pop out the st to a variable tmp until it finishes all elements.

while tmpst is not empty

if the top element of tmpst is smaller than tmp,

pop out tmpst and push that element onto st

push tmp onto tmpst ……

Sample output (Example):

Note: implement the Stack class with all necessary functionality.

APPENDIX 1

MARKING RUBRICS

Component Title Mergesort and Quicksort Percentage

(%) 50

Criteria

Score and Descriptors Weight

(%) Marks

(50-40) (40-30) (30-15) (15-10) (10-0)