بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی آنلاین 20 Quera

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسأله‌ی انتخابات

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
مرتب‌سازی سریع - الگوریتمستان
الگوریتمستان
6314.085.00
  »  

       

آشنایی با روش مرتب‌سازی سریع، همراه با قطعه کدهای نمونه به زبان برنامه‌نویسی ++C

http://www.aachp.ir آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «مرتب سازی سریع» دی ماه 1385 از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان) منتشر شده بود.


آنچه در این نوشته می‌خوانید:

روش مرتب‌سازی سریع (Quick Sort) یکی از الگوریتم‌های مشهور مرتب‌سازی داده‌ها است. این الگوریتم طی مراحل بازگشتی زیر یک روش تقسیم و غلبه برای مرتب کردن داده‌ها ارائه می‌نماید:

    1- انتخاب عنصر محوری: یکی از عناصر آرایه به عنوان عنصر محوری (pivot) - به عنوان مثال عنصر اول - انتخاب می‌شود.

    2- تقسیم آرایه: چینش عناصر آرایه به قسمی تغییر داده می‌شود که تمامی عناصر کوچکتر یا مساوی محور در سمت چپ آن و تمامی عناصر بزرگتر در سمت راست آن قرار بگیرند. این دو قسمت زیر آرایه‌های چپ و راست نامیده می‌شوند.

    3- مرتب‌سازی بازگشتی: زیرآرایه‌های چپ و راست به روش مرتب‌سازی سریع مرتب می‌شوند.

      

پیاده‌سازی تقسیم آرایه

  [بازگشت به فهرست]

با استفاده از تابع زیر - با فرض انتخاب عنصر اول به عنوان محور - می‌توان مرحله‌ی تقسیم آرایه را پیاده‌سازی کرد:

      

int partition(int arr[], int low, int high){
  int left = low + 1, right = high, temp, pivot = arr[low];
  while(left <= right){
    while(arr[left] <= pivot && left <= right)
      left++;
    while(arr[right] > pivot && left <= right)
      right--;
    if(left < right){
      temp = arr[left];
10       arr[left] = arr[right];
11       arr[right] = temp;
12     }
13   }
14   arr[low] = arr[right];
15   arr[right] = pivot;
16   return right;
17 }

      

    تابع partition آرایه‌ی arr و اندیس بازه‌ی مورد نظر از آرایه جهت مرتب‌سازی را با low و high دریافت می‌کند. در متغیر pivot مقدار عنصر ابتدای بازه به عنوان عنصر محوری ذخیره می‌شود. همینطور در متغیر left اندیس عنصر دوم - اولین عنصر غیر محور بازه - و در متغیر right اندیس عنصر آخر ذخیره می‌شوند.

    حلقه‌ی بیرونی تا زمانی که اندیس left کوچکتر یا مساوی اندیس right است تکرار خواهد شد. در این حلقه جابجایی‌های لازم برای قرار گرفتن عنصر محوری در محل صحیح خود صورت می‌گیرد. حلقه‌ی درونی اول مقدار اندیس left را تا جایی که مقدار آن کمتر یا مساوی right بوده و مقدار عنصر متناظر آن در آرایه کمتر یا مساوی محور باشد افزایش می‌دهد. به همین ترتیب حلقه‌ی بعدی مقدار اندیس right را تا جایی که مقدار آن بیشتر یا مساوی left بوده و مقدار عنصر متناظر آن در آرایه بیشتر از عنصر محوری باشد کاهش می‌دهد. در انتها اگر left کوچکتر از right باشد مقدار متناظر آنها در آرایه جابجا می‌شود. چرا که بر اساس عملکرد دو حلقه‌ی درونی، اندیس left محل اولین عنصر بزرگتر از محور از ابتدای بازه و اندیس right محل اولین عنصر کوچکتر از محور از انتهای بازه را مشخص می‌کند. اگر این شرط برقرار نباشد به معنی آن است که تمامی عناصر بزرگتر از محور در سمت راست و تمامی عناصر کوچکتر از محور در سمت چپ بازه جمع شده‌اند (چرا؟). در پایان مقدار محور با مقدار حد فاصل دو زیرآرایه جابجا شده و اندیس محل محور به عنوان محل تقسیم دو زیرآرایه از تابع بازگشت داده می‌شود.

    این تابع را روی یک آرایه‌ی هفت عنصری از اعداد صحیح بررسی می‌کنیم:

      

