@Jeka3333333

Как расширить быструю сортировку для произвольного типа данных?
#include <iostream>
#include <time.h>

using namespace std;

// прототип функции печати
template <typename T>
void printr(T *M, int N);

template <typename T>
void insertion_sort(T *M, int N)
{
T *k;
// пропускаем 1 элемент , указатель не должен выходить за пределвы массива
for (T *i = M + 1; i < M + N; i++)
{
T x = *i;// запоминаем значение вставляемого элемента
for (k = i; k > M && *(k - 1) > x; k--)
{
// "раздвигаем" элементы отсортированной последовательности
*k = *(k - 1);
}
// вставляем х в отсортированную последовательность
*k = x;
}

}

// общие функции
// печать массива
template <typename T>
void printr(T *M, int N)
{
// пока не исчерпались элементы
while (N--> 0)
{
// вывод разыменованного указателя с его(указателя) одновременным сдвигом
cout << *M++ << '\t';
}
cout << '\n';
}
// генерация случайных числовых значений
template <typename T>
T* generator(int size)
{
// резервируем место под массив
T* mas = new T[size];
for (int i = 0;i < size;i++)
{
// заполняем 2 знака до запятой, 2 знака после
mas[i] = rand() % 100 - 50 + (rand() % 100 / 100.0);
}
return mas; // потом массив нужно удалить !
}

// проверка
template <class T>
bool check(T* M, int N)
{
while (--N > 1)
{
if (M[N - 1] > M[N])
// элементы не на месте
return false;
}
// проверили весь массив, нет элементов не на месте
return true;
}


// быстрая сортировка со "сдвигом" массива
void quick_sort(double * M, int N)
{
int i = 0, j = N-1; // первый и последний индексы рассматриваемого подмассива
double c = M[N/2]; // элемент для сравнения
// выполнять, пока индексы не "заскочат" друг за друга
while (i <= j)
{
// элемент слева не на месте
while (i <= j && M[i] < c) i++;
// элемент справа не на месте
while (i <= j && M[j] > c) j--;
if (i <= j)
{
// обмен значениями не на месте
double tmp = M[i];
M[i] = M[j];
M[j] = tmp;
// сдвигаем индексы
i++; j--;
}
}
// здесь же условие завершения рекурсии - элементов <2

if (j>0)
quick_sort(M,j+1);// левая часть
if (i<N-1)
quick_sort(M+i, N-i);// правая часть

}



// более упрощенный вариант сортировки
// массив(не меняется, индекс первого(S) и индекс последнего(F)
// из группы рассматриваемых элементов
void quick_sort(double M[], int S,int F)
{
int i = S, j = F;
double c = M[(S + F) / 2]; // элемент для сравнения выбираем из середины кусочка
// выполнять, пока индексы не "заскочат" друг за друга
while (i <= j)
{
// элемент слева не на месте
while (M[i] < c) i++;
// элемент справа не на месте
while ( M[j] > c) j--;
if (i <= j)
{
// обмен значениями не на месте
double tmp = M[i];
M[i] = M[j];
M[j] = tmp;
// сдвигаем индексы
i++; j--;
}
}
// здесь же условие завершения рекурсии - элементов <2
if(S<j)
quick_sort(M,S, j); // левая часть
if(i<F)
quick_sort(M ,i,F); // правая часть


}



void main()
{
float massiv1[] = { 4,1,0.3,7,6 };
printr(massiv1, 5);
// для засекания времени выполнения
long long start = clock();
long long finish = clock();
#define _20000 200000
srand(time(NULL));
#if 1
cout << "insertion sort\n";
// создаем массив вещественных чисел
double *massiv2 = generator<double>(_20000);
// проверяем, должен получиться несортированный
cout << "Sorted before(0-1) ?" << check(massiv2, _20000) << '\n';
// засекаем время начала сортировки
start = clock();
// сортируем
insertion_sort(massiv2, _20000);
// когда закончилась сортировка
finish = clock();
// проверяем, должен получиться сортированный
cout << "Sorted after(0-1) ?" << check(massiv2, _20000) << '\n';
// printr(massiv2, _20000);
// удаляем массив
delete[] massiv2;
// сколько времени (в компьютерных циклах) заняла сортировка
cout << "delta(insertion)=" << finish - start << '\n';
#endif
// быстрая сортировка маленького массива
double massiv3[] = { 4,1,3,7,6,4};
int col = sizeof(massiv3) / sizeof(massiv3[0]);
cout << "Sorted before(0-1) ?" << check(massiv3, col) << '\n';
quick_sort(massiv3,0,5);
cout << "Sorted after(0-1) ?" << check(massiv3, col) << '\n';
printr(massiv3, col);


cout << "quick sort\n";
// создаем массив вещественных чисел
double *massiv4 = generator<double>(_20000);
// проверяем, должен получиться несортированный
cout << "Sorted before(0-1) ?" << check(massiv4, _20000) << '\n';
// засекаем время начала сортировки
start = clock();
// сортируем
// 2 перегруженные быстрые сортировки
// quick_sort(massiv4, 0, _20000 - 1);
quick_sort(massiv4, _20000);
// когда закончилась сортировка
finish = clock();
// проверяем, должен получиться сортированный
cout << "Sorted after(0-1) ?" << check(massiv4, _20000) << '\n';
// printr(massiv4, _20000);
// удаляем массив
delete[] massiv4;
// сколько времени (в компьютерных циклах) заняла сортировка
cout << "delta(quick)=" << finish - start << '\n';



}

0