Как посчитать сравнения в выборках? - PullRequest
Новая
       21

Как посчитать сравнения в выборках?

0 голосов
/ 09 апреля 2019

Как считать сравнения в selectionsort?

терминах: когда операторы, которые вы выполняете, чтобы найти максимальное значение, 'истинны', тогда сравнивайте счет.

Значение, чтобы получить максимальноезначение хранится в первом элементе массива, а не в случайном порядке.

Я пытаюсь с изменением позиции счетчика переменной C - не работает новая переменная 'first', first = sort [MAX] вставка первой для цикла, -нет работы 

#include <stdio.h>

int main() {
    int sort[10000], i, n, MAX, temp, count;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
       scanf("%d", &sort[i]);
    }
    for (MAX = 0; MAX < n; MAX++)
        for (i = MAX + 1; i < n; i++) {
            if (sort[MAX] > sort[i]) {
                count++;
                temp = sort[MAX];
                sort[MAX] = sort[i]; 
                sort[i] = temp;
            }
        }

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

Пример ввода 

10
0 7 1 6 7 7 6 6 5 4

Пример вывода 

17

РЕДАКТИРОВАТЬ : новый код: 

#include <stdio.h>
#define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )

int count = 0;

void selection_sort(int list[], int n) {
    int i, j, least, temp;

    for (i = 0; i < n - 1; i++) {
        least = i;

        for (j = i + 1; j < n; j++) {
            if (list[j] < list[least]) {
                least = j;
                count++;
            }
        }
        SWAP(list[i], list[least], temp);
    }
}

int main() {
    int list[10000], i, n;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &list[i]);
    };
    selection_sort(list, n);

    printf("%d", count);
}

как насчет этого?почему этот код тоже не двигался?

Ответы [ 4 ]

3 голосов
/ 09 апреля 2019

Вы не считаете нужную вещь, этот код 

     if(sort[MAX]>sort[i])  
     {
        count++;
         temp=sort[MAX];
         sort[MAX]=sort[i]; 
         sort[i]=temp;
     }

подсчитывает, сколько раз два числа поменялись местами .Но вы хотите посчитать сравнение, поэтому оно должно быть таким: 

     count++;
     if(sort[MAX]>sort[i])  // this is what we are counting
     {
         temp=sort[MAX];
         sort[MAX]=sort[i]; 
         sort[i]=temp;
     }

Другая проблема заключается в том, что вы не даете счетчику начальное значение ноль 

int sort[10000],i,n,MAX,temp,count;

должно быть 

int sort[10000],i,n,MAX,temp,count = 0;
3 голосов
/ 09 апреля 2019

как рассчитать выборку сравнения?

Ваше определение термина странно сформулировано, но, похоже, оно предназначено для того, чтобы сосредоточиться на основных сравнениях алгоритма , в отличие от сравнений, выполняемых случайно для других целей или внутри библиотечных функций.То есть в представленной вами реализации (чью корректность я не оцениваю) вы должны считать каждую оценку sort[MAX]>first, но не MAX<n или i<n.

Вы, похоже, используетедля этой цели переменная count, но вы учитываете только те сравнения, которые имеют значение true.Моя интерпретация проблемы, основанная как на представленной формулировке, так и на моих общих ожиданиях в отношении такой проблемы, заключается в том, что каждая оценка sort[MAX]>first должна учитываться независимо от результата.Этого можно достичь, подняв выражение count++ из блока if, но оставив его во внутреннем цикле for.

Конечно, как отмечает @john, вам нужно инициализироватьcount до 0 перед началом сортировки.Возможно, вам удастся получить это случайно, но начальное значение локальных переменных без инициализатора является неопределенным (по крайней мере), пока не будет присвоено значение.

Я пытаюсь с изменением положения счетчика переменных c -нет работы

новая переменная 'first', first = sort [MAX] вставка первой для цикла, - нет работы

Даже при неправильном увеличении приращения до count, есливаш вид действительно работал, тогда вы ожидаете увидеть некоторые счетчики для большинства входных данных.То, что вы этого не делаете, является хорошим признаком того, что ваш вид на самом деле не работает правильно.Я бы предложил выводить также отсортированные результаты, чтобы вы могли отладить детали алгоритма сортировки.

1 голос
/ 09 апреля 2019

Вы можете абстрагировать сравнение в функцию или макрос, который также увеличивает счетчик.Макро-подход может быть 

#define GT(x,y,counter) (counter++, (x) > (y) ? 1 : 0)
...
if ( GT( sort[MAX], sort[i], count ) == 1 )
{
  // perform swap
}

, тогда как функциональный подход будет 

int gt( int x, int y, int *counter )
{
  (*counter)++;
  if ( x > y )
    return 1;
  return 0;
}
...
if ( gt( sort[MAX], sort[i], &count ) == 1 )
{
  // perform swap
}
0 голосов
/ 13 апреля 2019

Вы подсчитываете количество свопов, а не количество сравнений.

Здесь исправлено без глобальной переменной и нескольких дополнительных проверок: 

#include <stdio.h>
#define SWAP(x, y, temp) ((temp) = (x), (x) = (y), (y) = (temp))

int selection_sort(int list[], int n) {
    int count = 0;
    int i, j, least, temp;

    for (i = 0; i < n - 1; i++) {
        least = i;
        for (j = i + 1; j < n; j++) {
            count++;
            if (list[j] < list[least]) {
                least = j;
            }
        }
        SWAP(list[i], list[least], temp);
    }
    return count;
}

int main() {
    int list[10000], i, n, count;

    if (scanf("%d", &n) != 1 || n > 10000)
        return 1;
    for (i = 0; i < n; i++) {
        if (scanf("%d", &list[i]) != 1)
            return 1;
    }
    count = selection_sort(list, n);

    printf("%d\n", count);
    return 0;
}

Не то чтобы вашАлгоритм всегда будет выполнять одинаковое количество сравнений для любого набора n значений: n * (n - 1) / 2 сравнений, а поскольку вы не проверяете i != least, он будет выполнять n - 1 перестановок.

...