3 0 6 1 7 2 5

      

    تابع به صورت (partition(arr, 0, 6 فراخوانی می‌شود:

      

3 0 6 1 7 2 5:  pivot = 3, left = 1, right = 6

      

    شرط left < right برقرار است. پس وارد حلقه شده و حلقه‌های درونی اجرا می‌شوند. پس از اجرای حلقه‌ها مقدار left و right به اندیس دو و پنج تغییر می‌کنند و مقادیر متناظر آنها جابجا می‌شوند:

      

3 0 2 1 7 6 5:  pivot = 3, left = 2, right = 5

      

    شرط left < right همچنان برقرار است. حلقه‌های درونی مقدار left و right را به چهار و سه تغییر می‌دهند. اما چون left < right نیست جابجایی انجام نمی‌شود:

      

3 0 2 1 7 6 5:  pivot = 3, left = 4, right = 3

      

    با نادرست بودن شرط left < right از حلقه‌ی بیرونی نیز خارج شده و به دستورات جابجایی نهایی می‌رسیم:

      

1 0 2 3 7 6 5

      

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

      

پیاده‌سازی مرتب‌سازی سریع

  [بازگشت به فهرست]

در مرحله‌ی بعدی از الگوریتم مرتب‌سازی سریع، دو زیرآرایه‌ی چپ و راست به صورت بازگشتی مرتب می‌شوند:

      

void quick_sort(int arr[], int low ,int high){
  if(low < high){
    int pivot = partition(arr, low, high);
    quick_sort(arr, low, pivot - 1);
    quick_sort(arr, pivot + 1, high);
  }
}

  

    تابع quick_sort آرایه و بازه‌ی مورد نظر برای مرتب‌سازی را دریافت کرده، پس از تقسیم آرایه و مشخص شدن محل عنصر محوری، دو زیرآرایه‌ی چپ و راست را با فراخوانی بازگشتی حل می‌کند. توجه داشته باشید که در این تابع pivot اندیس عنصر محوری را در خود ذخیره می‌کند. در تابع partition این متغیر مقدار عنصر محوری را ذخیره می‌کرد.

    در مثال فوق وضعیت آرایه پس از اجرای دستور تقسیم آرایه در هر فراخوانی به صورت زیر خواهد بود:

      

مرتب‌سازی سریع

      

0)  3 0 6 1 7 2 5:  low = 0, high = 6

1)  quick_sort(arr, 0, 6 )    ->    1 0 2 3 7 6 5, pivot = 3

2)  quick_sort(arr, 0, 2 )    ->    0 1 2 3 7 6 5, pivot = 1

3)  quick_sort(arr, 0, 0 )    ->    0 1 2 3 7 6 5

4)  quick_sort(arr, 2, 2 )    ->    0 1 2 3 7 6 5

5)  quick_sort(arr, 4, 6 )    ->    0 1 2 3 5 6 7, pivot = 6

6)  quick_sort(arr, 4, 5 )    ->    0 1 2 3 5 6 7, pivot = 4

7)  quick_sort(arr, 5, 5 )    ->    0 1 2 3 5 6 7

  

    در پایان آرایه مرتب شده است.

      

پیچیده‌گی زمانی مرتب‌سازی سریع

  [بازگشت به فهرست]

در مرتب‌سازی‌های مبتنی بر مقایسه عموما تعداد مقایسه‌ها ملاک بررسی پیچیده‌گی زمانی است. $T(n)$ را تعداد مقایسه‌های لازم برای مرتب کردن آرایه‌ای به طول $n$ با روش مرتب‌سازی سریع در نظر می‌گیریم. تابع partition برای تقسیم‌بندی بازه‌ای به طول $n$ به غیر از عنصر محوری تمامی عناصر را مقایسه می‌کند و به $n - 1$ مقایسه نیاز دارد.

    بهترین حالت قرار گرفتن عنصر محوری زمانی است که این عنصر در وسط بازه قرار بگیرد و آن بازه را به دو بازه با اندازه‌ی تقریبا برابر تقسیم کند. در این حالت هر زیربازه $ T(\frac{n}{2}) $ مقایسه نیاز خواهد داشت و می‌توان نوشت:

      

