### CISP400 Object Oriented Programming with C++

Added on - 09 Oct 2019

12

pages

2105

words

12

views

0

downloads

Showing pages 1 to 4 of 12 pages

You can choose to submit either A7 (worth 150 points), AD7 (worth 180), or both (worth 180)for 7th assignment you will get a score for this assignment either 150 points base or 180 pointsbase.Grading Criteria:1.If the submitted program cannot be compiled or run on aMicrosoft visual studio 2013 C++ compiler, the assignment willnot get any credit.2.If the file name does not follow the naming instruction as statedin syllabus, the assignment will get 5 to 15 points deduction.3.If the header section of the submitted file does not includepersonal information and purpose of the file, the assignment willget 5 to 30 points deduction.4.Late assignments will not get any credit for the assignment.5.A submission does not follow the instructions of the assignmentwill get little credit.6.A portion of the assignment is not finished or incomplete will getlittle or no credit.7.Submit an assignment to a wrong drop box. The wrong drop boxone will not get any credit.8.If use A for AD or AD for A assignments in the file name, thestudent will not get any credit for the assignments.9.If the submitted file(s) cannot be opened by the instructor’ssoftware (WinZip, Visual Studio, or text editor) the assignmentwill have little credit.10.If the submission file does not include all necessaryprogramming files to run the program, the program will get littlecredit.11.If the program does not separate into several files (driver,header file, implementation file, etc.) as describe in theassignment, the program will get little credit.Page1of12CISP400V9A7

12.If the displaying result of the program is not exactly matchwith the graphic in the assignment description or the displayingresult of the executable file which comes with the assignment,the assignment will get little credit.13.If the program does not have enough detail documentationin the programming area the program will get 5 to 30 pointsdeduction.14.If the program includes some unrelated documentation theprogram will get some points deduction.A7(Quicksort) The recursive sorting technique called quicksort uses the following basic algorithmfor a one-dimensional vector of values:a) Partitioning Step: Take the first element of the unsorted vector and determine its final locationin the sorted vector (i.e., all values to the left of the element in the vector are less than theelement’s value, and all values to the right of the element in the vector are greater than theelement’s value—we show how to do this below). We now have one value in its proper locationand two unsorted subvectors.b) Recursion Step: Perform the Partitioning Step on each unsorted subvector. Each time thePartitioning Step is performed on a subvector, another value is placed in its final location of thesorted vector, and two unsorted subvectors are created. When a subvector consists of oneelement, that element’s value is in its final location (because a one-element vector is alreadysorted).The basic algorithm seems simple enough, but how do we determine the final position of the firstelement value of each subvector? As an example, consider the following set of values (the valuein bold is for the partitioning element—it will be placed in its final location in the sorted vector):372 6 4 89 8 10 12 68 45Page2of12CISP400V9A7

Starting from the rightmost element of the vector, compare each element value with 37 until anelement value less than 37 is found; then swap 37 and that element’s value. The first elementvalue less than 37 is 12, so 37 and 12 are swapped. The new vector is12 2 6 4 89 8 103768 45Element value 12 is in italics to indicate that it was just swapped with 37. Starting from the leftof the vector, but beginning with the element value after 12, compare each element value with 37until an element value greater than 37 is found— then swap 37 and that element value. The firstelement value greater than 37 is 89, so 37 and 89 are swapped. The new vector is12 2 6 4378 10 89 68 45Starting from the right, but beginning with the element value before 89, compare each elementvalue with 37 until an element value less than 37 is found—then swap 37 and that element value.The first element value less than 37 is 10, so 37 and 10 are swapped. The new vector is12 2 6 4 10 83789 68 45Starting from the left, but beginning with the element value after 10, compare each element valuewith 37 until an element value greater than 37 is found—then swap 37 and that element value.There are no more element values greater than 37, so when we compare 37 with itself, we knowthat 37 has been placed in its final location of the sorted vector. Every value to the left of 37 issmaller than it, and every value to the right of 37 is larger than it. Once the partition has beenapplied on the previous vector, there are two unsorted subvectors. The subvector with valuesless than 37 contains 12, 2, 6, 4, 10 and 8. The subvector with values greater than 37 contains89, 68 and 45. The sort continues recursively, with both subvectors being partitioned in the samemanner as the original vector.Based on the preceding discussion, write a recursive function, quickSortHelper, to sort ten one-dimensional integer vectors. The function should receive as argumentsa starting index and anending index on the original vector being sorted. Please create ten vectors with random sizefrom 0 ~20 elements and randomly choose the size of the vector numbers from 0~100. Put thenumbers in the vectors and use quick sort to sort them.Page3of12CISP400V9A7

This assignment comes with a CISP400V9A7.zip file. It includes CISP400V9A7.exe file. TheCISP400V9A7.exe file is an executable file. You can double click the file to get to the expectingresult of this assignment.The following are some of the displays of the expecting results.Please be aware thevector size is randomlychoose from 0 ~ 20and the created sizedfor a vector is listedinside a pair ofparentheses (“ ( )”).Page4of12CISP400V9A7

**You’re reading a preview**

To View Complete Document

Become a Desklib Library Member.

Subscribe to our plans