program设计程序讲解、辅导C++编程语言、c++程序讲解
- 首页 >> Matlab编程 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)
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)