Question

СРОЧНО РЕШИТЕ ЗАДАЧУ НА С++ ДАЮ 30 БАЛЛОВ Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива. Формат входных данных На первой строке дано целое число n (1≤n≤1000) — количество элементов в массиве. На второй строке — сам массив. Гарантируется, что все элементы массива — различные целые числа, не превышающие по модулю 109. Формат выходных данных Выведите одно число –– количество обменов пузырьковой сортировки. входные данные 3 1 2 3 2 2 1 4 4 1 5 3 выходные данные 0 1 3

Answer 1

#include <algorithm>

#include <iostream>

#include <random>

#include <vector>

 

void fillVector(std::vector<int>&, int lowerBound, int upperBound);

void print(const std::vector<int>&);

 

int main() {

 

   std::vector<int> vec { };

   std::size_t size { 0 };

 

   std::cout

       << "Please, enter the number of elements: ";

   std::cin

       >> size;

 

   if (size < 1 || size > 1000) {

 

       std::cerr

           << "The size must be in the range [1; 1000]" << std::endl;

 

       return 1;

 

   }

 

   vec.resize(size);

 

   fillVector(vec, 0, 100);

   print(vec);

 

   std::size_t changes { 0 };

 

   for (std::size_t i { 0 }; i < vec.size() - 1; ++i) {

 

       int tempValue { 0 };

 

       for (std::size_t j { i + 1 }; j < vec.size(); ++j) {

 

           if (vec.at(i) > vec.at(j)) {

 

               tempValue = vec.at(i);

               vec.at(i) = vec.at(j);

               vec.at(j) = tempValue;

 

               ++changes;

 

           }

 

       }

 

   }

 

   print(vec);

 

   std::cout

       << "Number of changes: " << changes << std::endl;

 

   return 0;

 

}

 

void fillVector(std::vector<int>& vec, int lowerBound, int upperBound) {

 

   std::random_device rd;

   std::mt19937 gen(rd());

   std::uniform_int_distribution<int> dist(lowerBound, upperBound);

 

   int randomValue { };

 

   for (auto& value : vec) {

 

       while (true) {

 

           randomValue = dist(gen);

       

           if ( std::find( vec.begin(), vec.end(), randomValue) == vec.end() ){

       

               value = randomValue;

               break;

       

           }

 

       }

 

   }

 

}

 

void print(const std::vector<int>& vec) {

 

   for (const auto value : vec) {

 

       std::cout

           << value << " ";

 

   }

 

   std::cout

       << std::endl;

 

}

Answer 2

Для решения этой задачи мы можем моделировать работу алгоритма пузырьковой сортировки, подсчитывая количество обменов, которые происходят при каждой итерации. Пузырьковая сортировка работает так, что на каждой итерации она сравнивает соседние элементы массива и, если текущий элемент больше следующего, они меняются местами. Этот процесс продолжается до тех пор, пока весь массив не будет отсортирован.

Пример ваших входных данных:

3
1 2 3

На первой итерации пузырьковой сортировки происходит один обмен (1 и 2 меняются местами), на второй итерации нет обменов (2 и 3 уже в правильном порядке). Итак, общее количество обменов равно 1.

Пример других входных данных:

3
2 1 3

На первой итерации пузырьковой сортировки происходит один обмен (2 и 1 меняются местами), на второй итерации еще один обмен (2 и 3 меняются местами), на третьей итерации нет обменов (сортировка завершена). Итак, общее количество обменов равно 2.

Теперь давайте напишем код, который решает эту задачу:

n = int(input())
arr = list(map(int, input().split()))

# Инициализируем счетчик обменов
swaps = 0

for i in range(n):
    for j in range(0, n - i - 1):
        if arr[j] > arr[j + 1]:
            # Меняем элементы местами
            arr[j], arr[j + 1] = arr[j + 1], arr[j]
            swaps += 1

print(swaps)

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