Liczenie inwersji poprzez merge sort

Odpowiedz Nowy wątek
2016-04-03 15:02
0

Moim problemem nie jest samo działanie kodu, gdyż po paru testach wszystko działa tak jak należy, niestety doszedłem do prawidłowego wyniku metodą prób i błędów.Z tego właśnie powodu nie mogę zrozumieć jak działa linijka którą samemu napisałem.
Oczywiście próbowałem debugować krok po kroku ale dalej nie wiem jakim cudem mój kod działa poprawnie.Nadmienię, że nie chce pisać innego kodu ani też brać kod od kogoś.Chciałbym jedynie zrozumieć jedną z linijek mojego kodu.
A dokładniej o tę count += (q+j-k); .Z góry dziękuje za pomoc w zrozumieniu tej linijki.

#include <iostream>

using namespace std;

int lowhalflength(int p, int q)
{
    return q - p + 1;
}

int highhalflength(int q, int r)
{
    return r - q;
}

int merge(int array[], int p, int q, int r, int lowhalf[], int highhalf[])
{
    int k = p;
    int i;
    int j;
    int count = 0;
    for (int i = 0; k <= q; i++ , k++)
    {
        lowhalf[i] = array[k];
    }
    for (int i = 0; k <= r; i++ , k++)
    {
        highhalf[i] = array[k];
    }

    k = p;
    i = 0;
    j = 0;

    while (i <= (q - p) && j <= r - (q + 1))
    {
        if (lowhalf[i] <= highhalf[j])
        {
            array[k] = lowhalf[i];
            i++;
        }
        else
        {
            array[k] = highhalf[j];
            j++;
            count += (q+j-k);
            ;
        }

        k++;
    }

    while (i < lowhalflength(p, q))
    {
        array[k] = lowhalf[i];
        k++;
        i++;
    }

    while (j < highhalflength(q, r))
    {
        array[k] = highhalf[j];
        k++;
        j++;
    }

    return count;
}

int mergeSort(int array[], int p, int r)
{
    int q = ((p + r) / 2);
    int* lowhalf = new int[lowhalflength(p, q)];
    int* highhalf = new int[highhalflength(q, r)];

    int count = 0;
    if (p < r)
    {
        q = ((p + r) / 2);
        count = mergeSort(array, p, q);
        count += mergeSort(array, q + 1, r);
        count += merge(array, p, q, r, lowhalf, highhalf);
    }
    delete[] lowhalf;
    delete[] highhalf;
    return count;
}

int main()
{
    int* wsk = new int[10];
    int* temp = wsk;
    *wsk++ = 10;

    for (int i = 1; i < 10; i++)
    {
        *wsk++ = i;
    }
    wsk = temp;

    for (int i = 0; i < 10 ; i++) cout << *wsk++ << endl;
    wsk = temp;
        cout << endl << endl;
    cout << (mergeSort(wsk, 0, 9)) << endl;
    cout << endl << endl;
    wsk = temp;
    for (int i = 0; i < 10; i++) cout << wsk[i] << endl;

    delete[] wsk;

    getchar();
    getchar();

    return 0;
}

Pozostało 580 znaków

2016-04-03 15:39
0

Mi wygląda na to, że ten count nie jest do niczego potrzebny, bo nigdzie go nie używasz i program również zadziała bez niego.

Pozostało 580 znaków

2016-04-03 15:44
Wybitny Młot
0
szweszwe napisał(a):

Mi wygląda na to, że ten count nie jest do niczego potrzebny, bo nigdzie go nie używasz i program również zadziała bez niego.

Jak to nigdzie go nie używam jak go używam?

Racja, zaraz popatrzę w takim razie :D - szweszwe 2016-04-03 15:54
@szweszwe dziękuje Ci bardzo, liczę na Twoją pomoc :) - Charllie 2016-04-03 19:25

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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