Есть ли связь между сортировкой и преоб Фурье?

[erwins]

можно ли с помощью преобразования Фурье (прямого и обратного) отсортировать массив?
Если функциональная связь данных алгоритмов

[Евгений Машеров]

Нет. Нельзя. Несмотря на то, что некоторая аналогия в структуре алгоритмов БПФ и некоторых алгоритмов сортировки существует.

[erwins]

спасибо. У кого можно прочитать про обоснования не возможности и следствия из этого.

[Pavia]

Вопрос не корректный. Что значит с помощью преобразования Фурье сделать сортировку?
Я могу к примеру определить MySort как MySort=QSort(IFFR(FFT(a))) это значит что я сделал сортировку c помощью Фурье или не значит?

[erwins]

Точнее формулирую.

Существует ли обобщающая функция f(X, (x,x)->x) после свертки дающая
sort(X)=f(X,(x1,x2)->(x1>x2)?(x1,x2):(x2,x1))
fuer(X)=f(X,(x1,x2)....)

либо как вариант выполняющий сортировку с использованием константного числа преобразования фурье и количества операций операций пропорциональное числу элементов

[Chifu]

Между всеми алгоритмами есть связь - все они состоят из блоков, ветвлений и циклов :). Сортировка происходит по какому-то критерию, преобразование Фурье даёт упорядоченные данные - спектр. Почитайте "Алгебраическая алгоритмика", там должно быть что-то такое, хотя я может быть путаю с умножением полиномов.

[Circiter]

2erwins

Цитата:

Существует ли обобщающая функция f(X, (x,x)->x) после свертки дающая...

Увы, совершенно не понятно, что вам нужно. Кстати, не представляю как вообще можно сортировку выполнять через свертку, надо подумать...

Хотя вопроса вашего не понял и искомую функцию предложить не смогу, но попробую пофантазировать.

Например, пусть вместо вашей "(x,x)->x" будет просто функция g_sort с побочным эффектом, что-то вроде (это даже не псевдокод, а какой-то небрежный слепок потока сознания :) ):

y[]

g_sort(i, j)
{
    if(j>=n-1) return;

    if(y[j]>y[j+1])
        swap(y[j], y[j+1]);
}

Это я её под сортировку пузырьком подогнал. Тогда f будет примерно такой:

f(x[], g)
{
    y=x;

    for(i=0; i<length(x); i++)
        for(j=0; j<length(y); j++)
            g(i, j);

    x=y;
}

А можно, существенно не изменяя f, подсунуть ей вместо g_sort другую функцию g_dft:

g_dft(i, j)
{
    re[i]+=y[j]*cos(2*pi*i*j/length(y));
    im[i]-=y[j]*sin(2*pi*i*j/length(y));
}

В результате:

sort(x[]) {f(x, g_sort);}
fourier(x[]) {f(x, g_dft);}

Если свернуть побочные эффекты (офункционализировать код :) ) и реализовать более адекватную схему сортировки, e.g. вариацию на тему сортирующих сетей, то что-то близкое к требуемой вами f(...) может быть и получится (а может быть в моей писанине и вовсе нет никакого смысла :) )...

Но как это связано с первоначальным вопросом? :)

[erwins]

просто. Есть сортировка Хола имеющая порядок для конечного домена $n\ln(\ln(n))2^{\ln!(n)}$ где $\ln!(n)$ суперлогорифм
Возможно ли изменение преобразования фурье аналогичным образом?

[Pavia]

Что-то я такой сортировки не найду. Ни в книжке Холла не в книге Кнута. Откуда вы её взяли?

[erwins]

Извияюсь, Хана, вот только у Кнута ее быть не могло, так как она появилась в 2002
http://web.mit.edu/benmv/Public/thorup.pdf

[AlexDem]

Свёртка ведь соответствует действию линейного фильтра на некоторый сигнал, а преобразование Фурье позволяет заменить свёртку функций умножением. Сигнал здесь - последовательность значений $X$. Оператор сортировки $F: X \to N$ отображающий множество значений $X$ на множество порядковых номеров $N$, если он линеен, не должен зависеть от предыстории, то есть должен определять номер по значению локально, что в случае сортировки невозможно. То есть $F$ у нас - нелинейный и свёрткой не представим. Вроде так?

[Circiter]

2erwins
Спасибо за ссылку, надо будет почитать.

Возможно вам будет интересна вот эта странная тема: количество сложений и умножений при вычислении формул.

[Pavia]

Circiter
Возьмём сортировку пузырьком и на её основе построим через преобразование Фурье.
Берем Фурье переходим в спектральную область.
Дальше делаем пузырьковую сортировку. Сравнение есть, вычитание двух элементов и сравнение знака.
Вычитание для спектральной области заменимо свёрткой (аналогично дифференцирования) или можно через две свёртке с вычитанием.
Что касается обмена элементов, то это можно проделать через 2 операции вычитания и сравнения знака.

erwins

Цитата:

преобразование Фурье есть n*ln(n) и есть ли вероятность что возможен шаг похожий на сортировку Хола

как и в случае обычной сортировки, преобразование Фурье на произвольном кольце имеет порядок n*ln(n)

в тоже время, если в сортировке добавить требование конечности кольца, то удается получить порядка n*ln(ln(n))*2^(ln*(n)) что значительно меньше.

Есть по разрядная сортировка, которая выполняется за O(n), а есть обычная быстрая сортировка O(n*Log(n))
Вполне логично что мы можем построить сортировку по скорости между этими двумя.

Что касается преобразования Фурье. То его можно делать через свёртку. Свёртка может быть O(n).
Вот в конечном поле бпф можно делать быстрее чем O(n*log(n)) умножений. Но полноценного доказательства у меня нету.