مرتب سازی سریع بصورت موازی

با سلام
دوستان از این الگوریتم برای مرتب سازی سریع استفاده می کنیم حال برای موازی کردن این الگوریتم چه کاری باید انجام داد؟

public static int[] QuickSort(int[] Array, int Low, int High)

{

    if (Low < High)

    {

        int p = partition(Array, Low, High);

        QuickSort(Array, Low, p - 1);

        QuickSort(Array, p + 1, High);

    }

 

    return Array;

}

private static int partition(int[] Array, int Low, int High)

{

    int lb = Low + 1, rb = High, temp, pivot = Array[Low], p;

    while (lb <= rb)

    {

        while (Array[lb] <= pivot && lb <= rb)

            lb++;

        while (Array[rb] > pivot && lb <= rb)

            rb--;

        if (lb < rb)

        {

            temp = Array[lb];

            Array[lb] = Array[rb];

            Array[rb] = temp;

        }

    }

    if (rb == High)

        p = High;

    else if (rb == Low)

        p = Low;

    else

        p = lb - 1;

    Array[Low] = Array[p];

    Array[p] = pivot;

    return p;

}

اگه منظورت مرتب سازی آرایه هستش میتونی از کد زیر هم استفاده بکنیا این همه کد نویسی لازم نیست

Array.Sort(arrayname);

البته اگه منظورتو درست فهمیده باشم و میخوای آرایه هایی که توشون عدد هستن رو مرتب کنی

میتونی مثل merge sort نصف آرایتو با یه نخ نصف دیگشو با یه نخ دیگه به روش Quick sort مرتب کنی و از تابع merge استفاده کنی تا نتایج تو تا نخ رو با هم ادغام کنی. اگه میخوای درجه ی parallelism رو بالاتر ببری میتونی با تعداد بیشتری نخ این کار رو انجام بدی. نخ هات رو هم پارامتر دار بساز که بتونی رنج قسمتی رو که اون نخ قراره سورت کنه رو مشخص کنی. برای مساله ی concurrency هم میتونی یا قفل بذاری (که سرعت زیاد بالا نمیره و حتی پایین تر هم ممکنه بیاد) و میتونی آرایه رو کلا بشکونی که این روش بهتره.
-------
این کد رو با دو تا نخ نوشتم، زمان اجرا رو هم تقریبا به اندازه ی دو پنجم کاهش میده البته هر چقدر اعداد بیشتر باشن زمان اجرا با دو تا نخ تقریبا نصف میشه. میتونی از همین ایده استفاده کنی و تعداد نخ ها رو هم به صورت پویا تعریف کنی، یعنی با توجه به تعداد هسته های پردازنده و حجم آرایه:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Threading;

using System.Diagnostics;





namespace ConsoleApplication3

{

    class Program

    {

        static object mylock = new object();





        static public void MainMerge(int[] numbers, int left, int mid, int right)

        {

            int[] temp = new int[right+1];

            int i, eol, num, pos;





            eol = (mid - 1);

            pos = left;

            num = (right - left + 1);





            while ((left <= eol) && (mid <= right))

            {

                if (numbers[left] <= numbers[mid])

                    temp[pos++] = numbers[left++];

                else

                    temp[pos++] = numbers[mid++];

            }





            while (left <= eol)

                temp[pos++] = numbers[left++];





            while (mid <= right)

                temp[pos++] = numbers[mid++];





            for (i = 0; i < num; i++)

            {

                numbers[right] = temp[right];

                right--;

            }

        }





        struct mystruct

        {

            public int left;

            public int right;

        }

        static int[] array;

        public static void mythread(object number)

        {

            int[] localarray;





            mystruct num = (mystruct)number;





            int x = 0;

            int y = 0;





            if (num.left == 0)

                y = 1;

            else

                x = 1;





            localarray = new int[num.right - num.left+y];

            

            for (int i = 0; i < (num.right - num.left+y); i++)

            {

                localarray[i] = array[i + num.left];

            }

            

            QuickSort(localarray, 0, num.right - num.left-x);





            for (int i = 0; i < (num.right - num.left+y); i++)

            {

                array[i + num.left] = localarray[i];

            }





        }

        public static void ParallelSort(int items)

