Практическая работа #2 Амиров Исмаил Проверила: Лариса Тимофеевна М. Ташкент 2023 Задача №1

Ташкентский университет информационных технологий
Структурa данных и алгоритмы

Практическая работа #2

Выполнила: Амиров Исмаил
Проверила: Лариса Тимофеевна М.

Ташкент 2023

Задача №1
Методом шейкера-сортировки : Упорядочить все строки массивы по числу элементов, кратных 3, т.е. на первое место поставить строку с наименьшим числом таких элементов и т.д., на последнее место - с наибольшим числом таких элементов.

Вот пример реализации метода шейкер-сортировки для упорядочивания строк массива по числу элементов, кратных 3:

#include
#include
#include

// Функция для подсчета числа элементов, кратных 3, в строке

int countMultiplesOfThree(const std::string& str) {
int count = 0;
for (char c : str) {
if (c != ' ' && (c - '0') % 3 == 0) {
count++;
}
}
return count;
}

// Метод шейкер-сортировки для упорядочивания строк массива по числу элементов, кратных 3

void shakerSort(std::vector& arr) {
int left = 0;
int right = arr.size() - 1;

while (left <= right) {

// Проход слева направо
for (int i = left; i < right; i++) {
if (countMultiplesOfThree(arr[i]) > countMultiplesOfThree(arr[i + 1])) {
std::swap(arr[i], arr[i + 1]);
}
}
right--;

// Проход справа налево

for (int i = right; i > left; i--) {
if (countMultiplesOfThree(arr[i]) < countMultiplesOfThree(arr[i - 1])) {
std::swap(arr[i], arr[i - 1]);
}
}
left++;
}
}

int main() {

std::vector arr = {"123", "4567", "89", "101112", "1314", "15161718"};

std::cout << "Исходный массив:\n";

for (const std::string& str : arr) {
std::cout << str << " ";
}
std::cout << std::endl;

shakerSort(arr);

std::cout << "Отсортированный массив:\n";
for (const std::string& str : arr) {
std::cout << str << " ";
}
std::cout << std::endl;

return 0;

}

В данном примере массив строк arr содержит несколько строк. Функция countMultiplesOfThree подсчитывает количество элементов, кратных 3, в строке. Метод shakerSort реализует алгоритм шейкер-сортировки для упорядочивания строк массива arr по числу элементов, кратных 3. В функции main задается исходный массив строк, затем вызывается метод shakerSort, и отсортированный массив выводится на экран.