Про необходимость for(each)

[DIzer]

Вот в один прогон. Вроде, не накосячил. Есть поле для оптимизации.

Код: [Выделить]

cl, cr, x, tmp : INTEGER;

x := 0;
cl := 0;
cr := LEN( a );
WHILE x < cr DO
IF a[x] = 1 THEN
tmp := a[cl]; a[cl] := a[x]; a[x] := tmp;
cl := cl + 1;
ELSIF a[x] = 3 THEN
tmp := a[cr]; a[cr] := a[x]; a[x] := tmp;
cr := cr + 1;
END
x := x + 1
END

Да поле есть -  в частности если в определите массив из  четырех чисел temp то подсчет упрощается  сводится к  INC(TEMP[a]) -- но фиг думать - это классика

[vlad]

INC(TEMP[a]) -- но фиг думать - это классика

Вы не о том думаете Думать надо о сопровождении. По умолчанию. Потому что сопровождающий программист будет думать о вас очень плохо, когда матерясь будет выхерачивать ваш велосипед и менять его на банальную (без выпендрежа) строчку "std::sort", потому что у кастомера ваш мегакод случайным образом глючит, потому что таки в массиве стали появляться цифры 4 (и это абсолютно валидный случай после того как систему расширили добавив новый тип какой-нибудь херни).

P.S. Конечно если вы пишите на обероне... И вам все равно надо херачить сортировку... То грех не воспользоваться случаем и не написать свою уникальную Что, впрочем, не отменяет все тех же проблем при появлении цифры 4

P.S.S. Да, да - ни в одном велосипеде не было соответствующего ASSERT. Что как бы намекает, что думают совсем не о том

[DIzer]

Вы не о том думаете Думать надо о сопровождении. По умолчанию. Потому что сопровождающий программист будет думать о вас очень плохо, когда матерясь будет выхерачивать ваш велосипед и менять его на банальную (без выпендрежа) строчку "std::sort", потому что у кастомера ваш мегакод случайным образом глючит, потому что таки в массиве стали появляться цифры 4 (и это абсолютно валидный случай после того как систему расширили добавив новый тип какой-нибудь херни).

P.S. Конечно если вы пишите на обероне... И вам все равно надо херачить сортировку... То грех не воспользоваться случаем и не написать свою уникальную Что, впрочем, не отменяет все тех же проблем при появлении цифры 4

P.S.S. Да, да - ни в одном велосипеде не было соответствующего ASSERT. Что как бы намекает, что думают совсем не о том

  Не надо делать из  мухи слона - в данном случае абсолютно  стандартная реализация сортировки подсчетом+заведомо тот случай когда ТРЕБОВАЛОСЬ написать УНИКАЛЬНЫЙ вариант -смысл в  том, что нефиг думать - классика жанра (стандартное решение БЕЗ мозго-ства).
ЗЫ А вообще - то не фиг вырывать часть фразы из контекста  - напрягитесь и прочитайте ее хотя бы С НАЧАЛА до конца (думал Валерий - я ПРОСТО ОТВЕТИЛ на его ОПТИМИЗАЦИЮ стандартным решением)  я уж не говорю про сообщение вызвавшее этот OFFSPIN).

[DIzer]

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

[Peter Almazov]

Вы не о том думаете Думать надо о сопровождении. По умолчанию.

Vlad, это вы не о том думаете. Я предлагаю вам лично решить простую задачу. Без всякого сопровождения. Или вы хотите сказать: "Я крутой чувак, но такую ерунду решить не в состоянии". А самолюбие где?

[igor]

думал Валерий - я ПРОСТО ОТВЕТИЛ на его ОПТИМИЗАЦИЮ

Мотороллер не мой! Я просто разместил объяву

(Извините! Не удержался.  )

[alexus]

Вот в один прогон. Вроде, не накосячил.

Всё же... накосячил...
Оператор cr := cr + 1; (строка 12), надо заменить на cr := cr - 1;

[DIzer]

думал Валерий - я ПРОСТО ОТВЕТИЛ на его ОПТИМИЗАЦИЮ

Мотороллер не мой! Я просто разместил объяву

(Извините! Не удержался.  )

Да не за что  - один черт не понял к чему это. Хотя нет - если ваше сообщение есть демонстрация способностей использования тегов [url /url] - то прощаю (зачетная демонстрация).

