VPF::Подсчет сравнений в QuickSort - Форум программистов

Abbath1349

Дата 5.7.2012, 21:27 (ссылка)

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

Загрузка ...

Бывалый

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

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

Пытаюсь реализовать подсчет сравнений в quickSort испробовал 2 варианта первый подсчитывать перед сравнением(comparisons) второй подсчитывать количество элементов(counter), но оба выдают неправильный результат подскажите где ошибка?

Код


#include <iostream>
#include <math.h>
using namespace std;
class Quicksort
{
public:
    int sort(int arr[],int left,int right);
    int numbers;
private:
    int partition(int arr[],int left ,int right);
};

int main()
{
    int arr []={0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    Quicksort qs;
    qs.numbers=0;
    int counter=qs.sort(arr,0,9);
    printf("\nIt has %d comparisons",qs.numbers);
    printf("\nIt has %d comparisons",counter);
    system("pause");
return 0;
};

int Quicksort::sort(int arr[],int left ,int right)
{
    int p;
    int counter=0;
    if(left<right)
    {
        counter+=right-left;
        p=partition(arr,left,right);
        counter+= sort(arr,left,p-1);
        counter+=sort(arr,p+1,right);
    }
    return counter;
}
int Quicksort::partition(int arr[],int left ,int right)
{

    int p=arr[left];
    int i=left+1;
    int comparisons=0;

    for(int j=left+1;j<=right;j++)
    {
        comparisons++;
        if(arr[j]<p)
        {
            swap(arr[j],arr[i]);
            i++;            
        }
    }
    numbers+=comparisons;
        swap(arr[left],arr[i-1]);
    return i;
}

disputant

Дата 6.7.2012, 12:14 (ссылка)

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

Загрузка ...

Бывалый

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

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

Что-то вы странное суммируете, как на мой взгляд... Например, откуда это: counter+=right-left;?

Я бы все сравнения реализовал - если уж так приспичило считать smile

- через функцию сравнения с подсчетом количества вызовов.

И - во обязательно именно ваш код? Можно легко посчитать количество вызовов в библиотечной сортировке - sort или qsort - просто дописав компаратор...

Abbath1349

Дата 6.7.2012, 21:21 (ссылка)

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

Загрузка ...

Бывалый

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

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

Цитата(disputant @ 6.7.2012, 12:14)

counter+=right-left; Это сколько элементов будет сравниваться этот вариант наиболее быстрый.
Да именно в этом коде. Если подсчитывать количество вывозов функции сравнения ответ будет такой же.
Например тест 9, 6, 3, 7, 2, 4 должен выдавать 11 у меня считает 13.

disputant

Дата 7.7.2012, 06:59 (ссылка)

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

Загрузка ...

Бывалый

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

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

Что значит "Должно выдавать"? Как написан код, так и выдает. Руками прогонять пробовали?

Кстати, реально их 22 - вы же еще постоянно сравниваете left и right в sort smile

Abbath1349

Дата 7.7.2012, 13:40 (ссылка)

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

Загрузка ...

Бывалый

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

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

Цитата(disputant @ 7.7.2012, 06:59)

код был неправильным ошибку нашол) функция partition должна возвращать i-1

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