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

Тема в разделе "WASM.A&O", создана пользователем serega28, 3 ноя 2010.

  1. serega28

    serega28 Member

    Публикаций:
    0
    Регистрация:
    26 мар 2007
    Сообщения:
    115
    Адрес:
    Minsk
    Как это правильно реализовать.
    Я вот беру массив делю на попалам.
    Первую часть отдаю одному потоку, вторую другому.

    А потом финальная сортировка вставкой.

    Это так делается?
     
  2. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Почитайте википедию.
     
  3. serega28

    serega28 Member

    Публикаций:
    0
    Регистрация:
    26 мар 2007
    Сообщения:
    115
    Адрес:
    Minsk
    там не написан принцип многопоточной и параллельной сортировки
    как алгоритм работает я знаю
     
  4. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Тогда не вижу проблем, сортируйте каждую часть в отдельно.
     
  5. 100gold

    100gold New Member

    Публикаций:
    0
    Регистрация:
    26 фев 2010
    Сообщения:
    165
    Делить пополам а потом сливать - не очень хорошая идея, т.к. общее время будет равняться худшему из потоков. И если для 2,3,4 потоков разница между средним и худшим будет не столь существенна, то при массовом параллелизме простои будут очень большими.
     
  6. serega28

    serega28 Member

    Публикаций:
    0
    Регистрация:
    26 мар 2007
    Сообщения:
    115
    Адрес:
    Minsk
    А почему простои. Потоки блокироваться не будут т.к. каждый поток работает со своим куском данных.

    И в сортировке шелла не надо выполнять последний этап - сортировка вставками.
    Это сделается в самом конце одним потоком.

    Сравню результаты сколько времени в одном потоке, а сколько с несколькими потоками.