\[T(n) = 2 T(\frac{n}{2}) + n - 1 \]

      

    با استفاده از قضیه‌ی اصلی یا حل رابطه‌ی بازگشتی مشخص می‌شود که $T(n)$ از مرتبه‌ی اجرای $ \theta (n log n)$ است.

    در بدترین حالت عنصر محوری در یک سوی بازه قرار گرفته و تمامی عناصر دیگر در یک سمت آن جمع می‌شوند. این حالت زمانی اتفاق می‌افتد که بازه از قبل به صورت نزولی یا صعودی مرتب باشد. در نتیجه یک زیربازه از اندازه‌ی صفر و یک زیربازه از اندازه‌ی $n - 1$ تولید خواهد شد:

      

\[T(n) = T(0) + T(n - 1) + n - 1 = T(n - 1) + n - 1 \]

      

    حل این رابطه‌ی بازگشتی نشان از مرتبه‌ی اجرایی $ \theta(n^2)$ در بدترین حالت اجرای الگوریتم دارد.

      

ویژگی‌های مرتب‌سازی سریع

  [بازگشت به فهرست]

1- پیچیده‌گی زمانی اجرای الگوریتم در بهترین حالت $ \theta(n log n)$ و در بدترین حالت $ \theta (n^2)$ است. با استفاده محاسبات ریاضی می‌توان نشان داد در حالت متوسط نیز مرتبه‌ی اجرا $ \theta (n log n)$ است.

    2- این الگوریتم یک مرتب‌سازی درجا است. یعنی میزان حافظه‌ی مصرفی الگوریتم مستقل از طول آرایه است.

    3- زمانی که تعداد عناصر آرایه کم باشد، سرعت اجرای مرتب‌سازی درجی بهتر از مرتب‌سازی سریع است. به همین دلیل طی مراحل بازگشتی مرتب‌سازی سریع، اگر طول بازه عدد کوچکی باشد، معمولا بازه با مرتب‌سازی درجی مرتب می‌شود.

    4- الگوریتم مرتب‌سازی سریع با پیاده‌سازی فوق یک روش ناپایدار است. چنین الگوریتمی لزوما ترتیب عناصر با مقدار یکسان را پس از مرتب‌سازی حفظ نمی‌کند.

    5- انتخاب عنصر محوری بحث مفصلی دارد. اما در کل یک انتخاب آزاد است. می‌توان عنصر اول، عنصر آخر، یا هر عنصر دیگری را به عنوان عنصر محوری انتخاب کرد. حتی لازم نیست از ابتدا تا انتها از یک روش انتخاب استفاده کرد. یکی از روش‌های رایج، انتخاب یک عنصر تصادفی به عنوان عنصر محوری است. اگرچه انتخاب عنصر محوری مناسب باعث بالا رفتن کارایی الگوریتم می‌شود، اما عموما هزینه‌ی لازم برای یافتن چنین محوری بالا بوده و مقرون به صرفه نیست.


این نوشته آخرین بار در تاریخ پنجشنبه، ۱۰ اردیبهشت ماه ۱۳۹۴ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
        ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
        آشنایی با روش مرتب‌سازی ادغامی با قطعه کدهایی به زبان برنامه‌نویسی ++C
        بررسی الگوریتم‌های محاسبه‌ی دنباله‌ی اعداد فیبوناچی و کارایی آنها
        آشنایی با روش مرتب‌سازی هرمی (Heap Sort)
        بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه‌ی آن با روش تقسیم و حل و روش برنامه‌نویسی پویا
        آشنایی با دنباله‌ی عددی کاتالان، کاربردها و روش پیاده‌سازی آن به زبان برنامه‌نویسی ++C
        آشنایی با الگوریتم استراسن برای محاسبه‌‌ی حاصلضرب ماتریس‌ها
        آشنایی با روش مرتب‌سازی درجی، همراه با قطعه کد به زبان برنامه‌نویسی ++C
        بررسی روش‌های بسط لاپلاس، گاوس، فرمول تحویل و ساروس، برای محاسبه‌ی دترمینان ماتریس مربعی و پیچیده‌گی زمانی آنها
        بررسی روش‌های مختلف محاسبه‌ی ضرایب دوجمله‌ای نیوتن یا ترکیب دو عدد با قطعه کد به زبان برنامه‌نویسی ++C
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» محمد

