Where should I place a count variable to count how many swaps occurs in this qui

Question

Where should I place a count variable to count how many swaps occurs in this quick sort. I currently have the swap inside of the partition but i keep recieving swaps even when no swaps occur. Here is the code

/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high,int& swap1)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
  
for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(arr[i], arr[j]);
swap1++; //<- Here is where i placed the swap.
}
}
swap(arr[i + 1], arr[high]);
//swap1++;
return (i + 1);
}
  
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high,int& swap1)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high,swap1);
  
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1,swap1);
quickSort(arr, pi + 1, high,swap1);
  
}
}  

Explanation / Answer

Here in the code is given incomplete. We are not able to understand how you are calling the methods. And there should be one more method called swap, which is not give above. As you are trying to find how many swaps occurred, please put the counter inside swap method, so that the counter will be incremented only when the swap method is called.

Please comment if you need any help.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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