timp4

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

bool isRav(vector <char> th) {
    int a = 0;
    for (int i = 0; i < th.size(); i++) {
        for (int j = 0; j < th.size(); j++) {
            if (th[i] == th[j]) {
                a++;
            }
        }
    }
    if (a == th.size() * th.size()) {
        return true;
    }
    else {
        return false;
    }
}

int sh3 = 0;

vector <char> Thanos(vector <char> th) {
    if (th.size() == 1) {
        return th;
    }
    else if (th.size() == 2) {
        if (th[0] > th[1]) {
            swap(th[0], th[1]);
            sh3++;
        }
        return th;
    }
    else {
        float a = 0;
        for (int i = 0; i < th.size(); i++) {
            float ia = th[i] - '0';
            a = a + ia;
        }
        float sr = a / th.size();
        char* asd = new char[th.size()];
        int b = 0; //левая граница
        int c = th.size() - 1; //праввая граница
        for (int i = 0; i < th.size() && b != c + 1; i++) {
            float ia = th[i] - '0';
            if (ia <= sr) {
                asd[b] = th[i];
                sh3++;
                b++;
            }
            else if (ia > sr) {
                asd[c] = th[i];
                sh3++;
                c--;
            }
        }
        int ch = th.size() / 2;
        vector <char> th1;
        vector <char> th2;
        for (int i = 0; i < b; i++) {
            th1.push_back(asd[i]);
        }
        for (int i = b; i < th.size(); i++) {
            th2.push_back(asd[i]);
        }
        if (!isRav(th1)) {
            th1 = Thanos(th1);
        }
        if (!isRav(th2)) {
            th2 = Thanos(th2);
        }
        vector <char> th3;
        for (int i = 0; i < th1.size(); i++) {
            th3.push_back(th1[i]);
        }
        for (int i = 0; i < th2.size(); i++) {
            th3.push_back(th2[i]);
        }
        return th3;
    }
}

int main() {
    setlocale(0, "");
    cout << "Введите строку: ";
    string vr;
    getline(cin, vr);
    vector <char> strk;
    for (int i = 0; i < vr.size(); i++) {
        strk.push_back(vr[i]);
    }
    for (int i = 0; i < strk.size(); i++) {
        cout << strk[i] << " ";
    }
    cout << endl;
    vector <char> strk1;
    strk1 = strk;
    cout << "Время работы программы = " << clock() << endl;
    cout << "Сортировка вставками" << endl;
    int sh = 0; //счётчик перестановок
    for (int i = 0; i < strk1.size(); i++) {
        for (int j = i; j > 0 && strk1[j - 1] > strk1[j]; j--) {
            swap(strk1[j - 1], strk1[j]);
            sh++;
        }
    }
    cout << "Время работы программы = " << clock() << endl;
    for (int i = 0; i < strk1.size(); i++) {
        cout << strk1[i] << " ";
    }
    cout << endl;
    cout << "Количество перестановок: " << sh << endl;
    vector <char> strk2;
    strk2 = strk;
    cout << "Сортировка Шелла" << endl;
    int sh1 = 0;
    for (int h = strk2.size() / 2; h > 0; h = h/2) {
        for (int i = 0; i < strk2.size(); i++) {
            for (int j = i + h; j < strk2.size(); j = j + h) {
                if (strk2[i] > strk2[j]) {
                    swap(strk2[i], strk2[j]);
                    sh1++;
                }
            }
        }
    }
    cout << "Время работы программы = " << clock() << endl;
    for (int i = 0; i < strk2.size(); i++) {
        cout << strk2[i] << " ";
    }
    cout << endl;
    cout << "Количество перестановок: " << sh1 << endl;
    cout << "Быстрая сортировка" << endl;
    int sh2 = 0;
    vector <char> strk3;
    strk3 = strk;
    for (int i = strk3.size() - 1; i > 0; i--) {
        for (int j = 0; j <= i; j++) {
            if (strk3[j] > strk3[i]) {
                swap(strk3[j], strk3[i]);
                sh2++;
            }
        }
    }
    cout << "Время работы программы = " << clock() << endl;
    for (int i = 0; i < strk3.size(); i++) {
        cout << strk3[i] << " ";
    }
    cout << endl;
    cout << "Количество перестановок равно: " << sh2 << endl;
    cout << "Сортировка Таноса" << endl;
    vector <char> strk4;
    strk4 = strk;
    strk4 = Thanos(strk4);
    cout << "Время работы программы = " << clock() << endl;
    for (int i = 0; i < strk4.size(); i++) {
        cout << strk4[i] << " ";
    }
    cout << endl;
    cout << "Количество перестановок равно: " << sh3 << endl;
    return 0;
}