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

Question

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

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



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

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

компилируемая версия этого кода:

#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;
}

Comments

[Saboteur]

Считается правильно.
Возможно у вас алгоритм сортировки неправильно написан.

Answer 1

[res2001]

Уже в который раз вижу ваши одинаковые посты, вроде ответы были, но похоже не помогает.

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

Comments

[Muriam]

Кол-во пересылок не может быть равно на 1 элемент меньше размера массива и все время фиксировано.

[res2001]

Мария, В приведенной выше реализации именно так и будет всегда.
Но если добавить проверку на то что первый элемент он же минимальный, то уже да, не может:

if(min == i) continue;
      temp = array[i];                                     //
      array[i] = array[min];                             // меняю их местами
      array[min] = temp;                                 //

В этом случае количество пересылок будет плавать и SIZE-1 - это будет худший вариант.

[Muriam]

Там была пузырьковая сортировка, а здесь другая. Так что это не одно и то же.
Вы привели тело цикла, такое же, как у меня.

У меня по-моему не правильно генерируется массив, спросила об этом в вопросе:
Как корректно вывести на экран кол-во пересылок и сравнений в пузырьковой сортировке массива?

[Muriam]

res2001 вопрос генерации массива решен Почему при компиляции рандомного массива, при каждой последующей компиляции и запуске, отображаются те же цифры, а не генерируются новые?

[Muriam]

res2001, кажется примерно так:



пересылки посчитаны кол-ом итераций внешнего цикла,
сравнения по формуле ниже:

[Muriam]

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

(только количество элементов нужно взять 5, а не 10, чтоб меньше считать)

[res2001]

Мария,

Вы привели тело цикла, такое же, как у меня.

Нет не такое. Я перенес закрывающую скобку внутреннего цикла выше, именно в этом и состояла ваша ошибка.

На счет С = (n^2-n)/2 - эта формула напрямую выводится из формулы суммы n первых членов арифметической прогрессии, которую я указал. Если в формулу суммы подставить n=SIZE-1, a1=1, an = n и упростить. Просто я не стал заморачиваться - формула и так достаточно проста.

На счет M=3(n-1) - я давал значение n-1. Похоже, что в формуле 3(n-1) они считали каждую пересылку, т.е. 3 этих операции учитываются отдельно, отсюда множитель 3:

temp = array[i];
array[i] = array[min];
array[min] = temp;

Я же считал все три операции, как одну, коей они и являются по смыслу, поэтому у меня нет 3.
Кроме того в теории оценки сложности алгоритмов константные множители отбрасываются. Так что, думаю, что мой подход все таки правильней.

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

Гениально! Если бы вы это сделали сразу, вам, возможно не пришлось бы тут задавать вопросы :-)

[Muriam]

res2001, слушайте, где задаю вопросы - это не ваше дело. Если нравится самоутверждаться путем унижения других - поищите другое место.

[res2001]

Мария, Ок. Поставьте мой ответ решением, это будет справедливо, и разойдемся :-)

[Muriam]

res2001, нет.

[res2001]

Мария, :-)
Желаю удачи!

[Muriam]

res2001, Ок. Ведь диалог с вами привел (почти) к решению.

1. Выбираем элемент с min значением и помещаем в a[0]
2. Снова выбираем элемент с min значением из оставшихся несортированных элементов и помещаем его в a[1]
3. И т.д., с каждым несортированным элементом, до конца.

Пересылки считаются правильно. А сравнения - не знаю, но можно выяснить это в другой раз, сортировок много ещё видов, тренироваться.