void select(int* a, int K, long double* movents, long double* compasion) { int i, j, k; int x; for (i = 0; i < K; i++) // i - номер текущего шага { k = i; x = a[i]; (*compasion)++; for (j = i + 1; j < K; j++) // цикл выбора наименьшего элемента if (a[j] < x) { k = j; x = a[j]; *compasion = *compasion + 2;// k - индекс наименьшего элемента } a[k] = a[i]; a[i] = x; (*movents)++; } }

After sorting 10,000 elements, the number of movements also turned out to be 10,000; Is it really so? How to most accurately calculate the displacement and comparison?

  • 3
    How could it be otherwise? You insert by moving the item into place. Even if it is already there :) Do you have an increase in movents (by the way, why ?? !!! did you make floating-point counters? !!) at the end of the cycle, of course - you can just immediately increase by K ... Yes, and you have comparisons somehow strangely counted - an increase only if less, but then by 2 at once ... - Harry
  • You have *movents increased by K regardless of everything else. - Enikeyschik
  • @ Harry, made floating, otherwise on arrays with dimensions of 50,000 overflow int occurs - Elvin
  • @Harry, how would it be better to arrange them? - Elvin
  • Well, take a long long , but with a floating point - you will still start to lose this unit at certain values ​​... - Harry

1 answer 1

Well, I would do this:

 #include <stdlib.h> #include <stdio.h> #include <string.h> void select(int *a, int K, long long *moves, long long *comps) { int i, j, k; int x; *comps = *moves = 0; for (i = 0; i < K; i++) { // i - номер текущего шага k = i; x = a[i]; for (j = i + 1; j < K; j++) // цикл выбора наименьшего элемента { (*comps)++; if (a[j] < x) { k = j; x = a[j]; } } (*comps)++; if (a[k] != a[i]) { a[k] = a[i]; a[i] = x; (*moves)++; } } } void check(int *a, int K) { for(int i = 0; i < K-1; ++i) if (a[i] > a[i+1]) { printf("Sorting error!\n"); exit(1); } } int main() { #define COUNT 20000 int a[COUNT]; long long cs, ms; for(int i = 0; i < COUNT; ++i) a[i] = rand(); select(a,COUNT,&ms,&cs); check(a,COUNT); printf("Moves: %lld, compares: %lld\n",ms,cs); }

PS You can immediately give the number of comparisons as K*(K+1)/2 ...

  • exchange then why in the internal cycle included? And the second time comps increase why? - Fat-Zer 5:59 pm
  • @ Fat-Zer Ochenyat when adding to the author's code. Thanks for corrections. Comparisons - because I think ALL comparisons, comparisons to find out if a move is needed are also. It still does not affect the appearance of O (N ^ 2) ... - Harry
  • then the comparisons from the cycles are forgotten ... and if they are taken into account, they are usually considered separately comparing the data and comparing the indices ... - Fat-Zer
  • @ Fat-Zer Consider comparing data . This is better (and less movement). - Harry
  • lol, all for the sake of justifying the comparison =))) - Fat-Zer