چهارشنبه، ۲۸ مهر ماه ۱۳۹۵، ساعت ۲۱:۲۱
خوبه لایک

» محمد

چهارشنبه، ۲۸ مهر ماه ۱۳۹۵، ساعت ۲۱:۲۰
111009090909

» komeil70

جمعه، ۴ تیر ماه ۱۳۹۵، ساعت ۱۱:۲۰
نسبت به الگوریتم های دیگری که تو سایت عالی بودن این افتضاح بود نسبت به اونا....09

» احمد

سه‌شنبه، ۱۲ خرداد ماه ۱۳۹۴، ساعت ۰۱:۵۶
سلام و عرض ادب و خسته نباشید
یه سوال دارم این سوال در رابطه با یک استاد از دوست بنده سوال پرسیده شده که باید جواب رو ایمیل کنه آیا شما از این سوال سر در میارید راهنمایی کنید
اگه کاری از دست بنده بر بیاد انجام میدم حنی میتونم سایتتون رو در چند سایت گرافیک که دارم تبلیغ کنم البته در قبال کمکی که میکنید:
سوال1
برای جستجوی یک عنصر مثلا یک 50 یک عدد مرتب کنیم از نزولی به سعودی سوال 2
الگوریتم مرتب سازی در دو تمرین اجرا کنید فایل را ایمیل کنید همراه با عکس

» محمد عاشری

چهارشنبه، ۱۰ دی ماه ۱۳۹۳، ساعت ۰۴:۲۷
با سلام و خسته نباشید
امید وارم پیروز و سر بلند باشید01

» nika

دوشنبه، ۱۸ فروردین ماه ۱۳۹۳، ساعت ۱۰:۳۶
سلام. من برنامه ای می خوام با استفاده از الگوریتم تقسیم و غلبه  مرتب سازی سریع ،برای بدست اوردن عضو ی که بیش از نیمی از ارایه رو گرفته است.
اگه میشه خیلی زود جواب بدین ممنون میشم.07

» علیرضا

پنجشنبه، ۱ اسفند ماه ۱۳۹۲، ساعت ۲۳:۲۳
کارم راه افتاد
دست شما درد نکنه!!!!!!!!!!!!!!!!!!!!!!!!!!!04

» الی

چهارشنبه، ۱۸ دی ماه ۱۳۹۲، ساعت ۱۲:۱۹
سلام .خسته نباشید .ببخشید من یه پروزه دارم به هرکی گفتم نتونسته واسم انجامش بده اگه شما میتونید خبرم کنید .با استفاده از الگوریتم زنتیک برای پیاده سازی الگوریتم جست و جوی دودویی .با تشکر

» Mani Amoozadeh

شنبه، ۱۴ دی ماه ۱۳۹۲، ساعت ۱۰:۳۹
به طور تصادفی به این سایت برخوردم. خوب و روون می نویسی و مهم تر اینکه مفاهیم رو درست منتقل می کنی.

keep up the good works :)0

» D_felfelak

شنبه، ۱۵ تیر ماه ۱۳۹۲، ساعت ۱۳:۱۰
کد رو عينا" در ويژوال زدم فکر ميکنم که الگوريتم پارتيشن مشکل داره چون مثلا" اگر به تابع آرايه زير رو بديم :
45 37 3 102 68 12 10 38 37 100
جواب زير رو ميده:
102 100 68 38 45 37 37 12 3 10
که اشتباه هست!!



شنبه، ۱۵ تیر ماه ۱۳۹۲، ساعت ۱۹:۳۰
مسعود:
با تشکر از تذکرتون. اصلاح شد.

» محسن

سه‌شنبه، ۱۲ دی ماه ۱۳۹۱، ساعت ۲۱:۰۸
دوست عزیز واقعا از توضیح بسیار زیبای شما تشکر میکنم خیلی به من در فهم  این مرتب سازی کمک کرد امیدوارم همواره موفق باشید

» مجتبی

