Сортировать по темам

У меня есть назначение, и мне нужен рабочий код. Прежде чем начать, я хочу понять проблему, но не могу понять, как ее написать.

У меня есть массив данных, например

var arr = new byte[] {5,3,1,7,8,5,3,2,6,7,9,3,2,4,2,1}

Мне нужно разделить этот массив пополам, выбросить его в пул потоков и делать это рекурсивно, пока у меня не будет элементов <=2. Если у меня есть 2 элемента, мне нужно проверить, что меньше, и поместить его в левую часть, а затем вернуть массив.

Что я не понимаю, как я могу объединить массив? я должен разделить массив, бросить поток в пул и заблокировать, пока он не будет готов? Как я могу получить результаты потока? Я собираюсь предположить, что невозможно объединить массивы без блокировки?

Вот что у меня так далеко.

    static void Main(string[] args)
    {
        var arr = new byte[] { 5, 3, 1, 7, 8, 5, 3, 2, 6, 7, 9, 3, 2, 4, 2, 1 };
        var newarr = Sort(arr);
        Console.Write(BitConverter.ToString(newarr));
    }
    static byte[] Sort(byte[] arr)
    {
        if (arr.Length <= 2)
            return arr;
        if (arr.Length == 2)
        {
            if (arr[0] > arr[1])
            {
                var t = arr[0];
                arr[0] = arr[1];
                arr[1] = t;
            }
            return arr;
        }

        var arr1 = arr.Take(arr.Length / 2).ToArray();
        var arr2 = arr.Skip(arr1.Count()).ToArray();
        //??
        return arr;
    }

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

Источник

3 ответа

Решение

Это похоже на параллельную версию сортировки слиянием. Вы должны существенно заставить его работать как рекурсивная последовательная версия, но, очевидно, запускать каждую рекурсивную сортировку как отдельную задачу.

В вашем API задачи должен быть какой-то способ дождаться завершения и, возможно, также передать результаты. При этом вы можете достаточно хорошо скопировать традиционную сортировку слиянием: для каждой под-сортировки поместите задачу в пул и дождитесь завершения двух подзадач. Затем выполните объединение и передайте свой собственный результат в задачу по вызову.

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

Источник

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

Источник

Более чем рад обязательству: любая реализация многоядерной сортировки в.NET?

Источник
Другие вопросы по тегам