partition code:--------------------------------------------------------------------------------------------------------------------

#include #include #include #include #include using namespace std;

//Initially, start = 0, fin = v.size()-1 //Returns the k-th element in v if the elements were //sorted in ascending order int select(vector &v, int start, int fin, int k);

//initializes v with integers from standard input cin void init(vector &v);

//partitions elements of A around element A[index] int partition(vector &A, int low, int high, int index);

int main(){ vector v; init(v); int vsize = v.size(); for(int i = 0; i

//Returns the k-th element in increasing order (count starts with 0) int select(vector &v, int start, int fin, int k){

int vsize = fin - start + 1;

if(start == fin) return v[start]; else if(start > fin) return -1; if(vsize

vector medians(msize, 0); int med_ind = 0; for(int i = start; i temp(5, 0); int j = 0; for(; j > 1;//divide by 2 if(j % 2 == 0) jmid--; medians[med_ind++] = temp[jmid];

} }//for i

//so far we selected the medians of n/5 groups, each group of 5 elements int mid = msize >> 1; //divide by 2 if((msize % 2) == 0) mid--;

//find the median of the medians int x = select(medians, 0, msize - 1, mid); if(x == -1) { cerr

//partition elements of v around x //find the index of x in v int ind_of_x = -1; for(int i = start; i

int pivotIndex = partition(v, start, fin, ind_of_x);

if(k == pivotIndex) return v[k]; else if(pivotIndex

int partition(vector &A, int low, int high, int index){ //swap element at "index" and element at "high" (the last in the range) int temp = A[index]; A[index] = A[high]; A[high] = temp;

int pivot = A[high]; int i = low, j = high - 1; while(i = low && A[j] > pivot) j--; if(i

void init(vector &v){ int x; while(cin >> x) v.push_back(x);

}

Function partition that takes as parameters (1) string S of size n, passed constant by reference (2) vector indices of integers of size n, where each integer is the starting position of a suffix in S; indices are passed by reference (3) integers low and high, the start and the end indices of a given range; and (4) an integer pivotindex, which is an arbitrary index of the vector indices. int partition(const string &S, vector &indices, int low, int high, int pivotindex) First, this function swaps indices[pivotindex] and indices[high], where high is the last index in the range. Then, this function will partition suffix indices (use code of Partition provided in lecture notes as an example) so that the first half contains positions of suffixes that are less than suffix pivot and the second contains indices of suffixes that are greater than suffix pivot. This function will call the functions lessThan to accomplish this task INPUT: abracadabra 4 OUTPUT: 018310 5 74296 INPUT: abracadabra 1 OUTPUT: 0 10 8 3 7 5 1 4 2 9 6 INPUT: Life what happens while we are making other plans. 6 OUTPUT 46 43 2 3 4 41 49 7 37 9 10 11 36 32 1430 29 17 27 26 25 23 22 6 24 20 19 18 28 16 15 31 13 33 34 35 12 8 38 39 40 5 42 1 44 45 0 47 48 21 Function partition that takes as parameters (1) string S of size n, passed constant by reference (2) vector indices of integers of size n, where each integer is the starting position of a suffix in S; indices are passed by reference (3) integers low and high, the start and the end indices of a given range; and (4) an integer pivotindex, which is an arbitrary index of the vector indices. int partition(const string &S, vector &indices, int low, int high, int pivotindex) First, this function swaps indices[pivotindex] and indices[high], where high is the last index in the range. Then, this function will partition suffix indices (use code of Partition provided in lecture notes as an example) so that the first half contains positions of suffixes that are less than suffix pivot and the second contains indices of suffixes that are greater than suffix pivot. This function will call the functions lessThan to accomplish this task INPUT: abracadabra 4 OUTPUT: 018310 5 74296 INPUT: abracadabra 1 OUTPUT: 0 10 8 3 7 5 1 4 2 9 6 INPUT: Life what happens while we are making other plans. 6 OUTPUT 46 43 2 3 4 41 49 7 37 9 10 11 36 32 1430 29 17 27 26 25 23 22 6 24 20 19 18 28 16 15 31 13 33 34 35 12 8 38 39 40 5 42 1 44 45 0 47 48 21