سه‌شنبه، ۳۰ آبان ماه ۱۳۹۱، ساعت ۰۸:۴۷
با سلام. چگونه میتوان از الگوریتم سریع برای حل سوالات زیر استفاده کرد 1-
یافتن میانه2- یافتن عنصر kام عنصر مینیمم

» ف_ک

سه‌شنبه، ۲۳ آبان ماه ۱۳۹۱، ساعت ۰۹:۴۹
با تشکر از راهنمایی تون.
اگه میشه بگید چرا اسم این الگوریتم را مرتب سازی سریع نامیده اند.
مرسی.


پنجشنبه، ۲۵ آبان ماه ۱۳۹۱، ساعت ۱۴:۰۸
مسعود:
اصولا هر روش الگوریتمی بر اساس نوع عملکرد خودش یا منبعی که از اون الهام گرفته شده نامگذاری می‌شه. مثلا مرتب‌سازی ادغامی به خاطر بحث ادغام، الگوریتم ژنتیک به خاطر الگوبرداری از بحث تکامل ژنتیکی، جستجوی دودویی به خاطر تقسیم شدن بازه به دو قسمت در هر مرحله ...
احتمال زیاد

» هیوا

جمعه، ۱ اردیبهشت ماه ۱۳۹۱، ساعت ۰۲:۱۶
میشه لطفا این الگوریتم رو بصورت غیر بازگشتی پاده کنید و تغییراتش رو شرح بدید؟



جمعه، ۱ اردیبهشت ماه ۱۳۹۱، ساعت ۱۰:۴۶
مسعود:
اگر امکان و فرصتش باشه حتما در این مورد مطلبی می‌نویسم.
ممنون از توجهتون.

» محمد

پنجشنبه، ۱۵ دی ماه ۱۳۹۰، ساعت ۲۱:۵۶
خدا پدر و مادر اون آدمی رو بیامرزه که ویکیپدیا رو راه انداخت........ همه این مطالب اونجا هست........برو باباجون جمش کن14141414


پنجشنبه، ۱۵ دی ماه ۱۳۹۰، ساعت ۲۲:۵۸
مسعود:
درست می‌فرمایید محمد جان. همه‌ی این توضیحات ویکی‌پدیا هم هست. نه تنها اونجا که چند تا منبع اصلی دیگه هم خیلی کاملترش هست. برای تکمیل خود ویکی‌پدیا هم از اونها استفاده شده. در هر حال منم از همین منابع این روش رو یاد گرفتم.
ولی اینطور نیست که متن اونا رو اینجا کپی کرده باشم. اینا همه آموخته‌های خودم به قلم خودم هستن. سعی کردم طوری بیان کنم که اکثر ترجمه‌های این منابع در بیانشون مشکل دارن. 01

» نجمه

شنبه، ۳ دی ماه ۱۳۹۰، ساعت ۱۴:۳۴
خیلی ممنون عالی بودتوضیحات

» دانشجو

شنبه، ۲۶ آذر ماه ۱۳۹۰، ساعت ۱۰:۴۳
باسلام وخسته نباشید..مطالبتون درست چیزای بوذ که من دنبالشون بودم...و بسیار ممنونم...ولی سوالی که مطرح میشه اینه که شما چجوری پیچیدگی زمانی اونارو حساب میکنید..من پیچیدگی زمانی مرتب سازی درجی رو حساب کردم..ولی نحوه ی محاسبهbig tetaرو نمیدونم.فقطbig oرو میدونم.
باتشکر

» سید

جمعه، ۴ آذر ماه ۱۳۹۰، ساعت ۱۴:۵۶
ممنون از سایت جالبتون



بهتر است نمونه های قابل اجرا ارائه دهید


جمعه، ۴ آذر ماه ۱۳۹۰، ساعت ۱۶:۳۲
مسعود:
منم از شما سپاسگزارم سید جان
منظورتون از نمونه‌های قابل اجرا چیه؟

» مریم

چهارشنبه، ۲۵ آبان ماه ۱۳۹۰، ساعت ۲۰:۲۹
میشه مطلب در مورد بدست آوردن اوی بزرگ و تتا روی سایتتون بذلرید

» سهیلا

دوشنبه، ۲۵ مهر ماه ۱۳۹۰، ساعت ۲۰:۱۰
یه کم واضحتربنویسسسسسسسسسسسسس0702