1. Си / Говнокод #27191

    0

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    void s_sort(int *a, size_t sz)
    {
      if ((sz == 0) || (sz == 1))
      {
        return;
      }
      if (sz  == 2)
      {
        int a_max = a[0] > a[1] ? a[0] : a[1];
        int a_min = a[0] > a[1] ? a[1] : a[0];
        a[0] = a_min;
        a[1] = a_max;
        return;
      }
      s_sort(a, sz - 1);
      s_sort(a + 1, sz - 1);
      s_sort(a, sz - 1);
    }

    Крайне тупая по своей сути рекурсивная сортировка. Есть ли у нее название?

    Вряд ли она имеет какое-то практическое применение именно как сортировка, но зато можно ее переписать на какой-нибудь Coq и об нее доказывать другие сортировки. Типа если какая-то там другая сортировка на всех возможных входных массивах выдает то же, что и выдает вот эта сортировка, то сортировка правильная.

    Запостил: j123123, 03 Января 2021

    Комментарии (19) RSS

    • s_sort(a, sz - 1);
      s_sort(a + 1, sz - 1);
      s_sort(a, 2);

      Оптимизировал.
      Ответить
      • Или так:
        s_sort(a + 1, sz - 1);
        s_sort(a, 2);
        s_sort(a + 1, sz - 1);
        Ответить
        • Это пузырёк.

          Рассмотрим массив [3 2 1].
          На первой строке (s_sort(a + 1, sz - 1)) второй элемент всплывает на место третьего: [3 1 2].
          На второй строке первый элемент всплывает на место второго: [1 3 2].
          Наконец, на третьей строке второй элемент всплывает на место третьего: [1 2 3].

          Увеличим массив: [4 3 2 1].
          Первая строка изначального вызова «запузырит» последние три элемента по своим местам: [4 1 2 3].
          Вторая строка выпнет четвёрку на место второго элемента: [1 4 2 3].
          Третья строка повторит базовое всплывание: [1 4 2 3] -> [1 2 4 3] -> [1 2 3 4].

          Таким образом, на каждом вызове берётся один элемент (*a) и рекурсивно «всплывается» до нужного места.
          Кстати, это можно было бы ещё оптимизировать, отключив выполнение третьей строки в случае, если вторая ничего не поменяла (т.е. порядок не нарушился).
          Ответить
          • Пузырёк эффективнее вроде. У него каждый элемент просто всплывает, а здесь прям полная сортировка хвоста.

            O(n^2) против O(2^n).
            Ответить
            • А в чем разница? Тебе хоть евроцент принесло это знание?
              Ответить
              • любой ма-те-ма-тик в курсе, что показательная функция пиздец как быстро растет, в отличие от сраной параболы

                подставь n=1000 например
                Ответить
                • > 1000

                  Я думаю ему и 48 или 64 на всю жизнь хватит.
                  Ответить
                • Это ответ на первый вопрос.
                  Ответить
                  • Ну вот смотри, попросили тебя отсортировать табличку из 64 строк за 1 евроцент. Первым алгоритмом ты её отсортируешь за секунды. А по второму ты просто никогда не дождёшься своего евроцента.

                    З.Ы. Хотя можно взять готовый sort() и не париться.
                    Ответить
                    • > Хотя можно взять готовый sort() и не париться.

                      О чём и речь.
                      Ответить
              • Ну например если ты умеешь оценивать асимптотическую сложность всяких алгоритмов, этим знанием можно выебнуться на собеседовании, и тебя за эти знания с большей вероятностью возьмут на работу в какой-нибудь условный гугл.
                Ответить
                • Добрый вечер, j123123.
                  Ответить
                  • Я поставлю на радиолу пластинку Козловского, растормошу старый сталинский самовар и приглашу тебя выпить чаю с конфектами.
                    Придьош?
                    Ответить
            • Тьфу, блин, точно, я спросонья подумал, что тут квадрат. А так да, получается, экспоненциальный рекурсивный пузырёк.
              Ответить
    • > кок

      Сортировка правильная, если a[i] <= a[i + 1]
      Хуле тут доказывать?
      Ответить
      • А еще надо, чтоб массив до и после сортировки состоял из той же хуйни в том же количестве. Если все изменения, которые с массивом можно делать - обмен двух элементов, это должно быть тривиальным.
        Ответить

    Добавить комментарий