Сергей Суровцев ©   (04.04.17 13:21) [20]
Да, Ваш вариант несомненно вошел бы в призеры.
Это и есть нестандартный подход к решению задач, что всегда высоко ценится.

Kerk ©   (04.04.17 20:03) [39]
Видишь ли, ты здесь не рефери.
см [38]

> Jeer ©   (04.04.17 20:05) [41]
>
> Kerk ©   (04.04.17 20:03) [39]
> Видишь ли, ты здесь не рефери.
> см [38]

Здесь не я рефери, здесь здравый смысл рефери. Условия задачи открыты каждому, ни одно из "решений" из поста [34] условиям не соответствует. Сочувствую.

Но я рад за студента. Он выбрал единственно верный вариант из предложенных.

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

Kerk ©   (04.04.17 20:08) [42]

Специально для тебя повторяю условия задачи:

- есть/создается массив random-целых (integer 32b) чисел;
- требуется отсортировать массив на месте или вывести на консоль по следующим правилам:
-- массив должен быть отсортирован так, чтобы слева от "центра" массива находились бы все четные числа по убыванию от начала к "центру", а справа - все нечетные по возрастанию от "центра" к концу массива.

Переработанный вариант от Суровцева для PascalABC.Net:
(ограничение - только ноль и положительные числа)

[codebox]
var
 ar: array of integer;
const
 maxValue = 60; // Max value of rnd
 maxLen = 19; // ar.Length

procedure Inv(ar: array of integer);
begin
 for var i := Low(ar) to High(ar) do
   if not Odd(ar[i]) then ar[i] := -ar[i];
end;

begin
// Init  
 SetLength(ar, maxLen);
 for var i := Low(ar) to High(ar) do
   ar[i] := random(MaxValue + 1);

 write('rnd= ', ar.Length,' ', ar);
 writeln();
 
 Inv(ar); ar.Sort(ar); Inv(ar);
 
 write('rnd= ', ar.Length,' ', ar);
 writeln();
end.

[/codebox]

O! codebox здесь не работает.. :(

P.S.
Красиво, что еще можно сказать.

> Jeer

На самом деле ограничения легко убираются:

 for i:=0 to Length(Arr)-1 do Arr[i]:=(Arr[i] xor m) shr 1 xor -(Arr[i] and 1 xor 1);
 Sort(Arr);
 for i:=0 to Length(Arr)-1 do Arr[i]:=(Arr[i] shl 1 xor m) xor -(Arr[i] shr 31) xor 1;


В функцию Cmp из [2] вкралась ошибочка,
забыл учесть обратный порядок сортировки для четных.
Исправленая функция сравнения и несколько других до кучи:

const
 m=-MaxInt-1;

//неотрицательные числа: четные по возрастанию, затем нечетные по возрастанию
function Cmp1(i1, i2: integer): integer;
begin;
 i1:=i1 shr 1 xor i1 shl 31 xor m;
 i2:=i2 shr 1 xor i2 shl 31 xor m;
 if i1 xor i2>=0
 then i1:=i1-i2
 else i1:=i1 or 1;
 Result:=i1;
 end;

//неотрицательные числа: четные по убыванию, затем нечетные по возрастанию
function Cmp2(i1, i2: integer): integer;
begin;
 i1:=i1 shr 1 xor -(i1 and 1 xor 1);
 i2:=i2 shr 1 xor -(i2 and 1 xor 1);
 if i1 xor i2>=0
 then i1:=i1-i2
 else i1:=i1 or 1;
 Result:=i1;
 end;

//произвольные числа: четные по возрастанию, затем нечетные по возрастанию
function Cmp1a(i1, i2: integer): integer;
begin;
 i1:=i1 xor m; i1:=i1 shr 1 xor i1 shl 31 xor m;
 i2:=i2 xor m; i2:=i2 shr 1 xor i2 shl 31 xor m;
 if i1 xor i2>=0
 then i1:=i1-i2
 else i1:=i1 or 1;
 Result:=i1;
 end;

//произвольные числа: четные по убыванию, затем нечетные по возрастанию
function Cmp2a(i1, i2: integer): integer;
begin;
 i1:=(i1 xor m) shr 1 xor -(i1 and 1 xor 1);
 i2:=(i2 xor m) shr 1 xor -(i2 and 1 xor 1);
 if i1 xor i2>=0
 then i1:=i1-i2
 else i1:=i1 or 1;
 Result:=i1;
 end;

//произвольные числа по возрастанию
function Cmp0(i1, i2: integer): integer;
begin;
 if i1 xor i2>=0
 then i1:=i1-i2
 else i1:=i1 or 1;
 Result:=i1;
 end;


Ок, ты как и всегда - четок и краток, хотя и непонятен для начинающих студентов :)

