(Quicksort) The recursive sorting technique called quicksort uses the following basic algorithm for a one-dimensional vector of values:

a) Partitioning Step: Take the first element of the unsorted vector and determine its final location in the sorted vector (i.e., all values to the left of the element in the vector are less than the elements value, and all values to the right of the element in the vector are greater than the elements valuewe show how to do this below). We now have one value in its proper location and two unsorted subvectors.

b) Recursion Step: Perform the Partitioning Step on each unsorted subvector. Each time the Partitioning Step is performed on a subvector, another value is placed in its final location of the sorted vector, and two unsorted subvectors are created. When a subvector consists of one element, that elements value is in its final location (because a one-element vector is already sorted).

The basic algorithm seems simple enough, but how do we determine the final position of the first element value of each subvector? As an example, consider the following set of values (the value in bold is for the partitioning elementit will be placed in its final location in the sorted vector):

37 2 6 4 89 8 10 12 68 45

Starting from the rightmost element of the vector, compare each element value with 37 until an element value less than 37 is found; then swap 37 and that elements value. The first element value less than 37 is 12, so 37 and 12 are swapped. The new vector is

12 2 6 4 89 8 10 37 68 45

Element value 12 is in italics to indicate that it was just swapped with 37. Starting from the left of the vector, but beginning with the element value after 12, compare each element value with 37 until an element value greater than 37 is found then swap 37 and that element value. The first element value greater than 37 is 89, so 37 and 89 are swapped. The new vector is

12 2 6 4 37 8 10 89 68 45

Starting from the right, but beginning with the element value before 89, compare each element value with 37 until an element value less than 37 is foundthen swap 37 and that element value. The first element value less than 37 is 10, so 37 and 10 are swapped. The new vector is

12 2 6 4 10 8 37 89 68 45

Starting from the left, but beginning with the element value after 10, compare each element value with 37 until an element value greater than 37 is foundthen swap 37 and that element value. There are no more element values greater than 37, so when we compare 37 with itself, we know that 37 has been placed in its final location of the sorted vector. Every value to the left of 37 is smaller than it, and every value to the right of 37 is larger than it. Once the partition has been applied on the previous vector, there are two unsorted subvectors. The subvector with values less than 37 contains 12, 2, 6, 4, 10 and 8. The subvector with values greater than 37 contains 89, 68 and 45. The sort continues recursively, with both subvectors being partitioned in the same manner 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 arguments a starting index and an ending index on the original vector being sorted. Please create ten vectors with random size from 0 ~20 elements and randomly choose the size of the vector numbers from 0~100. Put the numbers in the vectors and use quick sort to sort them.

Please be aware the vector size is randomly choose from 0-20 and the created sized for a vector is listed inside a pair of parentheses CC) The 1st set of data 18 Initial vector values are: 42 94 66 62 40 36 26 25 24 12 20 23 55 91 71 40 7 78 The sorted vector values are: 12 20 23 24 25 26 36 40 40 42 55 62 66 71 78 91 94 The 2nd set of dataC3 Initial vector values are: 97 The sorted vector values are 97 The 3rd set of data(20 Initial vector values are 64 73 7 89 42 74 30 17 31 47 30 87 22 72 15 95 38 48 51 97 The sorted vector values are 15 17 22 30 30 31 38 42 47 48 51 64 72 73 74 87 89 95 97 The 4th set of data(16 Initial vector values are 34 55 61 51 26 46 52 42 42 34 26 53 80 28 81 96 The sorted vector values are 26 26 28 34 34 42 42 46 51 52 53 55 61 80 81 96 The 5th set of data 3 Initial vector values are: 94 28 63 The sorted vector values are: 28 63 94 The 6th set of data 13 Initial vector values are: 48 41 74 13 3 15 55 85 59 98 46 71 20 The sorted vector values are: 3 13 15 20 41 46 48 55 59 71 74 85 98 The 7th set of data 16 Initial vector values are 65 22 76 98 68 41 96 86 1 44 62 38 31 87 28 72 The sorted vector values are 1 22 28 31 38 41 44 62 65 68 72 76 86 87 96 98 The 8th set of data(4) Initial vector values are: 54 76 80 15 The sorted vector values are: 15 54 76 80 The 9th set of data(11 Initial vector values are 31 87 87 66 32 98 61 57 79 67 72 The sorted vector values are 31 32 57 61 66 67 72 79 87 87 98 The 10th set of data Initial vector values are 65 24 61 43 87 The sorted vector values are 24 43 61 65 87