Sorting possible using size 3 subarray rotation
Given an array of integer values which need to be sorted by only one operation – subarray rotation where subarray size should be 3. For example, If our array is (1 2 3 4) then we can reach to (1 4 2 3), (3 1 2 4) in one step. We need to tell whether it is possible to sort the complete array with this operation or not.
Suppose we have one subarray as [A[i] A[i+1] A[i+2]]. After one rotation, we get [A[i+2], A[i], A[i+1]]
If we observe inversions before and after rotation, we can see that parity of inversion is not changed i.e. if [A[i] A[i+1] A[i+2]] has even number of inversions [A[i+2] A[i] A[i+1]] will have even inversions. Same is true for odd inversions. Due to movement of A[i+2], inversions either increase by 2 or decrease by 2 or remain same i.e. their parity won’t change.
After observing above fact we can say that if initial array configuration has even number of inversion then it is possible to make them zero making array completely sorted otherwise not. We use merge sort based method for counting inversions. After getting the number of inversions, we can easily check parity of inversion and conclude whether it is possible to sort the array or not.
If we observe inversions before and after rotation, we can see that parity of inversion is not changed i.e. if [A[i] A[i+1] A[i+2]] has even number of inversions [A[i+2] A[i] A[i+1]] will have even inversions. Same is true for odd inversions. Due to movement of A[i+2], inversions either increase by 2 or decrease by 2 or remain same i.e. their parity won’t change.
After observing above fact we can say that if initial array configuration has even number of inversion then it is possible to make them zero making array completely sorted otherwise not. We use merge sort based method for counting inversions. After getting the number of inversions, we can easily check parity of inversion and conclude whether it is possible to sort the array or not.
/* This function merges two sorted arrays and
returns inversion count in the arrays.*/
public
static
int
merge(
int
[] arr,
int
left,
int
mid,
int
right)
{
int
[] temp =
new
int
[arr.length];
int
inv_count =
0
;
int
i = left;
/* i is index for left subarray*/
int
j = mid;
/* j is index for right subarray*/
int
k = left;
/* k is index for resultant merged
subarray*/
while
((i <= mid-
1
) && (j <= right))
{
if
(arr[i] <= arr[j])
{
temp[k++] = arr[i];
i++;
}
else
{
temp[k++] = arr[j];
j++;
/* this is tricky -- see above
explanation/diagram for merge()*/
inv_count = inv_count + (mid-i);
}
}
/* Copy the remaining elements of left subarray
(if there are any) to temp */
while
(i <= (mid-
1
))
temp[k++] = arr[i++];
/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while
(j <= right)
temp[k++] = arr[j++];
/* Copy back the merged elements to original
array */
for
(
int
l = left; l <= right; l++)
arr[l] = temp[l];
return
inv_count;
}
/* An auxiliary recursive function that sorts
the input array and returns the number of
inversions in the array. */
public
static
int
_mergeSort(
int
[] arr,
int
left,
int
right)
{
int
mid, inv_count =
0
;
if
(left < right)
{
/* Divide the array into two parts and
call _mergeSortAndCountInv() for each
of the parts */
mid = (left + right)/
2
;
/* Inversion count will be sum of inversions
in left-part, right-part and number of
inversions in merging */
inv_count = _mergeSort(arr, left, mid);
inv_count += _mergeSort(arr, mid+
1
, right);
inv_count += merge(arr, left, mid+
1
, right);
}
return
inv_count;
}
/* This function sorts the input array and returns the
number of inversions in the array */
public
static
int
mergeSort(
int
[] arr,
int
N)
{
return
_mergeSort(arr,
0
, N-
1
);
}
public
static
boolean
possibleSortingBy3SizeSubarray(
int
arr[],
int
N)
{
int
numberOfInversion = mergeSort(arr, N);
// if number of inversions are even then only
// we can sort the array
return
(numberOfInversion %
2
==
0
);
}