#arrays #c #sorting
#массивы #c #сортировка
Вопрос:
Учитывая массив, который сортируется в порядке возрастания, а затем в порядке убывания, например: {1, 3, 5, 4, 2}, Я хочу найти количество инверсий, необходимых для сортировки этого массива в O (n). Это мой код, который сортирует такие массивы в O (n):
void sort(long* a, long* result, long n)
{
long* start = amp;a[0];
long* end = amp;a[n - 1];
long count = 0;
while (start <= end) {
if (*start < *end) {
result[count] = *start;
start = 1;
}
else {
result[count] = *end;
end -= 1;
}
}
}
В моем коде я использовал 2 указателя от начала и конца и сохранил отсортированный массив в результирующем массиве. Как мне подсчитать количество инверсий, используя аналогичный алгоритм?
Комментарии:
1. Пожалуйста, определите «инверсию»
2. Вероятно, вы имеете в виду обмен для инверсии , и вы хотите знать минимальное количество требуемой замены?
How do I count the number of inversions using a similar algorithm?: поскольку ваш способ сортировки не инвертирует (не меняет местами) элементы, его нельзя использовать для подсчета количества требуемых инверсий (перестановок).3. Возможно, вам захочется прочитать статью в Википедии о циклической сортировке .
Ответ №1:
Вы могли бы использовать этот алгоритм из «https://www.geeksforgeeks.org/counting-inversions /»:
Алгоритм:
- Пройдите по массиву от начала до конца.
- Для каждого элемента найдите количество элементов, меньших текущего числа до этого индекса, используя другой цикл.
- Суммируйте количество инверсий для каждого индекса.
- Выведите количество инверсий.
Вы также можете найти пример кода на их веб-сайте.
Более того, для вашей функции кажется, что вам ПРОСТО нужна новая переменная для хранения количества выполняемых вами инверсий.
Надеюсь, это помогло!