C++ Напишите программу, которая сравнивает количество перестановок при сортировке одного и того же массива разными методами.C++ Напишите программу, которая сравнивает количество перестановок при сортировке одного и того же массива разными методами.
Normal 0 false false false RU X-NONE X-NONE
Напишите программу, которая сравнивает количество перестановок при сортировке одного и того же массива разными методами. Проведите эксперименты для возрастающей последовательности (уже отсортированной), убывающей (отсортированной в обратном порядке) и случайной.
Язык С++

Предыдущий
вопрос Следующий
вопрос

#include <iostream>
#include <vector>
#include <algorithm>
// Функция для сортировки массива методом пузырька и подсчета количества перестановок
int bubbleSort(std::vector<int>& arr) {
int n = arr.size();
int swaps = 0;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
std::swap(arr[j], arr[j+1]);
swaps++;
}
}
}
return swaps;
}
// Функция для сортировки массива методом сортировки по умолчанию и подсчета количества перестановок
int defaultSort(std::vector<int>& arr) {
std::vector<int> original = arr;
std::sort(arr.begin(), arr.end());
int swaps = 0;
for (int i = 0; i < arr.size(); i++) {
if (arr[i] != original[i]) {
swaps++;
}
}
return swaps;
}
int main() {
std::vector<int> arr1 = {1, 2, 3, 4, 5};
std::vector<int> arr2 = {5, 4, 3, 2, 1};
std::vector<int> arr3 = {3, 1, 4, 5, 2};
std::cout << "Already sorted array:" << std::endl;
std::cout << "Bubble Sort Swaps: " << bubbleSort(arr1) << std::endl;
std::cout << "Default Sort Swaps: " << defaultSort(arr1) << std::endl;
std::cout << "\nReverse sorted array:" << std::endl;
std::cout << "Bubble Sort Swaps: " << bubbleSort(arr2) << std::endl;
std::cout << "Default Sort Swaps: " << defaultSort(arr2) << std::endl;
std::cout << "\nRandom array:" << std::endl;
std::cout << "Bubble Sort Swaps: " << bubbleSort(arr3) << std::endl;
std::cout << "Default Sort Swaps: " << defaultSort(arr3) << std::endl;
return 0;
}

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