Бесполезные алгоритмы сортировки ^_^

Cобственно наибезсполезнейшие алгоритмы в программировании, и дело даже не в том, что проще всего запустить готовый модуль (а в некоторых яву они есть нативно, еще и выбирается оптимальный алгоритм), а в том что их зачем-то нужно знать. Еще на 1 курсе универа меня посетила мысль о смысле жизни смысле изучаемого…хотя в целом у нас не было глубого изучения данных алгоритмов, и были лишь показаны самые тривиальные и бесполезные (за исключением Quick sort). И так, главны вопрос (барабанная дроообь) зачем нужны алгаритмы, сложность которых O(n^2). И сейчас речь совсем не о базовых знаниях универа.

Что собственно меня натолкнуло на этим мысли? Собственно 1 из обсуждений в тематическом чате, о том что не знать сортировку пузырьком это чуть ли не тягчайший грех для программиста. А все началосьс того что какой-топрограммистна собеседовании не смог написать реализацию алгоритма…и вот вопрос, накой черт нужны эти алгоритмы, если в любом случае на практике они не применяются? Как по мне, это какое-то клеше, Да и к тому же вообще никак не отображает реальный опыт. Однако из всего этого вытек 1 видос, в принципе с основной идеей которого, я согласен. Дейтсвительно такие алгоритмы развивают программистское мышление. Немного подумав, я решил накатать на плюсах эту тривиальщину, заодно проверить как я помню учебную программу. Собственно сами алгоритмы мне дались достаточно просто, а вот на с++ я не кодил очень давно, и более того, я решил реализовать все в Qt, с которым знаком совсем уж мало. Почему именно плюсы? Конечно было бы куда проще реализовать это на каком-нибуь js или питоне, к тому же не нужно было устанавливать компилятор, но, от части, все это ради расслабона, и хотелось чего-то интересного и разнообразного +) поэтому плюсы, к тому же в блоге совсем пусто в данной категории, а когда-то давно я хотел загруить пару полезных функций (которые благополучно про…терял позже)

Итак начнем.

Bubble sort #

Все просто, проходим в цикле по массиву, если текущее значение больше следующего то меняем их местами этот обход N раз, где N количество элементов массива.

void BubleSotr(int* arr, int len){
    int tmp;
    for (int i=0; i < len; ++i){
        for (int j=0; j < len - 1; ++j){
            if (arr[j] > arr[j + 1]){
                tmp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

Также все просто, также 2 цикла. сравниваем значение по индексу min (изначально присваиваем индекс первого элемента массива) со всеми значениями массива, т.е ищем минимальный элемент в массиве. Если индекс внешнего цикла не совпадает с Min то меняем элементы местами. В следующей итерации (внешнего цикла) min присваиваем следующий индекс внешнего цикла.

Select sort #

void SelectSort(int* arr, int len){
    int tmp;
    int min;
    for (int i=0; i < len; ++i){
        min = i;
        for (int j=0; j < len; ++j){
            if (arr[min] < arr[j]){
                min = j;
            }
        if (i != min){
            tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
        }
    }
}

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

P.s. Не удержался, реализовал еще сортировку рандомом), забавно:

void BogSort(int* arr, int len){
    int counter = 0;
    bool check_sort = false;
    for (int i=0; i < len - 1; ++i){
        if (arr[i] > arr[i + 1]){
            check_sort = true;
            break;
        }
    }
    if (check_sort == true){
        for (int i=0; i < len; ++i){

                int swap1_index = rand() % len;
                int swap2_index = rand() % len;
                int tmp = arr[swap1_index];
                arr[swap1_index] = arr[swap2_index];
                arr[swap2_index] = tmp;

        }
        BogSort(arr, len);
    }
}