VPF::Подсчёт инверсий с помощью MergeSort

Abbath1349

Дата 21.6.2012, 14:29 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 214
Регистрация: 16.6.2010

Репутация: нет
Всего: нет

Я пытаюсь реализовать алгоритм подсчет инверсий через сортировку слиянием может кто нибудь подсказать где у меня ошибка?

Код


#include <iostream>
#include <queue>
using namespace std;
class merge_sort
{
public:
    int mergesort(int arr[],int low,int high);
private:
    int merge(int arr[],int left,int middle,int right);

};
int main()
{
    int arr[]={5, 4, 1, 3, 2};
    merge_sort ms;
    int counter=ms.mergesort(arr,0,4);
    for(int i=0;i<5;i++)
        printf("%d \n",arr[i]);
    printf("%d",counter);
    system("pause");
return 0;
};
int merge_sort::mergesort(int arr[],int low,int high)
{
    int middle;
    int counter=0;
    if(low<high)
    {
        middle=(low+high)/2;
        counter+=mergesort(arr,low,middle);
        counter+=mergesort(arr,middle+1,high);
        counter+=merge(arr,low,middle,high);
    }
    return counter;
}
int merge_sort::merge(int arr[],int left,int middle,int right)
{
    queue<int> buffer1,buffer2;
    int counter=0;
    int i;
    for(i=left;i<=middle;i++) buffer1.push(arr[i]);
    for(i=middle+1;i<=right;i++)buffer2.push(arr[i]);
    i=left;
    while(!buffer1.empty() &&!buffer2.empty())
    {
        if(buffer1.front()<=buffer2.front())
        {
            arr[i++]=buffer1.front();
            buffer1.pop();
            
        }
        else
        {
            arr[i++]=buffer2.front();
            buffer2.pop();
            counter++;
        }
    }
    while (!buffer1.empty())
    {
        arr[i++]=buffer1.front();
        buffer1.pop();
    }
    while (!buffer2.empty())
    {
        arr[i++]=buffer2.front();
        buffer2.pop();
    }
    return counter;
}

Это сообщение отредактировал(а) Abbath1349 - 21.6.2012, 14:30

maxdiver

Дата 21.6.2012, 14:39 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

В функции merge() делать просто "counter++" неправильно. То, что мы берём элемент из buffer2, не означает, что мы обнаружили _ровно_одну_инверсию_. На самом деле, при этом обнаруживается buffer1.size() инверсий: т.е. все элементы первой половины, которые больше текущего, образуют с ним инверсию.
В остальном вроде правильно.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »