Помогите с программой
Выполнить сортировку массива двумя способами. Массивы заполняются случайными числами. Алгоритмы сортировки реализовать в виде функций, возвращающих в качестве результата характеристику трудоемкости алгоритма (например, количество сравнений, времени). Произвести сравнение эффективности алгоритмов.
a) Сортировка выбором. Выбирается минимальный элемент в массиве и запоминается. Затем удаляется, а все последующие за ним элементы сдвигаются на один влево. Сам элемент заносится на освободившуюся последнюю позицию.
b) Шейкер-сортировка. Процесс движения в прямом и обратном направлении реализовать в виде одного цикла, используя параметр - направление движения (+1/-1) и меняя местами нижнюю и верхнюю границы просмотра.
a) Сортировка выбором. Выбирается минимальный элемент в массиве и запоминается. Затем удаляется, а все последующие за ним элементы сдвигаются на один влево. Сам элемент заносится на освободившуюся последнюю позицию.
b) Шейкер-сортировка. Процесс движения в прямом и обратном направлении реализовать в виде одного цикла, используя параметр - направление движения (+1/-1) и меняя местами нижнюю и верхнюю границы просмотра.
Вот, реализация алгоритма волновой сортировки Шейкера на С++:
Код:
void shakersort(int* pn, int size, SORTINFO* psortinfo)
{
time_t time_start; time(&time_start);
int first = 0, last = size-1, count = 0;
while ((first <= size-1) && (last >= 0))
{
int min = first, index = min+1;
int max = last, rev = max-1;
while ((index <= last) && (rev >= first))
{
if (pn[index] < pn[min]) min = index;
if (pn[rev] > pn[max]) max = rev;
index++; rev--;
}
if ((max == first) && (min == last))
{
swap(pn[first],pn[last]);
count++;
}
else if (max == first)
{
swap(pn[max],pn[last]);
swap(pn[min],pn[first]);
count++;
}
else
{
swap(pn[min],pn[first]);
swap(pn[max],pn[last]);
count++;
}
first++; last--;
}
time_t time_end; time(&time_end);
psortinfo->proctime = difftime(time_end,time_start);
psortinfo->subs = count;
}
void swap(int& value1, int& value2)
{
int temp = value1;
value1 = value2;
value2 = temp;
}
{
time_t time_start; time(&time_start);
int first = 0, last = size-1, count = 0;
while ((first <= size-1) && (last >= 0))
{
int min = first, index = min+1;
int max = last, rev = max-1;
while ((index <= last) && (rev >= first))
{
if (pn[index] < pn[min]) min = index;
if (pn[rev] > pn[max]) max = rev;
index++; rev--;
}
if ((max == first) && (min == last))
{
swap(pn[first],pn[last]);
count++;
}
else if (max == first)
{
swap(pn[max],pn[last]);
swap(pn[min],pn[first]);
count++;
}
else
{
swap(pn[min],pn[first]);
swap(pn[max],pn[last]);
count++;
}
first++; last--;
}
time_t time_end; time(&time_end);
psortinfo->proctime = difftime(time_end,time_start);
psortinfo->subs = count;
}
void swap(int& value1, int& value2)
{
int temp = value1;
value1 = value2;
value2 = temp;
}
Вот реализация всем известного алгоритма сортировки выбором на С++
Код:
void selsort(int* pn, int size, SORTINFO* psortinfo)
{
int count = 0;
time_t time_start; time(&time_start);
for (int i = 0; i < size; i++)
for (int k = i+1; k < size; k++)
if (pn[i] > pn[k])
{ swap(pn[i],pn[k]); count++; }
time_t time_end; time(&time_end);
psortinfo->proctime = difftime(time_end,time_start);
psortinfo->subs = count;
}
{
int count = 0;
time_t time_start; time(&time_start);
for (int i = 0; i < size; i++)
for (int k = i+1; k < size; k++)
if (pn[i] > pn[k])
{ swap(pn[i],pn[k]); count++; }
time_t time_end; time(&time_end);
psortinfo->proctime = difftime(time_end,time_start);
psortinfo->subs = count;
}
Описание структуры, с переменными, значения которых - характеристики трудоемкости:
Код:
typedef struct sortinfo
{
double proctime;
int subs;
} SORTINFO;
{
double proctime;
int subs;
} SORTINFO;