How to count and return swaps in algorithms - mergesort and quicksort?

@domenico 

In both mergesort and quicksort algorithms, swaps occur when two elements in the array are swapped in order to reorder elements during the sorting process. Swaps are essential for sorting algorithms to properly order elements in the array.

To count and return swaps in mergesort and quicksort algorithms, you can create a variable to keep track of the number of swaps that occur during the sorting process.

Here is how you can count and return swaps in mergesort:

1. In the merge function of mergesort, track the number of swaps by creating a variable to store the count of swaps.
2. Whenever a swap occurs in the merge step, increment the swap count.
3. Once the mergesort algorithm is complete, return the swap count to display the total number of swaps that occurred during the sorting process.

Here is an example code snippet for counting swaps in mergesort:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int mergeSort(int arr[], int l, int r) {
    int swaps = 0;
    if (l < r) {
        int m = l + (r - l) / 2;
        swaps += mergeSort(arr, l, m);
        swaps += mergeSort(arr, m + 1, r);
        
        // Merge the sorted halves and count swaps
        swaps += merge(arr, l, m, r);
    }
    return swaps;
}

For quicksort, you can implement a similar approach to count and return swaps. Here is an example code snippet for counting swaps in quicksort:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int quickSort(int arr[], int low, int high) {
    int swaps = 0;
    if (low < high) {
        int pi = partition(arr, low, high, &swaps);
        
        // Recursively sort elements before and after partition
        swaps += quickSort(arr, low, pi - 1);
        swaps += quickSort(arr, pi + 1, high);
    }
    return swaps;
}

By implementing the above code snippets, you can count and return the number of swaps that occur during the mergesort and quicksort algorithms.