Сортировка «демоном Максвелла» [Язык Си]

[Fyn]

Может кто-нибудь на примере кода объяснить сортировку «демоном Максвелла», заранее благодарю.
Тут описана сортировка «демоном Максвелла»---->https://habrahabr.ru/post/161835/

[Николай Соленый]

http://algolab.valemak.com/maxwell-demon
здесь человек пишет что его сложность
O(n! + [n/2]! + [n/4]! + [n/8]! + ... + 1!)
то есть он вообще не думоит

https://habr.com/post/161835/
также не ясно почему этот алгоритм оказался в этой шуточной статье

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

да даже в лабораторке задание вон с 2мя ошибками(jpg файл)

Я, должно быть поздновато вам отвечаю на вопрос, но вы просто знайте, что алгоритм неплох тем, что просто пишется и запоминается, не требователен к памяти (O(n)) и сложность по времени близка к O(n*log2n)

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

Завтра пойду смотреть в круглые глаза препода. Потому что он, когда копипастил задачу, наверное тоже думал что это еще один богосорт.

void DMaxwell(int *arr, int len) {
if(len == 1)
return;
if(len == 2) {
if(arr[0]>arr[1]) len=arr[0], arr[0]=arr[1], arr[1]=len;
return;
}

int *dat = malloc(4*len),
lb = 0, rb = len-1,
lmax = arr[0], rmin = arr[len/2];

for(int i = 0; i < len/2; i++)
if(arr[i] > lmax)
lmax = arr[i];
for(int i = len/2; i < len; i++)
if(arr[i] < rmin)
rmin = arr[i];

while(rmin<lmax) {
lb = 0, rb = len-1;

for(int i = 0; i < len/2; i++)
if(arr[i] <= rmin) dat[lb++] = arr[i];
else dat[rb--] = arr[i];
for(int i = len/2; i < len; i++)
if(arr[i] > lmax) dat[rb--] = arr[i];
else dat[lb++] = arr[i];

for(int i = 0; i < len; i++)
arr[i] = dat[i];

lmax = arr[0], rmin = arr[len/2];
for(int i = 0; i < len/2; i++)
if(arr[i] > lmax)
lmax = arr[i];
for(int i = len/2; i < len; i++)
if(arr[i] < rmin)
rmin = arr[i];
}
free(dat);
DMaxwell(arr, len/2);
DMaxwell(arr+len/2, len/2+len%2);
}

[Cryoto]

Сообщение от Николай Соленый

http://algolab.valemak.com/maxwell-demon
здесь человек пишет что его сложность
O(n! + [n/2]! + [n/4]! + [n/8]! + ... + 1!)
то есть он вообще не думоит

https://habr.com/post/161835/
также не ясно почему этот алгоритм оказался в этой шуточной статье

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

да даже в лабораторке задание вон с 2мя ошибками(jpg файл)

Я, должно быть поздновато вам отвечаю на вопрос, но вы просто знайте, что алгоритм неплох тем, что просто пишется и запоминается, не требователен к памяти (O(n)) и сложность по времени близка к O(n*log2n)

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

Завтра пойду смотреть в круглые глаза препода. Потому что он, когда копипастил задачу, наверное тоже думал что это еще один богосорт.

void DMaxwell(int *arr, int len) {
if(len == 1)
return;
if(len == 2) {
if(arr[0]>arr[1]) len=arr[0], arr[0]=arr[1], arr[1]=len;
return;
}

int *dat = malloc(4*len),
lb = 0, rb = len-1,
lmax = arr[0], rmin = arr[len/2];

for(int i = 0; i < len/2; i++)
if(arr[i] > lmax)
lmax = arr[i];
for(int i = len/2; i < len; i++)
if(arr[i] < rmin)
rmin = arr[i];

while(rmin<lmax) {
lb = 0, rb = len-1;

for(int i = 0; i < len/2; i++)
if(arr[i] <= rmin) dat[lb++] = arr[i];
else dat[rb--] = arr[i];
for(int i = len/2; i < len; i++)
if(arr[i] > lmax) dat[rb--] = arr[i];
else dat[lb++] = arr[i];

for(int i = 0; i < len; i++)
arr[i] = dat[i];

lmax = arr[0], rmin = arr[len/2];
for(int i = 0; i < len/2; i++)
if(arr[i] > lmax)
lmax = arr[i];
for(int i = len/2; i < len; i++)
if(arr[i] < rmin)
rmin = arr[i];
}
free(dat);
DMaxwell(arr, len/2);
DMaxwell(arr+len/2, len/2+len%2);
}

Проблема, которую необходимо решить, но я бессилен. Почему-то malloc требует тип void* и не хочет переобразовываться в int*

[p51x]

Не требует, а возвращает. Не почему-то, а потому что это "указатель на все". Сделайте приведение типов или раз уж пишите на С++ используйте new.