> Kerk

Доморощенные функции могут быть не хуже библиотечных.

Скорость работы HybridSortSha_AII отсюда http://guildalfa.ru/alsha/node/10
сильно зависит от функции сравнения и пред/постобработки:
со сравнением Cmp2a: 100000 - 16мс, 1000000 - 172мс, 10000000 - 1856мс
с [48] и со сравнением Cmp0: 100000 - 16мс, 1000000 - 110мс, 10000000 - 1295мс

Скорость работы ShaRadixSort отсюда http://guildalfa.ru/alsha/node/21
гораздо выше и не зависит от функции получения ключа:
со функцией ShaRadixKeyJeer: 100000 - 0мс, 1000000 - 32мс, 10000000 - 265мс
с [48] и с функцией ShaRadixKeyInteger: 100000 - 0мс, 1000000 - 32мс, 10000000 - 265мс

ShaRadixKeyInteger есть по приведенной ссылке, а ShaRadixKeyJeer тут:

function ShaRadixKeyJeer(Item: pointer): integer;
begin;
 Result:=(integer(Item) xor m) shr 1 xor (-(integer(Item) and 1 xor 1)) xor m;
 end;


> Sha ©

Я не устаю удивляться твоей ловкости с битами. Никогда наверно не пойму как ты это делаешь :)

Допилил 64-битный вариант:

Всего элементов: 100000
Четных: 49836
Нечетных: 50164

Сортировка по четности: 0,001 сек.
Сортировка четных: 3,703 сек.
Сортировка нечетных: 3,547 сек.
Всего: 7,25 сек.

Возможно не самый быстрый и компактный вариант, зато не нагуглил ;)

program Sort64;

{$APPTYPE CONSOLE}

uses
 System.SysUtils, Windows;

var
 sA: uint64;
 //a: array[0..7] of integer = (50,62,31,45,41,85,70,75);

procedure SwapInt(const i1, i2: pointer);
asm
 .NOFRAME
 mov r9d, [i1]
 mov r10d, [i2]
 mov [i2], r9d
 mov [i1], r10d
end;

procedure DoHigh(EvenIndex: int64);
//while (EvenIndex >= 0) do
//begin
 //for i := 0 to (EvenIndex - 1) do FirstHigh(sA + (i shl 2));
 //Dec(EvenIndex);
//end;
asm
 .NOFRAME
 movq xmm0, rsi
 movq xmm1, rcx
 movq xmm2, rbx
 movq xmm3, rdx

 mov rsi, sA //Адрес первого элемента

 mov rbx, EvenIndex //while (EvenIndex >= 0) do
 cmp rbx, 1
 jl @@C //Пропусти значения меньше единицы, иначе нижняя граница превысит пределы
 dec rbx //Отнимаем идиницу, чтобы не превысить границу EvenIndex, т.к. [r11+4]

@@C: //while (EvenIndex >= 0)

 xor rcx, rcx //i := 0
 dec rcx

@@N:
 inc rcx

 mov r11, rcx //i = r11
 shl r11, 2
 add r11, rsi

 mov eax, [r11]
 mov edx, [r11+4]
 cmp eax, edx
 jge @@NP //Если первое выше или равно, то ничего не делаем

 mov [r11+4], eax
 mov [r11], edx

@@NP:

 cmp rcx, rbx
 jl @@N

 dec rbx
 cmp rbx, 0
 jge @@C  //while (EvenIndex >= 0) do

 movq rsi, xmm0
 movq rcx, xmm1
 movq rbx, xmm2
 movq rdx, xmm3