[DIzer]

Vlad, это вы не о том думаете. Я предлагаю вам лично решить простую задачу. Без всякого сопровождения. Или вы хотите сказать: "Я крутой чувак, но такую ерунду решить не в состоянии". А самолюбие где?

    Ловля на "понты" -  а с какой стати он ДОЛЖЕН это делать, тем более если вы не удосужились даже толком обьяснить за чем это (то есть увеличить  ценность бессмысленной работы).

[Peter Almazov]

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

[DIzer]

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

На таких задачах ?    ,  впрочем, каждому свое (если, конечно, на самом деле это не "примитивная" попытка  достать человека).

[Peter Almazov]

На таких задачах ?

Что имеется в виду? Очень простых или очень сложных?
Это, конечно, не попытка "достать" человека. Я к vlad'у отношусь очень хорошо. Еще с тех пор, когда он писал на оберонкоре.

[Губанов Сергей Юрьевич]

Вот в один прогон. Вроде, не накосячил.

Всё же... накосячил...
Оператор cr := cr + 1; (строка 12), надо заменить на cr := cr - 1;

Ещё надо в начале cr := LEN(a); заменить на cr := LEN(a) - 1;

А идея классная. Лучше чем мой индусский вариант.

[Berserker]

Отказ от break/continue - это та самая поддержка и возможность безопасной доработки цикла в будущем. Выгода в ясности/надёжности превосходит время, единожды потраченное на понимание сути техники.

Сортировка массива на Объектном Паскале:

Код: (delphi) [Выделить]

PROCEDURE Sort (VAR Arr: TIntArray; MinValue, MaxValue: INTEGER);
CONST
  MAX_RANGE = 1000;

VAR
  NumItems:   INTEGER;
  ItemInd:    INTEGER;
 
  Range:      INTEGER;
  RangeArr:   TIntArray;
  FillValue:  INTEGER;
 
  i:          INTEGER;
  j:          INTEGER;
   
BEGIN
  {!} ASSERT(MinValue <= MaxValue);
  Range :=  MaxValue - MinValue + 1;
  {!} ASSERT(Range <= MAX_RANGE);
  NumItems  :=  LENGTH(Arr);
 
  IF NumItems > 1 THEN BEGIN
    SetLength(RangeArr, Range);
   
    FOR i := 0 TO Range - 1 DO BEGIN
      RangeArr[i] :=  0;
    END; // .FOR
   
    FOR i := 0 TO NumItems - 1 DO BEGIN
      {!} ASSERT(Math.InRange(Arr[i], MinValue, MaxValue));
      INC(RangeArr[Arr[i] - MinValue]);
    END; // .FOR
   
    FillValue :=  MinValue;
    ItemInd   :=  0;
   
    FOR i := 0 TO Range - 1 DO BEGIN   
      FOR j := 1 TO RangeArr[i] DO BEGIN
        Arr[ItemInd]  :=  FillValue;
        INC(ItemInd);
      END; // .FOR
     
      INC(FillValue);
    END; // .FOR
  END; // .IF
END; // .PROCEDURE Sort

[vlad]

Вы не о том думаете Думать надо о сопровождении. По умолчанию.

Vlad, это вы не о том думаете. Я предлагаю вам лично решить простую задачу. Без всякого сопровождения. Или вы хотите сказать: "Я крутой чувак, но такую ерунду решить не в состоянии". А самолюбие где?

Хорошему программисту самолюбие надо душить, как и чувство перфекционизма Именно это я и хотел сказать своим std::sort.
Оригинальный посыл вполне понятен - задача, укладывающаяся в рамки "шаблонного" решения, но имеющая намного более эффективное оригинальное решение (относительно оригинальное, конечно все придумано до нас, хотя лично я решения с подсчетом/приравниванием и не знал, расписываюсь в своей серости).
Если вам хотелось увидеть это оригинальное решение от меня лично - надо было прямо сказать, а не рассуждать про "нормальность" Я считаю, что смог бы  придумать однопроходный вариант O(n) с перестановками - аналог Valery Solovey. Если у вас есть еще более оригинальное/эффективное решение - можете им похватстать, потому что до него я бы уже вряд ли додумался