M
M
Muriam2019-04-07 16:46:33
C++ / C#
Muriam, 2019-04-07 16:46:33

How to count the number of comparisons and transfers in a direct selection sort?

void select_sort(int array[SIZE], int &comparison2, int &transfer2);
{    
    int min, temp;
        
    cout << "\nсортировка методом прямого выбора" << endl;       
        for (int i = 0; i < SIZE-1; i++) 
  { 
      min = i;                                                    // индекс минимального элемента
      for (int j = i+1; j < SIZE; j++)
      {
                comparison2++;                                   // инкремент сравнений 
          if (array[j] < array[min])                       // если текущий элемент меньше минимального 
                {           
        min = j;                                           // запоминаю его индекс
                }                  
      temp = array[i];                                      //
      array[i] = array[min];                              // меняю их местами
      array[min] = temp;                                 //
      transfer2++;                                           // инкремент пересылок
            }                                                  
        }   
}

the same code, but more even indents:
5ca9fffec95a7563229345.png
UNDERSTAND WHERE THE ERROR, you need to remove ; after the parameters of the function. Now it compiles.
But now it seems to me. that the number of transfers and comparisons is considered incorrect.
How to count the number of comparisons and transfers in a direct selection sort?
compiled version of this code:
#include <iostream>
#include <cstdlib>
#include <locale>
#include <conio.h>
#define SIZE 10


using namespace std;

int main()
{
   setlocale(LC_ALL, "rus");
  
    int array[SIZE];
    int transfer = 0;
    int comparison = 0;  
    int min, temp;
    
    cout << "\nсортировка методом прямого выбора" << endl;       
  for (int i = 0; i < SIZE-1; i++) 
  { 
      min = i;                                           // индекс минимального элемента
      for (int j = i+1; j < SIZE; j++)
      {
                comparison++;                                  // инкремент сравнений
          if (array[j] < array[min])                     // если текущий элемент меньше минимального 
                {           
         min = j;                                        // запоминаю его индекс
                }                  
      temp = array[i];                                     //
      array[i] = array[min];                             // меняю их местами
      array[min] = temp;                                 //
      transfer++;						  // инкремент пересылок
            }
  }


   cout << "сравнений " << comparison << endl;
   cout << "пересылок " << transfer << endl;
  
   getch();
   return 0;
}

Answer the question

In order to leave comments, you need to log in

1 answer(s)
R
res2001, 2019-04-07
@Muriam

For the umpteenth time I see your identical posts, like there were answers, but it does not seem to help.
1. You have an implementation error. Need like this:

for (int i = 0; i < SIZE-1; i++) 
  { 
      min = i;                                           // индекс минимального элемента
      for (int j = i+1; j < SIZE; j++)
      {
                comparison++;                                  // инкремент сравнений
          if (array[j] < array[min])                     // если текущий элемент меньше минимального 
                {           
         min = j;                                        // запоминаю его индекс
                }                  
            }
      temp = array[i];                                     //
      array[i] = array[min];                             // меняю их местами
      array[min] = temp;                                 //
      transfer++;						  // инкремент пересылок
  }

Brought only the body of the cycle.
Here is the correct implementation
. 2. The number of comparisons and transfers for this algorithm is easily determined analytically (no need to calculate anything in the algorithm itself):
2.1. The number of comparisons is found using the formula for the sum of the first n members of an arithmetic progression: Sn = (a1+an)/2*n. Where a1 = 1, an = SIZE-1, n = SIZE-1
2.2. The number of transfers is always equal to SIZE-1

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question