@Muriam

Как посчитать кол-во сравнений и пересылок в сортировке методом прямого выбора?

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++;                                           // инкремент пересылок
            }                                                  
        }   
}


этот же код, но более ровные отступы:

5ca9fffec95a7563229345.png

ПОНЯЛА В ЧЕМ ОШИБКА, нужно убрать ; после параметров ф-ции. Теперь компилируется.
Но теперь мне кажется. что количество пересылок и сравнений считается не правильно.

Как посчитать кол-во сравнений и пересылок в сортировке методом прямого выбора?

компилируемая версия этого кода:
#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;
}
  • Вопрос задан
  • 2442 просмотра
Решения вопроса 1
@res2001
Developer, ex-admin
Уже в который раз вижу ваши одинаковые посты, вроде ответы были, но похоже не помогает.

1.У вас ошибка в реализации. Нужно так:
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++;						  // инкремент пересылок
  }

Привел только тело цикла.
Вот тут показана правильная реализация
2.Количество сравнений и пересылок для этого алгоритма легко определяется аналитически (не надо ничего считать в самом алгоритме):
2.1. Количество сравнений находится по формуле суммы n первых членов арифметической прогрессии: Sn = (a1+an)/2*n. Где a1 = 1, an = SIZE-1, n = SIZE-1
2.2. Количество пересылок всегда равно SIZE-1
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы