сортировка, количество вызовов

Ммм... про сортировки почитать? Тут уже на твой вкус: от Википедии и статей в интернетах до Кнута, Седжвика или Кормана.

Куда копать, что почитать?

Загуглить «нотация O(n)». Книги по алгоритмам, курсы по алгоритмам. Там это всё разжёвано многократно, особенно, на примере сортировки массивов.

O(n)

Ок. Уже читаю.

колько вызовов приемлемо для массива n-размерности?

А это?

O(n) как раз и является универсальной и понятной оценкой времени для данных размерности n.

В общем, там дальше всё будет подробно объяснено. Эта тема разжевана на всех языках всеми возможными источниками.

Спасибо тебе, мил человек. Разбираюсь уже. Как минимум, мой код работает быстрее линейного, а это уже хорошо. А у тебя есть какой-нибудь код быстрой сортировки? Я не хочу докапаться, но хотел бы посмотреть твою реализацию сортировки или похожего.

Как минимум, мой код работает быстрее линейного, а это уже хорошо

Што? У тебя сортировка пузырьком, она имеет квадратичную сложность. Вдобавок зачем-то через рекурсию. Нормальные сортировки работают за O(NlogN). Быстрее чем за линию массив отсортировать нельзя. Начинай с самых основ алгоритмов и структур данных.

быстрая сортировка. https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0

На линейной сортировке получилось 64 шага из 8 элементов. Тут получилось 43 шага. Это на 25% быстрее. Собственно, я теперь знаю как эта сортировка называется. Спасибо 😁

Нотация O(n) показывает, не сколько будет операций в конкретном случае, а как число операций будет увеличиваться по мере роста массива для сортировки.

Вот, кстати, хорошее замечание. А вообще реально вылезти за пределы O(N log N)?

Посмотри количество операций на массиве из 100к элементов, и ты сразу поймешь что к чему)

Сортировок очень много, их просто море, и у каждой свои плюсы и минусы в целом и на конкретных данных ещё раз свои плюсы и минусы тут только крохотная часть можешь просто сишную, родную qsort дрыгнуть. https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 самое то когда ты не в курсе что там тебе надо сортировать, в том смысле какая степень «перемешивания» данных. Можно сделать быстрее, если написать свою qsort и вместо вызова функции калбека написать алгоритм сравнения в теле обхода напрямую.

А вообще реально вылезти за пределы O(N log N)?

нет. для общего случая это теоретический предел.

Спасибо большое, человек. Не зря на ЛОР захожу. Тут реально можно получить советы от практикующих людей, а не курсы от всяких инфоцыган.

alysnix понял тебя

А вообще реально вылезти за пределы O(N log N)?

сортировку можно отобразить на вставку каждого элемента в бинарное дерево, а потом перемещение из дерева в массив. вставка в дерево (logN) для каждого (N) - итого N*logN как минимум.

функция sort_by_swap вызывается 8 раз и цикл for внутри нее

вкурить про хвостовую рекурсию.

вольно/невольно вам в коде её привели, а она там совершенно ни к чему. Чисто учебный пример

Я реализовывал кучу алгоритмов сортировки, когда проходил бесплатные курсы по алгоритмам. Но в жизни я пользуюсь готовыми алгоритмами из стандартной библиотеки, и не изобретаю велосипед.

Более того, боюсь, что уже даже не смогу написать по памяти сейчас те алгоритмы сортировки, которые реализовал во время прохождения курса. :D

Кроме разве что сортировки пузырьком, но и то потому что впервые сам придумал этот алгоритм, когда учился в школе, ещё до того, как прочитал первую книгу по программированию. :)

На линейной сортировке

Что такое линейная сортировка? Пузырёк без уменьшения массива на единицу на каждой итерации?

64 шага из 8 элементов. Тут получилось 43 шага. Это на 25% быстрее

Это в любом случае квадрат.

Вот, кстати, хорошее замечание. А вообще реально вылезти за пределы O(N log N)?

Можно за линию если значений ключа не много. Это сортировка подсчётом.

Как то так. (вроде ничего не перепутал)

#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <time.h>
/*----------------------------------------------------*/
static int my_cmp(const void *left, const void *right) {
    return (*(int*)left > *(int*)right);
}
/*-----------------------------------------------------*/
void swap_local(int *left, int *right) {
    int temp = 0;
    temp = *right;
    *right = *left;
    *left = temp;
}

void sort_by_swap(int arrays[], int left, int right) {
    if (left >= right) {
        return;
    }
    for (int i = left; i <= right; ++i) {
        if (arrays[left] > arrays[i]) {
            swap_local(&arrays[left], &arrays[i]);
        }
    }
    sort_by_swap(arrays, ++left, right);
}
/*------------------------------------------------------*/
void x_sort_by_swap(int arrays[], int left, int right) {
    if (left >= right) {
        return;
    }
    for (int i = left; i <= right; ++i) {
        if (arrays[left] > arrays[i])
        {
            int swaps = arrays[i];
            arrays[i]=arrays[left];
            arrays[left]=swaps;
        }
    }
    x_sort_by_swap(arrays, ++left, right);
}
/*-----------------------------------------------------*/
void y_sort_by_swap(int arrays[], int left, int right) {
    if (left >= right) {
        return;
    }
    for (int x = left; x < right; x++)
    for (int i = x; i <= right; ++i) {
        if (arrays[left] > arrays[i])
        {
            int swaps = arrays[i];
            arrays[i]=arrays[left];
            arrays[left]=swaps;
        }
    }
}
/*-----------------------------------------------------*/

int main(int argc, char *argv[])
{
    int size = 500;
    if ( argc > 1 )
    {
        sscanf(argv[1],"%d",&size);
    }
    int * data = malloc(sizeof(int)*size+1);
    assert(data);

    //printf("---sbs----------------\n");
    srandom(684168464);
    for (int i = 0; i < size; data[i++]=random());
    time_t sbs_start = clock();
    sort_by_swap(data,0,size);
    time_t sbs_final = clock();
    //for (int i = 0; i < size; printf("%d\n",data[i++]));

    //printf("---qsort--------------\n");
    srandom(684168464);
    time_t qst_start = clock();
    for (int i = 0; i < size; data[i++]=random());
    qsort(data, size, sizeof(int), my_cmp);
    time_t qst_final = clock();
    //for (int i = 0; i < size; printf("%d\n",data[i++]));

    //printf("---xbs---------------\n");
    srandom(684168464);
    for (int i = 0; i < size; data[i++]=random());
    time_t xbs_start = clock();
    x_sort_by_swap(data,0,size);
    time_t xbs_final = clock();
    //for (int i = 0; i < size; printf("%d\n",data[i++]));
    
    //printf("---ybs---------------\n");
    srandom(684168464);
    for (int i = 0; i < size; data[i++]=random());
    time_t ybs_start = clock();
    y_sort_by_swap(data,0,size);
    time_t ybs_final = clock();
    //for (int i = 0; i < size; printf("%d\n",data[i++]));


    printf("sort_by_swap.. на %d элементов потратил %lf секунды\n",size,(double)(sbs_final-sbs_start)/CLOCKS_PER_SEC);
    printf("x_sort_by_swap на %d элементов потратил %lf секунды\n",size,(double)(xbs_final-xbs_start)/CLOCKS_PER_SEC);
    printf("y_sort_by_swap на %d элементов потратил %lf секунды\n",size,(double)(ybs_final-ybs_start)/CLOCKS_PER_SEC);
    printf("qsort......... на %d элементов потратил %lf секунды\n",size,(double)(qst_final-qst_start)/CLOCKS_PER_SEC);

    return 0;
}

dron@gnu:~/Рабочий-стол/ыыы$ gcc main.c ; ./a.out 5000
sort_by_swap.. на 5000 элементов потратил 0.134655 секунды
x_sort_by_swap на 5000 элементов потратил 0.121517 секунды
y_sort_by_swap на 5000 элементов потратил 0.071896 секунды
qsort......... на 5000 элементов потратил 0.000741 секунды
dron@gnu:~/Рабочий-стол/ыыы$ 

Если непонятно, я из твоего решения поочерёдно выкинул лишние функции.

Мужик, это то, что я хотел. Всех благ тебе. Спасибо огромное. Теперь есть на что ориентироваться)

По-хорошему конечно надо смотреть не на время выполнения, а на число шагов. Время-то от частоты и загрузки ЦПУ зависит.

как у тебя

int size = 500;

а печатает 5000

    int temp = 0;
    temp = *right;
    *right = *left;
    *left = temp;

зачем инициализировать temp нулем,и тут же присваивать снова.

а печатает 5000

500 это значение по умолчанию если в аргументы ничего не задано. Дальше проверка идёт на argc и sscanf пишет в указатель на size. Хотя там бы ещё аргумент проверить, а то ненароком можно и всю память выжрать, но это уже жирно будет для одноразового кода, а если у ТС машина в своп улетит, то будет повод разобраться что случилось и как этого избежать :) Грабли в лоб лучший учитель хехе

зачем инициализировать temp нулем,и тут же присваивать снова.

Спроси у ТС я сохранил оригинал, а уже ниже вносил изменения постепенно, чтобы ему было нагляднее. А так привычка инициализировать всегда явно переменные может порой очень много нервов спасти, так что в этом ничего плохого =) Хотя тут конечно проще сразу присваивать. Но это уже ничего не значащие и не меняющие мелочи.