M
M
Muriam2019-03-29 13:49:42
C++ / C#
Muriam, 2019-03-29 13:49:42

I have three sorts. How to calculate the number of transfers and comparisons in each of them?

An explanation of what transfers and comparisons are:
At each iteration step, two elements are compared - this is COMPARISON,
and if, for example, left > right, then they are rearranged (or vice versa, depending on the type of sorting) - this is TRANSFER.
That is, a forwarding is when two elements are swapped.

#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;                           // запоминаю границу
  }
}

Answer the question

In order to leave comments, you need to log in

1 answer(s)
A
Anton Fedoryan, 2019-03-29
@Muriam

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

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question