У меня есть три сортировки. Как подсчитать в каждой их них кол-во пересылок и сравнений?

Question

[Muriam]

Пояснение, что такое пересылки и сравнения:
На каждом шаге итерации два элемента сравниваются - это СРАВНЕНИЕ,
и если, к примеру левый > правого, то они переставляются местами (или наоборот, зависит от вида сортировки) - это ПЕРЕСЫЛКА.
То есть пересылка - это когда два элемента меняются местами.

#include <iostream>
#include <cstdlib>
#include <locale>
#include <conio.h>
#define SIZE 10

using namespace std;

void random_array(int array[SIZE]);
void bubble_sort(int array[SIZE]);
void select_sort(int array[SIZE]);
void shaker_sort(int array[SIZE]);


int main() 
{
    setlocale(LC_ALL, "rus");
    
    int array[SIZE];
      
    random_array(array);    
    bubble_sort(array); 
    for (int i = 0; i <= SIZE-1; i++) 
        cout << array[i] << " ";
    cout << "\n\n";

    random_array(array);
    select_sort(array); 
    for (int i = 0; i <= SIZE-1; i++) 
        cout << array[i] << " ";
    cout << "\n\n";
    
    random_array(array);
    shaker_sort(array);
    for (int i=0; i <= SIZE-1; i++)
        cout << array[i] << " ";
    cout << "\n\n";
    
     
    getch();
    return 0;
}

void random_array(int array[SIZE])
{
    cout << "исходный массив" << endl;
    for (int i=0; i<SIZE; i++) 
    {
        array[i] = rand()%100;
        cout << array[i] << " ";
    }
}

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

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

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

Comments

[Антон Федорян]

завести переменную-счетчик?

[Muriam]

Антон Федорян, ну, скорей всего да, но как это сделать в коде?

[Saboteur]

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

[Антон Федорян]

код найти удалось, а что с ним делать - непонятно... так?

[Muriam]

Антон Федорян, это мой код

Answer 1

[Антон Федорян]

void bubble_sort(int array[SIZE])
{
	int transfer = 0;
	int comparison = 0;

	cout << "\nпузырьковая сортировка" << endl;       
	for (int i = 0; i < SIZE-1 ; i++)
	{
		for (int j = SIZE-2; j >= i; j--)
		{
			comparison++;
			if (array[j] > array[j+1]) 
			{
				int temp = array[j];
				array[j] = array[j+1];
				array[j+1] = temp;
				transfer++;
			}
		}
	}

	cout << "СРАВНЕНИЕ " << comparison << endl;
	cout << "ПЕРЕСЫЛКА " << transfer << endl;
}