so you have a counting variable: static int count =0; Where would you put the va

Question

 so you have a counting variable: static int count =0; Where would you put the variable in each of the sorting function provided below (Quicksort,mergesort ,heapsort!!) ? Please help!  The sorting functions below all work fine. I need the 100% correct answer. If you are not sure, please don't reply. If possible, please slove it with explanations. Thanks

-------mergesort implemention

 void merge(int* arr, int low, int middle, int high)

 {     int* tmp = new int[high-low+1];     int i = low;     int j = middle+1;     int k = 0;     while ((i <= middle) && (j <= high))     {         if (arr[i] < arr[j])             tmp[k++] = arr[i++];         else             tmp[k++] = arr[j++];     }     if (i <= middle)     {         while (i <= middle)             tmp[k++] = arr[i++];     }     if (j <= high)     {         while (j <= high)             tmp[k++] = arr[j++];     }     /*See how are we adjusting tmp array index below*/     for (k = low; k <= high; ++k)         arr[k] = tmp[k-low];     delete[] tmp;     return; } /*For an array of size N call with 0 as low and N-1 as high*/void mergeSort(int* arr, int low, int high) {     if (low < high)     {         int middle = (high + low)/2;         mergeSort(arr, low, middle);         mergeSort(arr, middle+1, high);         merge(arr, low, middle, high);     }     return; }

 -------mergesort implemention

---------------Quicksort implementation

 int partition(int* a, int low, int high) {     /*Start index for scanning the array*/     int left = low;     /*Select middle element of the array as pivot*/     int pivotIdx = low + (high - low)/2;     /*Swap pivot with right most element of the array*/     int pivot = a[pivotIdx];     a[pivotIdx] = a[high];     a[high] = pivot;     pivotIdx = high;     /*Pivot will be placed at this index such that all elements     to right of it are greater than pivot and all elements to     the left of it are smaller than pivot*/     int partitionIdx = low;     while (left < high)     {         /*Initially our partition index is set to leftmost element         index in the input array. We keep traversing towards right         of the input array and if we find an element lesser than         pivot, we swap it with element at partiotion index and          increment partition index else just keep moving right*/         if (a[left] < pivot)          {             int tmp = a[left];             a[left] = a[partitionIdx];             a[partitionIdx] = tmp;             ++partitionIdx;         }         ++left;     }     /*Place the pivot value at the partition index*/     a[pivotIdx] = a[partitionIdx];     a[partitionIdx] = pivot;     return partitionIdx; } /*quick sort - sorts data in ascending order For an array of size N, initial call should be made with low 0 and high as N-1*/

 void q_sort(int* a, int low, int high) {     if (low < high)     {         int k = partition(a, low, high);         /*Sort all elements to the left of 'k'*/         q_sort(a, low, k-1);         /*Sort all elements to the right of 'k'*/         q_sort(a, k+1, high);     }     return; }

 void shiftRight(int* arr, int low, int high) {     int root = low;     while ((root*2)+1 <= high)     {         int leftChild = (root * 2) + 1;         int rightChild = leftChild + 1;         int swapIdx = root;         /*Check if root is less than left child*/         if (arr[swapIdx] < arr[leftChild])         {             swapIdx = leftChild;         }         /*If right child exists check if it is less than current root*/         if ((rightChild <= high) && (arr[swapIdx] < arr[rightChild]))         {             swapIdx = rightChild;         }         /*Make the biggest element of root, left and right child the root*/         if (swapIdx != root)         {             int tmp = arr[root];             arr[root] = arr[swapIdx];             arr[swapIdx] = tmp;             /*Keep shifting right and ensure that swapIdx satisfies             heap property aka left and right child of it is smaller than             itself*/             root = swapIdx;         }         else         {             break;         }     }     return; } void heapify(int* arr, int low, int high) {     /*Start with middle element. Middle element is chosen in     such a way that the last element of array is either its     left child or right child*/     int midIdx = (high - low -1)/2;     while (midIdx >= 0)     {         shiftRight(arr, midIdx, high);         --midIdx;     }     return; } void heapSort(int* arr, int size) {     assert(size > 0);     /*This will put max element in the index 0*/     heapify(arr, 0, size-1);     int high = size - 1;     while (high > 0)     {         /*Swap max element with high index in the array*/         int tmp = arr[high];         arr[high] = arr[0];         arr[0] = tmp;         --high;         /*Ensure heap property on remaining elements*/         shiftRight(arr, 0, high);     }     return; }

Explanation / Answer

1.

I am giving example of q_sort.

q_sort(.......)

{

static int count;

...............

partition(.....);

...............

}

we are increasing count in partition function. In that case count is not known to partition function.

We can not work like that. We have to declare count as a global variable.

But if you want to use static count, then we should go for mergeing of all specific sorting code to single code with help of stack, not through recursion. Please change your whole code through stack.

2. I have mised one count++. Please put count++ after below line, which i have mentioned here in heap your sort code(means after curly bracket).

if (swapIdx != root)
{

Whenever array element has compared, those places count are placed.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.