По-бързо сортиране?

[misho]

Задачата е следната:
Трябва да се намери броя на инверсиите в дадена пермутация.
Иначе казано, трябва да намеря броя на разместваният, които трябва да се направят, за сведем това
0 4 2 1 3
до това
0 1 2 3 4
В дадения пример инверсиите са 4.
И тук идва интересната част. Всичко това трябва да става максимално бързо. Това, което направих е да използвам Insertion sort и да броя всички промени, които той прави с един flag. Проблемът е, че времето е незадоволително. Трябва да го сведа от сегашните близо 3 секунди на 1-2. Ето какво измайсторих до момента:

#include<iostream>
#include<cstdio>

int main() {
    int n;
    do {
        scanf("%d",&n);
    } while(n < 1 || n > 2000000);

    int *arr = new int[n];
    for(int i = 0; i < n; i++)
        scanf("%d", &*(arr + i));

    // Insertion sort
    int flag = 0;
    for(int i = 1; i < n; i++) {
        int index = *(arr + i);
        int dec = i;

        while(dec > 0 && *(arr + dec - 1) >= index) {
            *(arr + dec) = *(arr + dec - 1);
            --dec;
            flag++;
        }
        *(arr + dec) = index;
    }

    printf("%d", flag);
      
    return 0;
}

Ще се надявам да предложите нещо. Може и с друг алгоритъм за сортиране, вероятно, въпросът е да мога да преброя инверсиите правилно за отрицателно време.

 

[StormBreaker]

Секунди?!?

Нещо такова например:

int inversions = 0;
for (int i = 1; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (arr[i] > arr[j])
inversions++;
}
}

 

[misho]

Бавно е това - почти 3 секунди. В крайна сметка стигнах до тук (0.672s / 16900KB):

#include<iostream>
#include<cstdio>

long counter = 0;

// MAGIC;)
void magic(int* left, int* right, int leftLength, int rightLength, int *buffer) {
      int leftFirst = 0, rightFirst = 0, resultIter = 0;

      while((leftLength > leftFirst) || (rightLength > rightFirst)) {
            if(leftLength > leftFirst && rightLength > rightFirst) {
                  if(*(left + leftFirst) <= *(right + rightFirst)) {
                        *(buffer + resultIter) = *(left + leftFirst);
                        leftFirst++;
                        resultIter++;
                  }
                  else {
                        *(buffer + resultIter) = *(right + rightFirst);
                        rightFirst++;
                        resultIter++;
                        counter += leftLength - leftFirst;
                  }
            }
            else if(leftLength > leftFirst) {
                  *(buffer + resultIter) = *(left + leftFirst);
                  leftFirst++;
                  resultIter++;
            }
            else if(rightLength > rightFirst) {
                  *(buffer + resultIter) = *(right + rightFirst);
                  rightFirst++;
                  resultIter++;
            }
      }

      for(int i = 0; i < leftLength; i++)
            *(left + i) = *(buffer + i);
      for(int i = 0; i < rightLength; i++)
            *(right + i) = *(buffer + leftLength + i);
}

// Merge sort
void mergeSort(int *arr, int length, int *buffer) {
      if(length <= 1)
            return;

      int middle = length/2;
      int *left = arr;
      int *right = arr + middle;

      mergeSort(left, middle, buffer);
      mergeSort(right, length - middle, buffer);

      magic(left, right, middle, length - middle, buffer);
}

int main() {
   int n;
   do {
       scanf("%d",&n);
   } while(n < 1 || n > 2000000);

   int *arr = new int[n];
      int *result = new int[n];
   for(int i = 0; i < n; i++)
       scanf("%d", arr + i);

   // Merge sort
   mergeSort(arr, n, result);

   printf("%d", counter);
   return 0;
}

 

[perer]

А защо не опиташ метода на мехурчето или още по-ефективния метод на шейкъра? Те са сравнително бързи.