1

Рассматриваю простые сортировки массивов.Делаю сортировку вставками(без барьера). Но в книге Вирта "Алгоритмы и структура данных" она написана с барьером , соответственно и количество сравнений(они же ключи) ( C ) и количество перестановок (пересылок) (М) посчитаны для кода с барьером. По сему вопрос : как самому посчитать эти С и М , есть ли какой-либо алгоритм , как у подсчета сложности (эти О(n^2) )?

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
const int N =7;
void vstavki(int *P)
{
    int i = 0, j = 0,x=0;
    for (i = 1; i <= N - 1; i++)
    {
        j = i;
         x = *(P + i);
         while (j > 0 && x < P[j - 1])
         {
             P[j] = P[j - 1];
             j--;
         }
         P[j] = x;
    }
}
int main()
{
    srand(time(NULL));
    int A[N], i = 0, j = 0, k = 0;
    while (i < N)
    {
        *(A+i) = rand() % 100;
        printf("%4d", *(A+i));
        i++;
    }
    vstavki(A);
    printf("\n");
    for (i = 0; i < N; i++)
    {
        printf("%4d", A[i]);
    }
    _getch();
    return 0;

}
1
  • Внешний цикл исполнится i-1 раз, что дает 2 * (i - 1) M и i - 1 C. K выполнений внутреннего цикла добавит K-1 C и K M (K-1, поскольку первое сравнение мы учли в составе выполнений внешнего цикла. Остается определить, чему в среднем равно K -)
    – avp
    Commented 7 янв. 2018 в 19:38

1 ответ 1

0

Насчет сортировки с барьером - никогда ее не реализовавывал (да и не сталкивался ни разу, но вот сортировку вставками я реализовал следующим образом:

void insertionSort (int array [], int size)
{
int temp = 0;

for (unsigned int i = 0; i < size; ++i) {
    temp = array [i];//элементы для сравнения берутся по-порядку
    for (unsigned int j = 0; j < i; ++j) {
        if (temp < array [j]) {//если элемент сравнения меньше текущего
            for (unsigned int l = i; l > j; --l) {
                array [l] = array [l - 1];//то выполняется смещение уже отсортированных элементов вправо
            }

            array [j] = temp;

            break;
        }
    }
}

return;
}
3
  • У ТС алгоритм лучше
    – avp
    Commented 7 янв. 2018 в 18:16
  • Что за ТС? Не совсем понял.. Commented 7 янв. 2018 в 18:23
  • TC -- это Topic Creator -- в данном случае, человек, который задал вопрос. Сразу: его алгоритм вставок лучше тем, что по крайней мере для подпоследовательностей одинаковых элементов у него меньше элементов сдвигается, поскольку внутренний цикл у него идет от конца уже отсортированной части массива. В частности, для уже отсортированного массива код во внутреннем цикле вообще ни разу не выполнится
    – avp
    Commented 7 янв. 2018 в 19:28

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.