تماس با ما

هرگونه پیشنهاد و انتقاد خود را با ما در میان بگذارید

یکی از روش های جالب مرتب سازی روش مرتب سازی سریعه که بر خلاف اسمش در بدترین حالت پیچیدگی اون از مرتبه O(n2) میشه که از مرتب سازی ادغامی کند تر میشه اما دلیل اینکه این اسم رو براش گذاشتن به خاطر پیچیدگی اون در حالت میانگینه.

در حالت میانگین میشه گفت که این الگوریتم واقعا سریعه و در خیلی از برنامه ها از این روش برای مرتب سازی استفاده میشه.

اول از همه باید بدونید که این الگوریتم در دسته الگوریتم های تقسیم و حل قرار داره پس میشه پیش بینی کرد که احتمالا الگوریتم به صورت بازگشتی قابل حله.

حالا روش کار رو توضیح میدم و بعد الگوریتم رو به زبان ++C می نویسم تا مطلب کامل بشه. برای اینکه بهتر بتونید این روش مرتب سازی رو با روش ادغامی مقایسه کنید همون آرایه ای که در مرتب سازی ادغامی به کار بردم رو با این روش مرتب میکنم، پس این آرایه رو در نظر بگیرید:

1 7 4 11 9 2 13 14 3 10

 حالا مرتب سازی به روش سریع رو به این ترتیب انجام میدیم:

  • مرحله اول مثل مرتب سازی ادغامی شامل تقسیم آرایه است اما روش تقسیم با مرتب سازی ادغامی متفاوته، در اینجا یک عضو آرایه رو انتخاب میکنیم و اسم اون رو میگزاریم عنصر محوری (pivot point) و کلیه عناصری که از عنصر محوری کوچکتر هستن رو سمت چپ عنصر محوری قرار میدیم و عناصر بزرگتر رو در سمت راست عنصر محوری قرار میدیم. اسم رویه ای که این کار رو میکنه میگذاریم partition که الگوریتم اون به زبان ++c این شکلی میشه:
    int part(int* ar,int arr_beg,int arr_end)
    {
        int pivot =arr_beg;
        int higher = arr_end;
        int temp;
        while(pivot < higher )
        {
            if(ar[pivot] > ar[pivot+1] )
            {
                temp=ar[pivot+1]; ar[pivot+1]=ar[pivot]; ar[pivot]=temp;
                pivot++;
            }
            else
            {
                temp=ar[pivot+1]; ar[pivot+1]=ar[higher]; ar[higher]=temp;
                higher--;
            }
        }
        return pivot;
    }
    

    در مورد این قطعه کد چیزی که مهمه بدونید اینه که در هر بار اجرای حلقه while عنصری از آرایه که در محل pivot قرار داره با عنصر بعدی (یعنی عنصر pivot+1) مقایسه میشه و اگر از اون بزرگتر باشه با اون جابجا میشه (مسلماً وقتی که این اتفاق بیفته باید خود متغیر pivot هم که شماره عنصر محوری هست باید اصلاح بشه) و اگر بزرگتر نباشه با عنصر انتهای آرایه که با متغیر higher مشخص شده جابجا میشه و برای اینکه دفعه بعد عنصر انتهای آرایه دوباره جابجا نشه متغیر higher یکی کم میشه.
    در نهایت شرط انتهای حلقه اینه که متغیر های pivot و  higher با هم برابر بشن و در این حالت آرایه به دو بخش تقسیم شده که یک بخش از arr_beg شروع و تا عنصر قبل از pivot  ادامه داره و بخش دیگه از عنصر بعد از pivot شروع میشه و تا arr_end ادامه داره.
    یه نکته مهم: دقت کنید که خود آرایه رو با اشاره گر به عنصر ابتدای اون به تابع منتقل کردم تا زمانی که خواستم از این الگوریتم به صورت بازگشتی استفاده کنم هر بار مجبور نشم کل آرایه رو به تابع منتقل کنم.
    حالا اگر خواستیم ارایه خودمون رو با استفاده از این الگوریتم مرتب کنیم تابع رو این شکلی صدا میزنیم:
    int p= part(ar,0,9);

    به این ترتیب آرایه به این شکل در میاد:

     3 1 7 2 9 4 10 11 13 14

    رنگ خونه ای که 10 در اون قرار داره رو زرد کردم تا مشخص باشه که عنصر محوری کدوم عنصره و هر کدام از دو بخش از کجا شروع و تا کجا ادامه دارن، اگر به شکل زیر نگاه کنید به خوبی متوجه میشید که این الگوریتم چطور کار میکنه:
    ادغام دو آرایه مرتب
    مشخصه که زمانی که دو تا خونه نارنجی میشه الگوریتم داره اون دو تا خونه رو مقایسه میکنه و بعد از هر مقایسه یا اون دو تا خونه با هم جابجا میشه و یا عنصر بزرگتر از pivot با خونه ای که اشاره گر higher بهش اشاره میکنه جابجا میشه.

  •  در مرحله بعد هر کدوم از بخشهایی رو که بدست اومده به صورت بازگشتی با همین الگوریتم مرتب میکنیم، اینم از الگوریتم کامل مرتب سازی سریع، با دقت بخونید تا توضیح بدم:
    int main()
    {
        int ar [] = {10,3,14,13,2,9,11,4,7,1};
        quick_sort(ar,0,9);
        for(int i = 0 ; i <= 9 ; i++) cout << " " << ar[i];
        return 0;
    }
    
    void quick_sort(int* raw_array,int arr_beg,int arr_end)
    {
        int pivotpoint= part(raw_array,arr_beg,arr_end);
        if(arr_beg < pivotpoint ) quick_sort(raw_array,arr_beg,pivotpoint-1);
        if(pivotpoint < arr_end) quick_sort(raw_array,pivotpoint+1,arr_end);
    
    }
    int part(int* ar,int arr_beg,int arr_end)
    {
        int pivot =arr_beg;
        int higher = arr_end;
        int temp;
        while(pivot < higher )
        {
            if(ar[pivot] > ar[pivot+1] )
            {
    
                temp=ar[pivot+1]; ar[pivot+1]=ar[pivot]; ar[pivot]=temp;
                pivot++;
            }
            else
            {
                temp=ar[pivot+1]; ar[pivot+1]=ar[higher]; ar[higher]=temp;
                higher--;
            }
        }
        return pivot;
    }
    

    اگر دقت کنید تابع part محل عنصر محوری ( pivot point) رو به عنوان مقدار برگشتی میفرسته، و نکته ای که نباید فراموش کنید اینه که محل عنصر محوری بعد از این مرحله تغییری نمیکنه برای همین در تابع quick_sort بعد از اینکه دو گروه کمتر از عنصر محوری و بیشتر از عنصر محوری، ساخته شد، در بخشی که فراخوانی بازگشتی تابع quick_sort انجام میشه عنصر محوری در هیچکدام از مرتب سازی های بخشهای جدید تشکیل شده  وجود نداره.
