Сортировки: пять методов на выбор в одной программе - C++ - Ответ 6019227

 #include <iostream>
#include <time.h>
using namespace std;
 
int opred_mas(int* Arr, int size);    
template< class T > void selectSort(T* arr, int size);
template< class T > void bubbleSort(T* arr, int size);
template< class T > void insertSort(T* a, int size);
template<class T> void quickSortR(T* a, long N);
template<class T> void merge(T* a, int l, int r);
 
int main()
{
    setlocale(0,"");
    int k=10;     //константа размера массива
    cout<<"Введите количество элементов массива\n";
    cin >>k;
 
    int *Arr1;      //указатель обьявляется, для использования динамического массива
    Arr1=new int [k];     //создание динамического массива
       
    cout<<"Полученный массив\n";
    opred_mas(Arr1,k);
    unsigned int H;
    cout<<"Нажмите 1, если вы хотите провести сортироку методом выбора"<<endl;
    cout<<"Нажмите 2, если вы хотите провести сортироку методом пузырька"<<endl;
    cout<<"Нажмите 3, если вы хотите провести сортироку методом вставок"<<endl;
    cout<<"Нажмите 4, если вы хотите провести сортироку методом быстрой сортировки"<<endl;
    cout<<"Нажмите 5, если вы хотите провести сортироку методом слияния "<<endl;
    cout<<"нажмите 0, если вы хотите выйти"<<endl;
    cin>>H;
    
    switch(H)
    {
        case 1:
            selectSort(Arr1,k);
            break;
        case 2:
            bubbleSort(Arr1,k);
            break;
        case 3:
            insertSort(Arr1,k);
            break;
        case 4:
            quickSortR(Arr1,k-1);
            break;
        case 5:
            merge(Arr1,0,k-1);
            break;
        default:
            exit(0);
    }
    
    
    cout<<endl;
    for(int i=0;i<k;++i)  cout<<Arr1[i]<<" ";
    system("pause");
}
 
int opred_mas(int* Arr, int size)       //функция задания элементов массива
{
    //srand(time(NULL));
    for(int i=0;i<size;++i)
    {
        Arr[i]=rand()%100-50;
        cout<<Arr[i]<<" ";
    }
    cout<<endl;
    return 0; 
}
 
template< class T > void selectSort(T* arr, int size) // сортировка выбором
{
    T tmp;
    for(int i = 0; i < size; ++i) // i - номер текущего шага
    { 
        int pos = i; 
        tmp = arr[i];
        for(int j = i + 1; j < size; ++j) // цикл выбора наименьшего элемента
        {
            if (arr[j] < tmp) 
           {
               pos = j; 
               tmp = arr[j]; 
           }
        }
        arr[pos] = arr[i]; 
        arr[i] = tmp; // меняем местами наименьший с a[i]
    }
}
 
template< class T > void bubbleSort(T* arr, int size)// пузырьком
{
    T tmp;
 
    for(int i = 0; i < size - 1; ++i) // i - номер прохода
    {            
        for(int j = 0; j < size - 1; ++j) // внутренний цикл прохода
        {     
            if (arr[j + 1] < arr[j]) 
            {
                tmp = arr[j + 1]; 
                arr[j + 1] = arr[j]; 
                arr[j] = tmp;
            }
        }
    }
}
 
template< class T > void insertSort(T* a, int size) // вставками
{
    T tmp;
    for (int i = 1, j; i < size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = a[i]; 
        for (j = i - 1; j >= 0 && a[j] > tmp; --j) // поиск места элемента в готовой последовательности 
            a[j + 1] = a[j];    // сдвигаем элемент направо, пока не дошли
        a[j + 1] = tmp; // место найдено, вставить элемент    
    }
}
 
template<class T> void quickSortR(T* a, long N) { // быстрая
// На входе - массив a[], a[N] - его последний элемент.
 
  long i = 0, j = N;        // поставить указатели на исходные места
  T temp, p;
 
  p = a[ N>>1 ];        // центральный элемент
 
  // процедура разделения
  do {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;
 
    if (i <= j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i<=j );
 
  // рекурсивные вызовы, если есть, что сортировать 
  if ( j > 0 ) quickSortR(a, j);
  if ( N > i ) quickSortR(a+i, N-i);
}
 
template<class T> void merge(T* a, int l, int r) {
    if (r == l)
        return;
    if (r - l == 1) { 
        if (a[r] < a[l])
            swap(a[r], a[l]);
        return;
    }
    int m = (r + l) / 2;
    merge(a,l, m);
    merge(a,m + 1, r);
    T *buf=new T[r];
    int xl = l;
    int xr = m + 1;
    int cur = 0;
    while (r - l + 1 != cur) {
        if (xl > m)
            buf[cur++] = a[xr++];
        else if (xr > r)
            buf[cur++] = a[xl++];
        else if (a[xl] > a[xr])
            buf[cur++] = a[xr++];
        else buf[cur++] = a[xl++];
 
    }
    for (int i = 0; i < cur; i++)
        a[i + l] = buf[i];
}