Сортировка в одну строку

    Имеем обычный «пузырек»:
    for(int i = 0; i < n - 1; i++ )
    	  for(int j = i + 1; j < n; j++)
    	   if(ar[i] > ar[j])
    	   {
    		 int temp = ar[i];
    		 ar[i] = ar[j];
    		 ar[j] = temp; 
    	   }
    


    Задача №1: Избавиться от временной переменной. Делается это вот таким макаром:

    ar[i] ^= ar[j] ^= ar[i] ^= ar[j];
    


    Задача №2: Избавиться от if.
    Делается еще проще:
    (ar[i] > ar[j]) ? ar[i] ^= ar[j] ^= ar[i] ^= ar[j] : 0;
    


    Задача №3: Основная. Избавиться от внутреннего цикла for по j.
    Для этого следует: 1) Итерировать от j до n, при этом в условии всегда возвращать true 2) Проверять условие конца алгоритма, только когда вся итерация по j прошла
    3) При проверке условия, делать j = i + 1, i = i + 1.
    Результат таков:
    for(int i = 0, j = 0;		
    		j < n ? 1 : i < n - 1;	
    		  j = j < n ?	
    		   ((ar[i] > ar[j] ? ar[i] ^= ar[j] ^= ar[i] ^= ar[j] : 0),		
    	        ( j + 1 ))		  
    		     : ++i	// иначе j=n, идем на следующую итерацию
    			);
    


    Исходник
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 60

      +22
      >ar[i] ^= ar[j] ^= ar[i] ^= ar[j]
      Так нельзя делать. Это undefined behavior, как i = i++;
        0
        это почему еще?
          +5
          Действительно, тут нет sequence point нигде посередине, но мне казалось, что этот код нормально работает (видимо компилятор обычно компилирует это ожидаемым образом). Сравнение с i = i++ все-таки не самое правильное, тут такого сильного парадокса нет.

          P.S.: промахнулся и поставил минус вместо плюса. Поставьте, пожалуйста, два плюса за меня.

            –4
            я не сильно шарю в С++, но почему i = i++ может привести к чему-то плохому (undefined behavior)?
            разве это не эквивалентно:
            i = i;
            I++;

            Сначала идёт присваивание, потом увеличение. Я даже тест сделал. 100 раз запустил и 100 раз получил один и тот же правильный результат.
              +5
              ста разными компиляторами с различными настройками оптимизации?
                –5
                Вообще, поведение ++ и = довольно чётко описано и я бы сильно призадумался о смене компилятора, если бы он вёл себя как-то не так.
                С таким успехом можно бояться, что 2+2 различными компиляторами как-то не так обработается.

                В общем, ответа на свой вопрос я пока не услышал. Или хотя бы пример как компилятор «может» поступить, чтоб результат был неожиданным
                  –7
                  конечно, проще минус поставить, чем объяснить.
                  i=i++ это же так сложно, не то что
                  простой и понятный пример снизу:
                  ЗначениеИзСтрокиВнутр("{""#"",51e7a0d2-530b-11d4-b98a-008048da3034,{0,{"«S»",""" + СтрЗаменить(СтрЗаменить(Строка, """", """"""), Разделитель, """},{"«S»",""") + """}}}");

                  Если вы что-то не можете объяснить 6-летнему ребёнку, вы сами этого не понимаете (с)
                    +5
                    Потому, что в Стандарте написано, что такие конструкции приводят к undefined behavior. За деталями — смотрите Стандарт/гугл на предмет «sequence point».

                    Этой «особенности языка» уже лет двадцать примерно.
              • UFO just landed and posted this here
                  +1
                  кажется теперь понял о чём идёт речь.
                  конкретно i=i++ совершенно не важен порядок выполнения (могу опять ошибаться), но в более сложном, реальном случае это может вызвать большие проблемы.
                  Получил ответ на свой вопрос и узнал для себя нечто новое.
                  Спасибо
                  • UFO just landed and posted this here
                      0
                      да, так стало в 100 раз понятнее.
                      ещё раз спасибо.
                +22
                там не весь текст программы, наверху еще такие строки:

                // счастливой отладки
                
                  0
                  Практической выгоды тут не ищите. Разве что, если Enter и скобки западут.
                  +10
                  Но зачем?
                    0
                    Brainfuck
                    +6
                    Вариант с исключающим «или» изучают классе этак в девятом.
                    И да, в чём актуальность?
                      0
                      Например вариант для соревнований по ненормальному С.
                        0
                        Побеждает тот, в чьём коде разбирались дольше всего?
                      +11
                      а где вы тут от if избавились? написав его сокращенную форму это вы вроде как избавились да? ну тогда можно было сделать и так eval(base64_decode(....)) — тоже иф вроде как нет :) чистым текстом
                        +4
                        ?: — это не сокращенная форма if'а, это отдельный оператор
                          +4
                          Вот именно, оператор, причем, возвращающий значение. Использовать операции над указателями внутри аргументов верный путь получить разное поведение системы в зависимости от компилятора и условий оптимизации. И, как следствие, невозможность нормальной отладки.
                            +7
                            если цель была избавиться именно от буковок «if», то да, цель выполнена. Смысл тот же.
                          +2
                          Вы только допишите, что ar[i] ^= ar[j] ^= ar[i] ^= ar[j]; при одинаковых значениях обнуляет их.
                            +3
                            Нет, не обнуляет (можете проверить на бумажке). Это раз. И два, это то, что если элементы и будут равны, то по условию выражение не будет вычисляться.
                            +17
                            Гореть в аду такой пишущим код.
                              +1
                              Извините, а причем тут в одну строку?
                              С таким же успехом, можно было и начальный код написать просто в одну строку, без выравнивания)
                              В студии на сколько я помню, теоретически бесконечное виртуальное пространство.
                                0
                                В одну конструкцию, если точнее.
                                +1
                                Не туда, извините.
                                  +1
                                  Вот вам код от безысходности, правда на 1с:
                                  ЗначениеИзСтрокиВнутр("{""#"",51e7a0d2-530b-11d4-b98a-008048da3034,{0,{"«S»",""" + СтрЗаменить(СтрЗаменить(Строка, """", """"""), Разделитель, """},{"«S»",""") + """}}}");
                                  Делает массив из строки с разделителями, а если классическим вариантом — то на два порядка медленнее…
                                  0
                                  Я с вами согласен :) Однако, лаконичность кода тоже ценна по своему. Отдельные конструкции можно применять на практике, как например несколько выражений через запятую, и ?: вместо if.
                                    +2
                                    Это не ?:
                                    ?: это удобно и правильно.
                                    Но есть разница между ?: и

                                    for(int i = 0, j = 0;
                                    j < n ? 1 : i < n - 1;
                                    j = j < n ?
                                    ((ar[i] > ar[j] ? ar[i] ^= ar[j] ^= ar[i] ^= ar[j] : 0),
                                    ( j + 1 ))
                                    : ++i // иначе j=n, идем на следующую итерацию
                                    );


                                    На вскидку, сколько времени, по вашему, у девелопера, который не читал эту статью, возьмет понять что делает этот код? И бонусный вопрос — средняя концентрация мата на предложение при попытке понять вышенаписанное. Даже сам автор подобного кода через 2 дня ничего в нем не поймет.

                                    Проблема в том, что периодически встречаются «оптимизаторы», которые так пишут не только куски кода, а целые проекты. Для них в аду отдельные котлы есть — с кипящим майонезом, шипами, бензопилами и ректальными ананасами (см. Little Nicky).

                                    Лаконичность это хорошо, согласен, но используюя кю и ку далеко не уйдешь.
                                      0
                                      Однако же, в разделе о ненормальном программировании должен встречаться понятный код? Все это так, и шапке поста можно добавить — никогда так не пишите.
                                  +1
                                  Автор страдает фигней, не от большого ума такие фокусы, я скажем явно не хотел бы вчитываться в такой код понимая что там делается, тем более не прироста в скорости не каких-то других преимуществ нет.
                                  В одну строку это скорее так arrayObj.sort( [sortFunction] ) стандартными средствами языка, а не больной фантазией.

                                    0
                                    ну и соотвествено для каждого языка есть свои стандартные способы сортировки уже находящиеся в апи
                                    • UFO just landed and posted this here
                                      +1
                                      Тут наверное ненормальное программирование уже в использовании пузырьковой сортировки, так как еще со школы известно, что это самый простой, но при этом и самый медленный алгоритм сортировки, который применяется только в учебных материалах.
                                      +8
                                      Ко всему у вас появилась ошибка переполнения и как уже кто-то заметил undefined behaviour при решении задачи №1. Сортировка в одну строчку std::sort().
                                        +7
                                        Не хотел бы я получить такой код в наследство.
                                          +6
                                          Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live.
                                          (с)Фаулер
                                        • UFO just landed and posted this here
                                            0
                                            Более точно в одну конструкцию. Это же ненормальное программирование. Целью было описать весь алгоритм в for.
                                            +5
                                            Вот вам сортировка в одну строку из первого варианта:

                                            for(int i = 0; i < n - 1; i++ ) for(int j = i + 1; j < n; j++) if(ar[i] > ar[j]) { int temp = ar[i]; ar[i] = ar[j]; ar[j] = temp; }
                                            
                                              0
                                              А зачем такие метаморфозы кода?

                                              Чтобы запутать любого читающего в последствии? Тогда Ок.

                                              Для оптимизации? Достаточно вынести объявление «int temp» наверх за пределы циклов, плюс «n-1» заранее вычислить, жестко предопределив поведение оптимизатора, дабы избежать возможной реаллокации.
                                              Больше там вроде делать нечего, не меняя стандартный «пузырек».

                                              Можно еще вот так извратиться, развернув алгоритм реверсивно(не «пузырек всплывает», а «камень тонет») и избавившись от переменной J, не теряя особо в читабельности:
                                              int i, temp;
                                              while ((n--)>0) {
                                                i=n-1;
                                                while ((i--)>0) if (ar[n] < ar[i]) {
                                                       temp = ar[n];
                                                       ar[n] = ar[i];
                                                       ar[i] = temp;
                                                }
                                              }
                                              

                                              Тут я не отлаживал, писал с ходу, поэтому мог накосячить в реализации. Но не в самой идее.
                                              Суть — нижнюю границу массива мы знаем и так — это ноль, поэтому при «камень тонет» ее достижение проще контролировать, не создавая лишнюю переменную.
                                              Подразумевается, судя по исходному коду в посте, что n — количество элементов массива, а не индекс последнего, поэтому я избавился так же от начального холостого декремента этой переменной.

                                              Можно еще таким вот образом избавиться от второго while:
                                              int i=0;
                                              int temp;
                                              while (n>-1) {
                                                if (i==0) i=(--n)-1; 
                                                if (ar[n] < ar[i]) {
                                                       temp = ar[n];
                                                       ar[n] = ar[i];
                                                       ar[i] = temp;
                                                }
                                                i--;
                                              }
                                              

                                              (тоже не отлаживал, за возможные косяки в условиях не пинать)
                                              С точки зрения оптимизации разницы в принципе особой нет. Ну разве что оптимизатор оверхед на циклы генерирует какой-то. То есть оптимизация если и есть, то весьма условная.
                                                0
                                                Ненормальное программирование же. На Brainfuck'e тут пишут, тоже не для выгоды.
                                                  +1
                                                  Ну если в этот термин входит так же «бессмысленное», то я тут таких примеров накидать могу )))
                                                  0
                                                  Прошу прощения, во втором варианте явный косяк, нулевой элемент не обрабатывался, т.к. i не достигнет нуля.
                                                  Вот поправленное:
                                                  int i=0;
                                                  int temp;
                                                  while (n>-1) {
                                                    if ((--i)<0) i=(--n)-1; // контроль двойного цикла
                                                    if (ar[n] < ar[i]) {
                                                           temp = ar[n];
                                                           ar[n] = ar[i];
                                                           ar[i] = temp;
                                                    }
                                                  }
                                                  
                                                  
                                                    0
                                                    Тьфу ежкин кот. Сам себя запутал ))
                                                    Одно поменял, второе забыл.
                                                    Последняя итерация же нафиг не нужна, равно как и что-либо делать при n=1.
                                                    Вот теперь правильно, никаких лишних действий, последняя и единственная для данного n итерация произойдет при n=1, но строго только если изначально было n>1:
                                                    int i=0;
                                                    int temp;
                                                    while (n>1) {
                                                      if ((--i)<0) i=(--n)-1; // контроль двойного цикла
                                                      if (ar[n] < ar[i]) {
                                                             temp = ar[n];
                                                             ar[n] = ar[i];
                                                             ar[i] = temp;
                                                      }
                                                    }
                                                    

                                                      0
                                                      Ну тогда уж приведу и поправленный первый вариант:
                                                      int i, temp;
                                                      while ((--n)>0) {
                                                        i=n;
                                                        while ((i--)>0) if (ar[n] < ar[i]) {
                                                               temp = ar[n];
                                                               ar[n] = ar[i];
                                                               ar[i] = temp;
                                                        }
                                                      }
                                                      

                                                      Исправлен тот же косяк с лишней итерацией.
                                                      Утром спешил на работу, писал впопыхах перед отъездом, поэтому за первичные косяки простите, был напуган (с) )))
                                                    +2
                                                    троллейбус_из_буханки_хлеба.жпг
                                                      0
                                                      k=(sqrt((a-b)^2)/(a-b))/2 а>b=1 a<b=0
                                                      not_k=sqrt((-1+k)^2)
                                                      b=(a+b)*k+b*not_k
                                                      a=(b-a)*k+a*not_k
                                                      b=(b-a)*k+b*not_k
                                                        0
                                                        Ой, не ту кнопку коцнул, ну вобщем это избавление от ифа ну и избавление от доп. переменных заодно(к и нот_к введены токмо для удобочитаемости), только при a-b=0 получается 0/0 что не есть хорошо но думаю это тоже как нибудь решить можно
                                                          0
                                                          Ну и вдогонку добавлю что писал на коленке и соответственно не проверял, так что может вобще не сработать хотя вроде бы должно.
                                                            0
                                                            Ой таки да, обшибся, в первой строчке:
                                                            k=((sqrt((a-b)^2)/(a-b))+1)/2
                                                              0
                                                              собсно придумал как от деления на 0 избавиться заодно и с скосить чуток в одну или другую сторону ака < или <= релаизовать:
                                                              вместо (a-b) делаем (int)(a-b)+0,5 или (int)(a-b)-0,5
                                                        0
                                                        Имеем обычный «пузырек»
                                                        Только я один заметил, что это линейная сортировка!?
                                                          0
                                                          def qsort(a):
                                                              return a if len(a) < 2 else qsort(filter(lambda t: t < a[0], a)) + filter(lambda t: t == a[0], a) + qsort(filter(lambda t: t > a[0], a))
                                                          

                                                          Only users with full accounts can post comments. Log in, please.