Как корректно вывести на экран кол-во пересылок и сравнений в пузырьковой сортировке массива?

Question

[Muriam]

Как сделать чтоб кол-во сравнений и пересылок отображались после отсортированного пузырьком массива,
а не между надписью "пузырьковая сортировка" и последовательностью "0 24 34 41 58 62 64 67 69 78"?
Текущий вывод:

#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 comparison = 0;
    int transfer = 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;
}

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]

Герман, Roman подскажите как исправить. По-моему тут есть баг.

В этом моем вопросе обратите внимание на вывод массива на экран (см выше). Это результат после компиляции неделю назад.
А теперь я создала другой файл .cpp, скопировала туда этот же код, снова скомпилировала и рандомный массив сгенерировал такие же числа (см. картинка ниже).



Как исправить этот баг, чтобы при каждой компиляции генерировался новый рандомный массив, а не одинаковый, как и в прошлый раз?

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

[Имя]

Добавьте в начале
#include <ctime>

Измените функцию так:

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

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

Answer 1

[Имя]

У тебя сначала вызывается функция в которой и выводятся эти данные и после её завершения выводится сам массив.

1. Вынести cout'ы в функцию main и сделать переменные считающие данные в глобальную область.
2. Передавать 2 перемененные в функцию по ссылке и затем в main'e выводить после вывода массива.
3. Выводить массив в функции.

Comments

[Muriam]

Герман, Roman что-то я совсем запуталась.
Подскажите, что в моем коде не правильно.
Вроде бы должно получиться: сравнений 45, пересылок 18 (см картинку в вопросе).
Извиняюсь за смещение отступов.

#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], int *comparison, int *transfer);


int main() 
{
    setlocale(LC_ALL, "rus");
    
    int array[SIZE];
    int compar;
    int transf;
      
    random_array(array);    
    bubble_sort(array, &compar, &transf); 
    for (int i = 0; i <= SIZE-1; i++) 
        cout << array[i] << " ";
    cout << "\n";    
    cout << "сравнений " << compar << endl;
    cout << "пересылок " << transf << endl;
    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 *comparison, int *transfer)
{
    //*comparison = 0;
    //*transfer = 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;
}

[Roman]

Мария, Могло быть хуже.
С++ же.

// ...
void bubble_sort(int array[SIZE], int& comparison, int& transfer); // по ссылке
// ...
int compar = 0;
int transf = 0;
bubble_sort(array, compar, transf); 
// ...

[Muriam]

Roman, спасибо большое.

[Muriam]

Герман и вам тоже спасибо, идея то ваша.
Если исправить так, как указано через одно сообщение выше - все работает.

[Roman]

Мария, Решений может быть несколько. Кроме того, Герман, вам так и написал "2. Передавать 2 перемененные в функцию по ссылке...". Справедливости ради, этот ответ нужно отметить решением.

[Muriam]

Roman, согласна.

Answer 2

[Roman]

Как-то так:

#include <iostream>
#include <map>
#include <string>
#include <iomanip>
using namespace std;


void swap(int& a, int& b)
{
  int c = a;
  a = b;
  b = c;
}

struct info
{
  int swapCount = 0;
  int compCount = 0;
};

class Counter
{
  public:
    static Counter& Instance()
    {
      static Counter tsCounter;
      return tsCounter;
    }

    info& getCount(string fn)
    {
      return callCount[fn];
    }

    void print()
    {
      for(auto& a : callCount)
      {
        cout << a.first   << "\n"
             << setw(15) << left << "swap: " << a.second.swapCount << "\n"
             << setw(15) << left << "compare: " << a.second.compCount << "\n";
      }
      cout.flush();
    }

  private:
    map<string, info> callCount;
    Counter(){}
    Counter(const Counter&) = delete;
    Counter& operator=(const Counter&) = delete;
};

void mysort(int* a, size_t sz)
{
  for(int i = 0; i < sz - 1; ++i)
  {
    int minIdx = i;
    for(int j = i + 1; j < sz; ++j)
    {
      if(a[j] < a[minIdx]) minIdx = j;
    }
    swap(a[i], a[minIdx]);
    Counter::Instance().getCount(__FUNCTION__).swapCount++;
  }
}


int main()
{
  int a[] = {2, 5, 6, 77, 1, 32, 45, 77, 12, 13, 14, 15};
  mysort(a, sizeof(a)/sizeof(int));
  Counter::Instance().print();
}

Comments

[Muriam]

Пример с ООП - это интересно, пригодится, чтоб понять другую парадигму.

ответ компилятора:


он остановился на строке ф-ции print:
for(auto& a : callCount)

[Roman]

Мария, range based for С++11

[Muriam]

Roman, похоже мне надо поискать другую IDE, DEV-C++ не поддерживает стандарт 2011 года.

[Roman]

Мария, C++98

void print()
{
  map<string, info>::iterator it = callCount.begin();
  while(it != callCount.end())
  {
    cout << it->first   << "\n"
         << setw(15) << left << "swap: " << it->second.swapCount << "\n"
         << setw(15) << left << "compare: " << it->second.compCount << "\n";
    ++it;
   }
   cout.flush();
}

[Muriam]

Roman, больше спасибо, все работает.

Сначала попробую доделать свою программу, потом отмечу лучший ответ.