vborees
BAN USERThe idea is simple: toss 2 coins, until you get different results. Then the probability of (true, false) = the probability of (false, true). Even more, it is easy to compute that
P(first coin is heads | both coins are different) = 1 / 2.
Having this understanding, the code is obvious:
bool rand_bit() {
bool coin1, coin2;
do {
coin1 = rand_bit_p();
coin2 = rand_bit_p();
} while (coin1 == coin2);
return coin1;
}
Let's think about sorting in descending order for just a second. Intuitively, exchanging elements while sorting contains the required information already. If we move some element forward, we incrementing the counter for all elements, that we have "outruned" in the array.
So, we need only to modify some existing sorting algorithm witn O(nlogn) complexity in order to store the required information. Let's take Merge sort and make two modifications.
1. Let's preserve the source array by introducing the array of indices ( int[] arrindices ), where arrindices[i] shows which element of the source array stays at position i at the moment.
2. we introduce int[] resarray to store the number of elements, greater than that element remaining in the array.
Let's consider the DoMerge part of the algorithms, where we are merging two sorted subarrays. If we take the element from the second array (else clause), it is by default greater then all remaining elements from the first array. So, we have to increment the resulting array for all such elements by one. To avoid introducing another loops in code, we'll introduce the counter of the elements, that had been moved from the second array, and will add this counter to resarray for each element of the first array, when it is taken to the resulting array.
Complete code here:
public class MergeSortModified
{
public void DoMerge(int[] arr, int[] arrindices, int[] resarray, int start, int middle, int end)
{
// create temp array to store sorted subarray
int[] temp = new int[end - start + 1];
int l = start;
int m = middle + 1;
int k = 0;
// store the amount
int gr = 0;
// run a marker until at least one source subarrays is not empty
while (l <= middle && m <= end)
{
if (arr[arrindices[l]] >= arr[arrindices[m]])
{
temp[k] = arrindices[l];
// increment the result array by the number of already found greater elements
resarray[arrindices[l]] += gr;
l++;
k++;
}
else
{
// increment the amount of "greater" elements
gr++;
temp[k] = arrindices[m];
m++;
k++;
}
}
// take the remaining elements from the first subarray is any
while (l <= middle)
{
temp[k] = arrindices[l];
// increment the result array by the number of already found greater elements
resarray[arrindices[l]] += gr;
k++;
l++;
}
// take the remaining elements from the second subarray is any
while (m <= end)
{
temp[k++] = arrindices[m++];
}
// copy sorted subarray of indices back to the indices array
for (int pos = 0; pos < end - start + 1; pos++)
arrindices[start + pos] = temp[pos];
}
public void Merge(int[] arr, int[] arrindices, int[] resarray, int start, int end)
{
// if array is long enough
if (start < end)
{
// divide array into two parts
int m = (start + end) / 2;
// sort the first half
Merge(arr, arrindices, resarray, start, m);
// sort the second half
Merge(arr, arrindices, resarray, m + 1, end);
// Merge sorted subarrays
DoMerge(arr, arrindices, resarray, start, m, end);
}
}
}
- vborees May 24, 2021