Is it possible to calculate the number of count inversions using quicksort?

Question

I have already solved the problem using mergesort, now I am thinking is that possible to calculate the number using quicksort? I also coded the quicksort, but I don't know how to calculate. Here is my code：

def Merge_and_Count(AL, AR):
    count=0
    i = 0
    j = 0
    A = []
    for index in range(0, len(AL) + len(AR)):        
        if i<len(AL) and j<len(AR):
            if AL[i] > AR[j]:
                A.append(AR[j])
                j = j + 1
                count = count+len(AL) - i
            else:
                A.append(AL[i])
                i = i + 1
        elif i<len(AL):
            A.append(AL[i])
            i=i+1
        elif j<len(AR):
            A.append(AR[j])
            j=j+1
    return(count,A)

def Sort_and_Count(Arrays):
        if len(Arrays)==1:
            return (0,Arrays)
        list1=Arrays[:len(Arrays) // 2]
        list2=Arrays[len(Arrays) // 2:]
        (LN,list1) = Sort_and_Count(list1)
        (RN,list2) = Sort_and_Count(list2)
        (M,Arrays)= Merge_and_Count(list1,list2)
        return (LN + RN + M,Arrays)

Baggy

Answer 1

Generally no, because during the partitioning, when you move a value to its correct side of the pivot, you don't know how many of the values you're moving it past are smaller than it and how many are larger. So, as soon as you do that you've lost information about the number of inversions in the original input.

Leslee

is that possible to caculate how many it past?or the Complexity is about O(n^2)? – Baggy

Well, Quicksort is O(n log n) on average to begin with, O(n^2) worst case. So yes, adding a Theta(n^2) operation to each partition step is going to make the complexity worse than just forgetting about the sort and naively counting inversions by checking every pair of elements in the input. – Leslee

I think if you can think up a special case, you will know why can't. For instance, suppose we have set {3, 2, 1} and use the last one to be the pivot. Actually number 2 lose its inversion, because after one iteration the array will be {1, 2, 3}. – Torrid

Answer 2

I come across this problem for some times, As a whole, I think it should be still ok to use quick sort to compute the inversion count, as long as we do some modification to the original quick sort algorithm. (But I have not verified it yet, sorry for that).

Consider an array 3, 6, 2, 5, 4, 1. Support we use 3 as the pivot, the most voted answer is right in that the exchange might mess the orders of the other numbers. However, we might do it different by introducing a new temporary array:

1. Iterates over the array for the first time. During the iteration, moves all the numbers less than 3 to the temporary array. For each such number, we also records how much number larger than 3 are before it. In this case, the number 2 has one number 6 before it, and the number 1 has 3 number 6, 5, 4 before it. This could be done by a simple counting.
2. Then we copy 3 into the temporary array.
3. Then we iterates the array again and move the numbers large than 3 into the temporary array. At last we get 2 1 3 6 5 4.

The problem is that during this process how much inversion pairs are lost? The number is the sum of all the numbers in the first step, and the count of number less than the pivot in the second step. Then we have count all the inversion numbers that one is >= pivot and another is < pivot. Then we could recursively deal with the left part and the right part.

Stretcherbearer

Answer 3

The solution given by @Yun Gao is correct, here is the code I implemented:

fn calc_inversions_quick_sort(vec: &[usize]) -> usize {
    fn partition_count(vec: &mut [usize], low: usize, high: usize) -> (usize, usize) {
        let pivot = vec[low];
        let ind_len = high - low + 1;
        let mut i = low;
        let mut count = 0;
        let mut small_ind = Vec::with_capacity(ind_len);
        let mut big_ind = Vec::with_capacity(ind_len);
        let old_v = vec.to_vec();
        for j in low + 1..=high {
            if vec[j] < pivot {
                count += j - i;
                small_ind.push(j);
                i += 1;
            } else {
                big_ind.push(j);
            }
        }
        let perm = [small_ind, vec![low], big_ind].concat();
        for (ind, p) in perm.iter().enumerate() {
            vec[low + ind] = old_v[*p];
        }

        (i, count)
    }
    fn quick_sort_count(vec: &mut [usize], low: usize, high: usize) -> usize {
        let mut res = 0;
        if low < high {
            let (pos, count) = partition_count(vec, low, high);
            res += count;
            if pos > low + 1 {
                res += quick_sort_count(vec, low, pos - 1);
            }
            if high > pos + 1 {
                res += quick_sort_count(vec, pos + 1, high);
            }
        }
        res
    }

    let mut v = vec.to_vec();
    let len = vec.len();
    quick_sort_count(&mut v, 0, len - 1)
}

Tonkin