الگوریتم مرتب سازی سریع (Quick Sort)

  • شنبه ۱۱ آبان ۱۳۹۸
  • بازدید ۳۵ نفر

quick sort algorithm 7333 تصویر

الگوریتم مرتب سازی سریع (Quick Sort)

الگوریتم مرتب سازی سریع (Quick Sort) مانند الگوریتم Merge Sort، به روش تقسیم و غلبه (Divide and Conquer) عمل می کند. در این الگوریتم یک عنصر به عنوان محور انتخاب می شود و آرایه با توجه به آن عنصر تقسیم می شود. روش انتخاب عنصر محوری در نسخه های مختلف الگوریتم مرتب سازی سریع متفاوت است.

  • همیشه عنصر اول به عنوان عنصر محوری انتخاب می شود.
  • همیشه عنصر آخر به عنوان عنصر محوری انتخاب می شود (در زیر پیاده سازی شده است).
  • یک عنصر تصادفی به عنوان عنصر محوری انتخاب می شود.
  • عنصر میانی به عنوان عنصر محوری انتخاب می شود.

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

quick sort algorithm 7333 2 تصویر

شبه کد مربوط به تابع Quick Sort به صورت بازگشتی:

quick sort algorithm 7333 1 تصویر

الگوریتم پارتشین بندی:

راه های زیادی برای انجام پارتیشن بندی آرایه وجود دارد. منطق کار ساده است، از سمت چپ ترین عنصر شروع می کنیم و به دنبال عناصری که کوچکتر از i (یا برابر با آن) هستند، می گردیم. اگر عنصر کوچکتری پیدا کردیم، آن را با arr[i] جا به جا می کنیم. در غیر این صورت این عنصر را نادیده می گیرم.

شبه کد مربوط به تابع partition:

مراحل پارتشین بندی:

پیاده سازی الگوریتم Quick Sort

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

امتحان کنید

خروجی:

بررسی الگوریتم Quick Sort

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

دو بخش اول مربوط به فراخوانی های بازگشتی و بخش سوم هم مربوط به عملیات پارتیشن بندی است. K تعداد عناصر کوچکتر از عنصر محوری (pivot) است. میزان زمان سپری شده توسط الگوریتم Quick Sort به آرایه ورودی و استراتژی پارتیشن بندی بستگی دارد.

  • پیچدگی زمانی در بدترین حالت برابر است با O(n2).
  • پیچدگی زمانی در بهترین حالت O(nlog n) برای پارتیشن بندی ساده و O(n) برای پارتیشن بندی سه جانبه و کلیدهای برابر.
  • پیچدگی زمانی در حالت متوسط برابر است با O(nlog n).
ثبت نظر
ریفریش کنید!
نظرات کاربران (۰ مورد)

هیچ نظری ثبت نشده است