end;

procedure DoLow(OddIndex: int64; K: int64);
//while (k <> OddIndex) do
//begin
//  for i := OddIndex to (k - 1) do FirstLow(sA + (i shl 2));
//  Dec(k);
//end;
asm
 .NOFRAME
 movq xmm0, rsi
 movq xmm1, rcx
 movq xmm2, rbx
 movq xmm3, rdx

 mov rsi, sA //Адрес первого элемента

 mov rbx, OddIndex

 mov r8, K

@@C:
 mov rcx, rbx //for i := OddIndex
 dec rcx

 mov r10, r8 //to (k - 1)
 dec r10

@@N:
 inc rcx

 mov r11, rcx //i = r11
 shl r11, 2
 add r11, rsi

 mov eax, [r11]
 mov edx, [r11+4]
 cmp eax, edx
 jle @@NP //Если первое ниже или равно, то ничего не делаем

 mov [r11+4], eax
 mov [r11], edx

@@NP:

 cmp rcx, r10
 jne @@N

 dec r8 //Dec(K)
 cmp r8, rbx
 jne @@C

 movq rsi, xmm0
 movq rcx, xmm1
 movq rbx, xmm2
 movq rdx, xmm3
end;

procedure OutText(a: array of integer; H: integer);
var
 i: integer;

begin
 Write('[');
 for i := 0 to (H - 1) do
   Write(IntToStr(a[i]) + ',');
   Write(IntToStr(a[H]));
 Write(']');
 Writeln;
end;

var
 A: array of integer;
 NumElements, H, i: integer;
 OddIndex, EvenIndex: integer;
 ST, ET, ET1, ET2: cardinal;
 TT, TT1, TT2, TT3: double;
 DoOut: boolean;

begin
 //Кол-во элементов в массиве
 NumElements := 100000;

 //Флаг вывода текста
 if (NumElements > 40) then
   DoOut := false else
   DoOut := true;

 Randomize;
 SetLength(A, NumElements);

 H := High(A);
 for i := 0 to H do A[i] := Random(100);

 //Адрес первого элемента
 sA := uint64(@A[0]);

 //Вывод массива
 if DoOut then OutText(A, H);

 //Стартовые индексы
 EvenIndex := 0;
 OddIndex := H;

 ST := GetTickCount;

 //Этап 1
 //Сортировка по четности
 while (EvenIndex < OddIndex) do
 begin
   //Если число нечетное, то сдвигаем в конец
   if ((A[EvenIndex] and 1) = 1) then
   begin
     SwapInt(@A[EvenIndex], @A[OddIndex]);
     Dec(OddIndex);
   end
   else Inc(EvenIndex);
 end;

 //Выясним где граница
 if (A[EvenIndex] and 1) = 1 then Dec(EvenIndex);
 if (A[OddIndex] and 1) = 0 then Inc(OddIndex);

 //Вывод массива
 if DoOut then OutText(A, H);

 //Конец первого этапа
 ET1 := GetTickCount;

 Writeln('Всего элементов: ' + IntToStr(H + 1));
 Writeln('Четных: ' + IntToStr(EvenIndex + 1));
 Writeln('Нечетных: ' + IntToStr(H - OddIndex + 1));
 Writeln;

 //Этап 2
 //Сортировка четных со сдвигом к меньшему
 //Индекс должен быть боле нуля, т.к.
 //элементов для сравнения должно быть минимум 2
 if ((EvenIndex + 1) > 1) then DoHigh(EvenIndex);

 //Конец второго этапа
 ET2 := GetTickCount;

 //Этап 3
 //Сортировка нечетных со сдвигом к большему
 //Кол-во элементов для сравнения должно быть минимум 2
 if ((H - OddIndex + 1) > 1) then DoLow(OddIndex, H);

 //Конец последнего этапа
 ET := GetTickCount;

 //Засекаемый минимум
 TT := 0.001;
 TT1 := TT;
 TT2 := TT;
 TT3 := TT;

 if (ET - ST) > 0 then TT := ((ET - ST) / 1000);
 if (ET1 - ST) > 0 then TT1 := ((ET1 - ST) / 1000);
 if (ET2 - ET1) > 0 then TT2 := ((ET2 - ET1) / 1000);
 if (ET - ET2) > 0 then TT3 := ((ET - ET2) / 1000);

 //Вывод массива
 if DoOut then OutText(A, H);

 Writeln('Сортировка по четности: ' + FloatToStr(TT1) + ' сек.');
 Writeln('Сортировка четных: ' + FloatToStr(TT2) + ' сек.');
 Writeln('Сортировка нечетных: ' + FloatToStr(TT3) + ' сек.');
 Writeln('Всего: ' + FloatToStr(TT) + ' сек.');

 SetLength(A, 0);
 A := nil;

 Readln;
