Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
5.5 kB
5
Indexable
Never
#include <iostream>
 
using namespace std;

void inclusion()
{
    int size = 20;
    int arr[size] = {20, 1, 19, 2, 18, 3, 17, 4, 16, 5, 15, 6, 14, 7, 13, 8, 12, 9, 11, 10};
    int comparisons = 0;
    int permutations = 0;
    cout << "Массив ДО сортировки методом прямого включения:" << endl;
    for(int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
    cout <<endl <<endl << "Массив ПОСЛЕ сортировки методом прямого включения:" << endl;
    for (int i = 0; i<size; i++)
    {
        int value = arr[i];
        int index = i;
        
        while ((index > 0) && (arr[index - 1] > value))
        {
            arr[index] = arr[index - 1];
            index --;
            
            permutations += 1;
            comparisons += 1;
        }
        
        arr[index] = value;
        
        comparisons += 1;
    }
   
    for (int i = 0; i < size; i++)
    {
      cout << arr[i] << " ";
    }
    cout << endl;
    cout << endl << "перестановки - " << permutations;
    cout << endl << "сравнения - " << comparisons << endl;
}

void selection()
{
  int size = 20;
  int arr[size] = {20, 1, 19, 2, 18, 3, 17, 4, 16, 5, 15, 6, 14, 7, 13, 8, 12, 9, 11, 10};
  int comparisons = 0;
  int permutations = 0;
  int min, temp; // для поиска минимального элемента и для обмена
  cout << "Массив ДО сортировки методом прямого выбора:" << endl;
    for(int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
  cout <<endl <<endl << "Массив ПОСЛЕ сортировки методом прямого выбора:" << endl;
  for (int i = 0; i < size - 1; i++) 
  {
    min = i; // запоминаем индекс текущего элемента
    // ищем минимальный элемент чтобы поместить на место i-ого
    for (int j = i + 1; j < size; j++)  // для остальных элементов после i-ого
    {
      if (arr[j] < arr[min]) // если элемент меньше минимального,
        {
        min = j; // запоминаем его индекс в min
        comparisons += 1;
        }
        else{
        comparisons += 1;}
        
    }
        
    temp = arr[i];      // меняем местами i-ый и минимальный элементы
    arr[i] = arr[min];
    arr[min] = temp;
    
    permutations += 1;
  }
 
    for (int i = 0; i < size; i++)
    {
      cout << arr[i] << " ";
    }
    cout << endl;
    cout << endl << "перестановки - " << permutations;
    cout << endl << "сравнения - " << comparisons << endl;
}

void bubble()
{
  int size = 20;
  int arr[size] = {20, 1, 19, 2, 18, 3, 17, 4, 16, 5, 15, 6, 14, 7, 13, 8, 12, 9, 11, 10};
  int comparisons = 0;
  int permutations = 0;
  cout << "Массив ДО сортировки методом пузырька:" << endl;
    for(int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
  cout <<endl <<endl << "Массив ПОСЛЕ сортировки методом пузырька:" << endl;
  // Для всех элементов
  for (int i = 0; i < size - 1; i++)
  {
    for (int j = (size - 1); j > i; j--) // для всех элементов после i-ого
    {
    if (arr[j - 1] > arr[j]) // если текущий элемент меньше предыдущего
      {
        int temp = arr[j - 1]; // меняем их местами
        arr[j - 1] = arr[j];
        arr[j] = temp;
        permutations += 1;
      }
     comparisons += 1;
    }
  }
    for (int i = 0; i < size; i++)
    {
      cout << arr[i] << " ";
    }
    cout << endl;
    cout << endl << "перестановки - " << permutations;
    cout << endl << "сравнения - " << comparisons << endl;
}

void Shell()
{
  int size = 20;
  int arr[size] = {20, 1, 19, 2, 18, 3, 17, 4, 16, 5, 15, 6, 14, 7, 13, 8, 12, 9, 11, 10};
  int comparisons = 0;
  int permutations = 0;
  int d = 4;
  cout << "Массив ДО сортировки методом Шелла:" << endl;
    for(int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
    cout <<endl <<endl << "Массив ПОСЛЕ сортировки методом Шелла:" << endl;
  while (d > 0)
  {
      for (int i = d; i < size; i++)
      {
          int index = i;
          int value = arr[i];
          while ((index >=d) && (arr[index - d] > value))
          {
              arr[index] = arr [index - d];
              index = index - d;
              permutations += 1;
              comparisons += 1;
          }
          arr[index] = value;
          comparisons += 1;
      }
      if (d/2 != 0)
        d = d/2;
      else if (d == 1)
        d = 0;
      else
        break;
  }
    for (int i = 0; i < size; i++)
    {
      cout << arr[i] << " ";
    }
    cout << endl;
    cout << endl << "перестановки - " << permutations;
    cout << endl << "сравнения - " << comparisons;
}
 
int main()
{
    inclusion();
    cout << "==================================================" << endl;
    selection();
    cout << "==================================================" << endl;
    bubble();
    cout << "==================================================" << endl;
    Shell();
    
    return 0;
}