---

#include <iostream>
using namespace std;

void log_arr(int* arr, int m) {
    cout << "Sorted Array\n";
    for (int i = 0; i < m; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;
}

void bubbleSort(int* arr, int m)
{
    bool swapped;
    for (int i = 0; i < m - 1; i++) { 
        swapped = false;
        for (int j = 0; j < m - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

void shakerSort(int* arr, int m)
{
    int left = 0;
    int right = m - 1;

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

void quickSort(int* arr, int left, int right)
{
    int i = left;
    int j = right;
    int pivot = arr[(left + right) / 2];
    
    while (i <= j){
         while (arr[i] < pivot) i++;
         while (arr[j] > pivot) j--;
         
         if (i <= j){
             swap(arr[i], arr[j]);
             i++;
             j--;
         }
    }
    
    if (left < j) {
        quickSort(arr, left, j);
    }
    if (i < right) {
        quickSort(arr, i, right);
    }
}

int main()
{
    srand(static_cast<unsigned>(time(0)));
    int choice;
    int m;
    cout << "Select size - ";
    cin >> m;
    if (m <= 0) return 0;

    int* arr = new int[m];
    for (int i = 0; i < m; i++) {
        arr[i] = rand() % 133 - 78;
        cout << arr[i] << ' ';
    }
    cout << endl;

    while (true)
    {
        cout << "\n1. BubbleSort \n2.ShakerSort \n3.QuickSort \n0.Exit\n";
        cin >> choice;
        
        switch (choice)
        {
        case 1:
        {
            bubbleSort(arr, m);
            log_arr(arr, m);
            break;
        }
        case 2:
        {
            shakerSort(arr, m);
            log_arr(arr, m);
            break;
        }
        case 3:
        {
            quickSort(arr, 0, m - 1); 
            log_arr(arr, m);
            break;
        }
        case 0:
        {
            delete[] arr;
            exit(0);
        }
        default:
        {
            cout << "Invalid command\n";
        }
        }
    }
}