end.

> Kerk ©   (05.04.17 02:13) [52]
> Никогда наверно не пойму...

Заклинания настоящей магии тут https://graphics.stanford.edu/~seander/bithacks.html

P.S. Мир видится иначе сквозь призму графического адаптера )

> dmk

Есть несколько предложений по коду [53].

1. Флаг вывода текста можно вычислить без if:
DoOut:=(NumElements<=40);

2. Сортировка по четности будет работать быстрее и без лишних перестановок элементов,
если оба EvenIndex и OddIndex будут бежать навстречу друг другу,
ища элементы, которые надо переставить как в алгоритме быстрой сортировки QuickSort,
а затем переставлять их.

3. Скорость работы алгоритмов сортировки слабо зависит от языка (обычно не более 3 раз),
но сильно зависит от алгоритма (десятки и более раз).
Поэтому в первую очередь имеет смысл сосредоточиться на алгоритме.

4. Изучение и замеры скорости разнообразных опубликованных алгоритмов сортировки -
неиссякаемый источник вдохновления и грусти )

>Sha ©   (05.04.17 10:01) [55]
>2. Сортировка по четности будет работать быстрее
Это не самое узкое место: 100 млн за 0.6 сек.

>источник вдохновления и грусти
Просто выжал из этого алгоритма максимум. Думаю над другим.

> Всего элементов: 100000


> Всего: 7,25 сек.


Чего так долго ?

>Sha ©   (04.04.17 23:01) [48]
>На самом деле ограничения легко убираются:

Красиво! Практическая магия. ))
На Delphi работает идеально, а вот на C# не проканало...

Этот вариант, конечно попроще, но должен пройти на любом ЯП. ))




>Jeer ©   (04.04.17 21:36) [45]
>ограничение - только ноль и положительные числа

Ограничение на положительные снято. С нулем есть 2 варианта. Если не обрабатывать, он встанет ровно посередине между четными и нечетными. Можно и обрабатывать, сейчас он для примера закинут в ветку нечетных.

P.S.
В условиях говорится о массиве целых чисел, а не о целочисленном массиве. ))

Меньше циклов, веселее жизнь

           for (int i = 0; i < rnd.Length; i++)
           {
               if (rnd[i] < 0)
               {
                   if (rnd[i] % 2 == 0) rnd[i] = 1 / rnd[i];
                   else rnd[i] = 1 / rnd[i] * (-1);
               }
               if (rnd[i] % 2 == 0 && rnd[i] > 1) rnd[i] = rnd[i] * (-1);
               if (rnd[i] == 1) rnd[i] = rnd[i] + 0.1;
               if (rnd[i] == 0) rnd[i] = 1;
           }
           Array.Sort(rnd);
           for (int i = 0; i < rnd.Length; i++)
           {
               if (rnd[i] % 2 == 0 && rnd[i] < -1) rnd[i] = rnd[i] * (-1);
               if (rnd[i] < 0 && rnd[i] > -1) rnd[i] = 1 / rnd[i];
               if (rnd[i] > 0 && rnd[i] < 1) rnd[i] = 1 / rnd[i] * (-1);
               if (rnd[i] == 1) rnd[i] = 0;
               if (rnd[i] == 1.1) rnd[i] = 1;
           }