Inwersje- main2

0

Witam.
Piszę w sprawie zadania inwersje ( https://main2.edu.pl/c/kurs-podstaw-algorytmiki-druga-e/p/inw/ ), ponieważ mój program działa za wolno..
Zastosowałem w nim algorytm MergeSort i sortowanie bąbelkowe w wyliczania ile razy program się wykonał.
Mógłbym prosić o nakierowanie jak przyśpieszyć mój program?Z góry dziękuje

#include <cmath>
#include <iostream>
#include <iomanip>
#include <cstdlib>

using namespace std;

long long A[1000000],B[1000000];

void MergeSort(int p, int q)
{
    if (p==q)
        return;
    int s = (p + q) / 2;
    MergeSort(p, s);
    MergeSort(s+1, q);

    int i = p;
    int j = s+1;
    for (int k = p; k <= q; k++)
        if (j>q || ( i<=s && A[i] < A[j] ) )
        {
           B[k] = A[i];
           i++;
        } else
        {
           B[k] = A[j];
           j++;
        }
     for(int k = p ; k <= q; k++)
          A[k] = B[k];

}
int main() {
    int n,ilosc=0;
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >>n;
    for (int i=0;i<n;i++) cin>>A[i];

    for(int i=0;i<n-1;i++)
    {
        for(int j= i+1;j<n;j++)
        {
            if(A[i]>A[j])
            {
                ilosc++;
            }
        }
    }
    MergeSort(0,n-1);
    for (int i=0;i<n;i++) cout << A[i]<<" ";
    cout<<"\n"<<ilosc;
    return 0;
}

0

Zoptymalizowałem kod do postaci:

#include <iostream>
#include <algorithm>

using namespace std;

long long A[1000000],B[1000000];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,ilosc=0;
    cin>>n;
    for (int i=0;i<n;i++) cin>>A[i];
    for(int i=0;i<n-1;i++) for(int j=i+1;j<n;j++) if(A[i]>A[j]) ilosc++;
    sort(A, A + n);
    for (int i=0; i<n; i++) cout << A[i]<<" ";
    cout<<'\n'<<ilosc;
    return 0;
}

A i tak program działa za wolno:
5a Przekroczenie limitu czasu 3.00s/3.00s 0/14
5b Przekroczenie limitu czasu 3.00s/3.00s
6a Przekroczenie limitu czasu 3.01s/3.00s 0/15
6b Przekroczenie limitu czasu 3.01s/3.00s
6c Przekroczenie limitu czasu 3.01s/3.00s
7a Przekroczenie limitu czasu 3.03s/3.00s 0/15
7b Przekroczenie limitu czasu 3.02s/3.00s
7c Przekroczenie limitu czasu 3.01s/3.00s

Ma ktoś jakiś pomysł, jakąś rade?

2

Używasz najprostszego podejścia o złożoności czasowej O(n^2), przy ilości elementów 300000 jest to za wolne.
Możesz wykorzystać Enhanced Merge Sort o złożoności O(n log n)
http://www.geeksforgeeks.org/counting-inversions/

0

Dziękuje!
Enhanced Merge Sort w tej sytuacji pomógł!
Jeszcze raz dziękuje, pozdrawiam!

1 użytkowników online, w tym zalogowanych: 0, gości: 1