پیچیدگی مرتب سازی سریع: 

بر خلاف مرتب سازی ادغامی که پیچیدگی اون همواره ثابت هست در مرتب سازی سریع پیچیدگی الگوریتم به شدت به نحوه قرار گیری اعضای آرایه بستگی داره، اگر ترتیب اعضای آرایه جوری باشه که پس از تقسیم به دو آرایه کوچکتر اعضای دو آرایه تقسیم شده تقریبا برابر باشن پیچیدگی کمتر میشه در حالی که اگر به هر دلیل (مثلا به این دلیل که آرایه از قبل تا حدودی مرتب شده باشه) یکی از بخش ها از بخش دیگه بزرگتر باشه اون وقت پیچیدگی افزایش پیدا میکنه.

اول ببینیم تابع part چه پیچیدگیی داره؟ با توجه به اینکه در هر با تکرار حلقه while یکی از دستورات higher-- یا pivot++ تکرار میشه به وضوح پیداست که حلقه while در این تابع دقیقا به تعداد عناصری که قراره تقسیم بشه تکرار میشه و این تعداد دقیقا برابر میشه با arr_end-arr_beg+1 یعنی داریم:

 T(part(ar,arr_beg,arr_end))=arr_end-arr_beg+1

در بهترین حالت فرض میکنیم که آرایه به دو بخش تقریبا مساوی تقسیم میشه بنابراین میشه گفت که پیچیدگی محاسباتی الگوریتم به این صورت میشه:

B(n)=B(part)+B(n/2-1)+B(n/2-1) => B(n)=O(n.log2n)

اگر در مورد حل معادلات بازگشتی مانند این معادله میخاهید بیشتر بدونید اینجا کلیک کنید.

تا اینجای کار همه چیز خوبه اما میدونیم که پیچیدگی در بهترین حالت اصلا ملاک خوبی برای تشخیص کارایی الگوریتم نیست، بنابراین میریم سراغ بدترین حالت، در این حالت تابع part آرایه رو به دو بخش که یکی شامل 0 عنصر و دیگری شامل n-1 عنصر هست تقسیم میکنه، یادتون نره که اگه آرایه تصادفا کاملا مرتب شده باشه هر بار اجرای تابع part دقیقا همین کار رو میکنه بنابراین پیچیدگی در بدترین حالت به این صورت به دست میاد:

 W(n)=W(part)+W(n-1) => W(n)=O(n2)

پیداست که بد ترین حالت اصلا امیدوار کننده نیست اما باید در نظر بگیرید که بدترین حالت زمانی اتفاق میفته که آرایه کاملا مرتب باشه و احتمال رخ دادن این حالت خیلی کمه و اگر n تا عدد داشته باشیم این احتمال برابر است با:

 P("رخدادن بدترین حالت")=2/n!

مثال برای 10 عدد:P=2/3628800=0.0000000551

محاسبه حالت میانگین اما بر خلاف بدترین حالت و بهترین حالت که به راحتی به دست اومد اصلا ساده نیست، چون در حالت میانگین بسته به میزان مرتب بودن باید پیچیدگی رو حساب کنیم و سپس میانگین رو حساب کنیم.

اما این کار خیلی مشکله چون n عدد رو میشه به n فاکتوریل طریق کنار هم چید و در نتیجه n فاکتوریل حالت داریم که باید پیچیدگی مساله رو در اون حالت ها حساب کنیم و میانگین رو بدست بیاریم که کار عاقلانه ای نیست.

برای اینکه بتونیم پیچیدگی مساله در حالت میانگین رو حساب کنیم باید یه کم از قواعد درس آمار و احتمال رو استفاده کنیم و چونکه من الان این درس رو برای خودم مرور نکردم فعلا بی خیال اثبات میشم و اعلام میکنم که پیچیدگی این الگوریتم در حالت میانگین برابر O(n.log n) میشه. بعدا که درس آمار رو مرور کردم بر میگردم و این مطلب رو کامل میکنم.


اگر دنبال اطلاعات بیشتری در مورد این مطلب هستید لینک های زیر رو دنبال کنید:

جزوه آموزشی دانشگاه صنعتی شریف

ویکی پدیا

الگوریتمستان

بی کارت

 مدیریت کارت های بانکی

دانلود اپلیکیشن بی کارت از بازار:
https://goo.gl/cyNai2

تبلیغات


  تهران هاست
ارائه کننده خدمات میزبانی وب

 


 

مهندس رضا زنگنه

انجام هرگونه تعمیرات PC و لب تاپ در اصفهان

09387652826