---

#include <iostream>
using namespace std;

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

void bubbleSort(int* arr,int m)
{
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < m-1;j++) {
            if(arr[j] > arr[j+1]) {
                swap(arr[j],arr[j+1]);
            }
        }
    }
}
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] < arr[i-1]) {
                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()
{

    int arr2 [6];  
    srand(time(0));
    int n;
    int m;
    
    cout << "Select size - ";
    cin >> m;
    int left = 0;
    int right = m-1;
    int* arr = new int[m];
    int** arr1 = new int*[m];
    for(int i = 0; i < m; i++) {
        arr[i] = rand() % 55 - 78;
        cout << arr[i] << ' ';
    }
   
    while (true)
    {
        
        cout << "\n1. BubbleSort \n2.ShakerSort \n3.QuickSort \n0.Exit\n";
        cin >> n;
        switch (n)
        {
        case 1:
        {
            bubbleSort(arr,m);
            log_arr(arr,m);
            break;
        }
        case 2:
        {
            shakerSort(arr,m);
            log_arr(arr,m);
            break;
        }
        case 3:
        {
            quickSort(arr,left,right);
            log_arr(arr,m);
            break;
        }
        case 0:
        {
            exit(0);
        }
        default:
        {
            cout << "invalid command";
        }
        }
    }
}