        {

            int mid;

            int right = items;

            int left = 0;

            mid = (right + left) / 2;

            

            mystruct s1 = new mystruct();

            s1.left = left;

            s1.right = mid;





            mystruct s2 = new mystruct();

            s2.left = (mid + 1);

            s2.right = right;





            Thread t1 = new Thread (new ParameterizedThreadStart(mythread));

            Thread t2 = new Thread (new ParameterizedThreadStart(mythread));





            t1.Start(s1);

            t2.Start(s2);





            t1.Join();

            t2.Join();





            MainMerge(array, left, (mid + 1), right-1);

        }

        public static int[] QuickSort(int[] Array, int Low, int High)

        {

            if (Low < High)

            {

                int p = partition(Array, Low, High);

                QuickSort(Array, Low, p - 1);

                QuickSort(Array, p + 1, High);

            }





            return Array;

        } 

        private static int partition(int[] Array, int Low, int High)

        {

            int lb = Low + 1, rb = High, temp, pivot = Array[Low], p;

            while ((lb <= rb))

            {

                while (Array[lb] <= pivot)

                {

                    lb++;

                    if (!(lb <= rb))

                        break;

                }

                while (Array[rb] > pivot)

                {

                    rb--;

                    if (!(lb <= rb))

                        break;

                }

                    

                if (lb < rb)

                {

                    temp = Array[lb];

                    Array[lb] = Array[rb];

                    Array[rb] = temp;

                }

            }

            if (rb == High)

                p = High;

            else if (rb == Low)

                p = Low;

            else

                p = lb - 1;

            Array[Low] = Array[p];

            Array[p] = pivot;

            return p;

        }





        static void Main(string[] args)

        {

            Random rnd = new Random(DateTime.Now.Millisecond);

            int number = 5000000;

            array = new int[number];

            for (int i = 0; i < number; i++)

            {

                array[i] = rnd.Next(0, number);

            }





            var x = Stopwatch.StartNew();

            QuickSort(array, 0, number - 1);

            x.Stop();

            Console.WriteLine("Quick sort takes "+x.ElapsedTicks+" ticks.");





            for (int i = 0; i < number; i++)

            {

                array[i] = rnd.Next(0, number);

            }

            x = Stopwatch.StartNew();

            ParallelSort(number);

            x.Stop();

            Console.WriteLine("Parallel sort takes " + x.ElapsedTicks + " ticks.");





            Console.ReadKey();

        }

    }

}

نقل قول:

---

نوشته شده توسط erfan_urchin

اگه منظورت مرتب سازی آرایه هستش میتونی از کد زیر هم استفاده بکنیا این همه کد نویسی لازم نیست

Array.Sort(arrayname);

البته اگه منظورتو درست فهمیده باشم و میخوای آرایه هایی که توشون عدد هستن رو مرتب کنی

---

دوست عزیز منظورم الگوریتمش بود.

نقل قول:

---

نوشته شده توسط Arcsinos

میتونی مثل merge sort نصف آرایتو با یه نخ نصف دیگشو با یه نخ دیگه به روش Quick sort مرتب کنی و از تابع merge استفاده کنی تا نتایج تو تا نخ رو با هم ادغام کنی. اگه میخوای درجه ی parallelism رو بالاتر ببری میتونی با تعداد بیشتری نخ این کار رو انجام بدی. نخ هات رو هم پارامتر دار بساز که بتونی رنج قسمتی رو که اون نخ قراره سورت کنه رو مشخص کنی. برای مساله ی concurrency هم میتونی یا قفل بذاری (که سرعت زیاد بالا نمیره و حتی پایین تر هم ممکنه بیاد) و میتونی آرایه رو کلا بشکونی که این روش بهتره.

---

مرسی-میشه سمپل بزاری یا بیشتر توضیح بدی

نقل قول:

---

نوشته شده توسط Reza,M

مرسی-میشه سمپل بزاری یا بیشتر توضیح بدی

---

برادر پست قبلی رو ویرایش کردم و یه کد به دو تا نخ قرار دادم. اگه سوالی داشتی بپرس.
در ضمن کدی هم که خودت گذاشتی باگ داشت که توی کدی که گذاشتم اون باگ هم برطرف شده. وقتی که lb بزرگتر از rb شد باید break بشه که این اتفاق صورت نمی گرفت.

چرا به namespace
using System.Threading.Tasks
خطا میگیره؟؟