Question

int foo(int A[], int left, int right){ int i, x, q, N; if(right <= left) return 1; x = 0; for(i=left; i <= right; i++) x += A[i] % 2; // busy work... N = right-left+1; q = left + (N/3); return x + foo(A, left, q) + foo(A, q+1, right);

Answer 1

quicksort.cpp

void quickSort(int arr[], int left, int right) {

int i = left, j = right;

int tmp;

int pivot = arr[(left + right) / 2];

/* partition */

while (i <= j) {

while (arr[i] < pivot)

i++;

while (arr[j] > pivot)

j--;

if (i <= j) {

tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

i++;

j--;

}

};

/* recursion */

if (left < j)

quickSort(arr, left, j);

if (i < right)

quickSort(arr, i, right);

}