Сортировка массива методом вставки в несколько потоков

#массивы #c #алгоритм #cpp

Какие идеи есть, чтобы отсортировать массив элементов в n потоков методом вставки?    

Ответы

Ответ 1

Делим массив на n частей, сортируем каждую в отдельном потоке "вставками", а частичные
результаты сливаем в один "слиянием", которое так же можно рекурсивно распараллеливать,
если надо.


Ответ 2

@mega, вот ведь беда с этим лимитом комментариев. Приходится в ответе на вопрос отвечать
на Ваш комментарий.
Ну, хорошо. Опять возвращаемся к тому что было: Ваше понятие устойчивости ни как
не влияет на сборку массива, о которой я говорю изначально, т.к. порядок следования
элементов в сортировке вставками соблюдается переносом этих элементов в любом случае,
а в быстрой сортировке этот порядок соблюдается без переноса, это очень важное качество
алгоритма, т.к. объем перемещаемых данных на вставках составляет 100%, исключая первый
элемент, в отличие от быстрой сортировки или любой другой сортировки с аналогичным
свойством, поэтому она здесь наиболее приемлема.


В сортировке вставками элемент перемещают (обменом с предыдущим (для сортировки по
возрастанию)) до тех пор, пока он меньше предыдущего. Если не ошибаюсь в среднем получится
(N^2)/4 обменов. В случае уже упорядоченного массива обменов вообще не будет. Для массивов
в которых много уже упорядоченных последовательностей число обменов будет мало.
Совершенно не понял фразу: "...а в быстрой сортировке этот порядок соблюдается без
переноса"

Вы считаете, что элемент массива, выбранный в качестве разделяющего не перемещается
(путем обменов) по массиву? 
Уверяю Вас, перемещается, ровно столько раз, сколько слева от него (после очередного
обмена) оказывается больший или справа меньший. Другой вопрос, что в случае quicksort
эти перемещнеия делят массив пополам (ну, это в идеале) и дальше перемещения (и сравнения!)
проводятся только в уже разделенных частях. Именно поэтому (обязательно надо учтитывать
количество сравнений) сложность quicksort будет O(N log N).