We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Well, I tried with merge sort. And merge sort takes like quicksort O(n log n) time. This is pretty fast. But anyway the timeout was not the problem. The problem is that it produces wrong answers. Has anyone an idea how this problem differs from the classic inversion count problem?
I got it to run with quicksort. What helped me was to remember to operate on copies of the arrays, since the approach of comparing with sorted and swapping elements destroys the map and the original input array. You need to compare for both asc and desc. One is just inversion of the other. Here is my C# verion with custom quick sort.
// Complete the lilysHomework function below.
static int lilysHomework(int[] arr) {
var originalIndexValueMap = new Dictionary<int, int>();
for (var i = 0; i < arr.Length; i++)
{
originalIndexValueMap[arr[i]] = i;
}
var sortedAsc = new int[arr.Length];
Array.Copy(arr, 0, sortedAsc, 0, arr.Length);
quicksort(sortedAsc, 0, arr.Length - 1);
var sortedDesc = new int[arr.Length];
Array.Copy(sortedAsc, 0, sortedDesc, 0, sortedAsc.Length);
Array.Reverse(sortedAsc);
var ascCount = Count(arr, sortedAsc, originalIndexValueMap);
var descCount = Count(arr, sortedDesc, originalIndexValueMap);
return Math.Min(ascCount, descCount);
}
static int Count(int[] a, int[] sorted, Dictionary<int, int> map)
{
var arr = new int[a.Length];
Array.Copy(a, 0, arr, 0, arr.Length);
var mapCopy = new Dictionary<int, int>();
foreach (var kv in map)
{
mapCopy[kv.Key] = kv.Value;
}
var count = 0;
for (var i = 0; i < arr.Length; i++)
{
if (arr[i] != sorted[i])
{
count++;
var indexToSwap = mapCopy[sorted[i]];
mapCopy[arr[i]] = indexToSwap;
var tmp = arr[i];
arr[i] = arr[indexToSwap];
arr[indexToSwap] = tmp;
}
}
return count;
}
static void quicksort(int[] arr, int left, int right)
{
var p = arr[(right + left) / 2];
int i = left;
int j = right;
while (i <= j)
{
while (arr[i] < p) {
i++;
}
while (arr[j] > p) {
j--;
}
if (i <= j)
{
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
if (left < j)
{
quicksort(arr, left, j);
}
if (right > i)
{
quicksort(arr, i, right);
}
}
Lily's Homework
You are viewing a single comment's thread. Return to all comments →
I thought I could solve this problem by quicksorting the array and then counting the number of swaps.
No other person did it this way and I was unable to get it to pass for more than the first test case. I guess I misunderstood the problem somehow.
Why wouldn't my approach work?
I tried the same but i think its because quicksorting takes a lot of time to partition and then recounting them takes a lot of time
Well, I tried with merge sort. And merge sort takes like quicksort O(n log n) time. This is pretty fast. But anyway the timeout was not the problem. The problem is that it produces wrong answers. Has anyone an idea how this problem differs from the classic inversion count problem?
Ok, I think I got it: This problem is not about the number of inversions. It is about the minimum number of swaps.
You can try heapsort as it works beautifully in this case.
I got it to run with quicksort. What helped me was to remember to operate on copies of the arrays, since the approach of comparing with sorted and swapping elements destroys the map and the original input array. You need to compare for both asc and desc. One is just inversion of the other. Here is my C# verion with custom quick sort.