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

Answer:

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);

}