nefrat
شنبه 15 آبان 1389, 18:45 عصر
الگوریتم های مرتب سازی آرایه ها
یکی از مباحث اساسی دروس ساختمان داده ها و اصول طراحی الگوریتم ، یافتن الگوریتم هایی برای مرتب سازی اعدادی بهم ریخته ای است که در یک آرایه پشت سر هم قرار گرفته اند. تا کنون الگوریتم های مختلفی برای اینکار ایجاد شده است که در این مقاله با چند تا از این الگوریتم ها آشنا میشوید. همچنین مرتبه پیچیدگی هر الگوریتم (میزان زمانی که از CPU برای اجرای هر الگوریتم می گیرد) را ذکر خواهیم کرد.
الگوریتم مرتب سازی انتخابی (Selection Sort): در این روش، برنامه کوچکترین مقدار را یافته و آنرا در اولین خانه ی آرایه قرار می دهد. حال که کوچکترین عضو یافت شده است، برنامه به سراغ یافتن دومین عنصر کوچک در میان اعداد باقی مانده که از 2 تا n هستند می رود و دومین عدد کوچک را در خانه دوم قرار میدهد. حال به سراغ سومین عدد کوچک می رود و این رویه را تا یافتن آخر عدد و قرار دادن آن در جای خودش تکرار میکند. با توجه به اینکه برنامه باید n عدد را n بار با هم مقایسه کند مرتبه ی پیچیدگی این الگوریتم O(n^2) است.
مرتب سازی حبابی (Bubble Sort): در این روش هر عنصر با عنصر بعدی اش مقایسه میشود. در صورتی که عنصر دومی کوچکتر از عنصر اولی باشد، جای دو عنصر با هم عوض میشود. برنامه به کارش ادامه میدهد و عناصر دوم و سوم را با هم مقایسه میکند و این کار را تا اخر آرایه ادامه میدهد. دوباره الگوریتم ، پویش را از اول آرایه شروع میکند و مراحل قبل را تکرار میکند و این مراحل آنقدر تکرار میشوند تا آرایه کاملا مرتب شده باشد. مرتبه ی پیچیدگی این الگوریتم O(n^2) است.
مرتب سازی درجی (Insertion Sort): در این روش عنصر اول و دوم با هم مقایسه شده و در صورت نیاز مرتب میشوند و سپس سومین عنصر با عناصر اول و دوم مقایسه میشود. در صورتی که عنصر سوم از اولی کوچکتر باشد به جای اولین عنصر می نشیند و عناصر قبلی به سمت راست هل داده میشوند. اگر عنصر سوم از اولی بزرگتر و از دومی کوچکتر باشد، بین آنها درج میشود و عنصر دوم به بعد یکی به سمت راست هل داده میشود. (پس در این روش همیشه عناصر ِ قبل از عنصری که میخواهیم مرتبش کنیم، مرتب هشتند.) این روال برای بقیه عناصر نیز اجرا میشود و هر عنصر در جای خودش قرار می گیرد تا تمام عناصر مرتب شوند. مرتبه ی پیچیدگی این الگوریتم O(n^2) است.
مرتب سازی سریع(Quick Sort) : در این الگوریتم یک عنصر را بعنوان محور (pilot) مرتب سازی انتخاب میکنیم. و تمام عناصر کوچکتر از آن را به سمت چپ آن برده و عناصر بزرگتر را به سمت راست اش می‌بریم. حالا بخش چپ خودش یک بخش جدید است که با الگوریتمی که گفتیم آنرا مرتب میکنیم و سمت راست را نیز همینطور. یعنی در سمت چپی ها دوباره یک عنصر را بعنوان pilot در نظر میگیریم و عناصر کوچکتر از pilot را به سمت چپ آن و عناصر بزرگتر از pilot این قسمت را ، به سمت راست pilot می بریم. دوباره الگوریتم را روی یک چهارم های به وجود آمده اجرا میکنیم و اینکار را آنقدر ادامه میدهیم تا کل آرایه مرتب شود. مرتبه پیچیدگی این الگوریتم در بدترین حالت O(n^2) است. اما در حال نرمال O(n log n) است که کمترین مرتبه پیچیدگی برای مرتب سازی اعداد به حساب می آید.
مرتب سازی ادغام (Merge Sort): این الگوریتم به روش بازگشتی (Recursive) عمل میکند و آرایه را به چند آرایه ی دو عنصری تقسیم میکند و آنها را مرتب میکند. سپس آرایه های کوچک را دوبه‌دو با هم ادغام میکند تا آرایه های مرتب 4 عنصری ایجاد شوند و بعد آرایه های 8 عنصری و به همین ترتیب پیش می رود تا آرایه اصلی بصورت مرتب شده ظاهر شود. مرتبه پیچیدگی این الگوریتم O(n log n) است.
مرتب سازی هرمی (Heap Sort): در این روش، برنامه از کل آرایه ی داده شده یک درخت MaxHeap می سازد. (درخت مکس هیپ درختی دودویی و کامل است که مقدار ذخیره شده در هر گره ، بزرگتر و یا مساوی مقدار ذخیره شده در گره فرزندانش است) سپس مقدار ماگزیمم را از درخت حذف میکند و آنرا در انتهای آرایه میگذارد و دوباره از بقیه اعداد یک درخت maxHeap میسازد و باز روش مذکور را روی آن نیز اعمال میکند تا دومین عدد بزرگ یافت شود. در این روش آرایه از آخر به اول مرتب میشود. مرتبه پیچیدگی این الگوریتم O(n log n) است.
در تصویر زیر میتوانید مقایسه ای بین سرعت سه الگوریتم که مرتبه پیچیدگی شان n log n است مشاهده کنید.
http://uploadpress.wordpress.com/files/2009/12/sort-algorithms.jpg
روش هایی وجود دارند که حداقل مرتبه ی پیچیدگی هر الگوریتم را با روابطی اثبات میکنند. بطور مثال برای الگوریتم های مرتب سازی ، میزان O(n Log n) حداقل است و کمتر از این میزان ممکن نیست و همانطور که میدانیم الگوریتم های ادغام و هرمی و سریع هر سه با همین میزان پیچیدگی مرتب سازی را انجام میدهند. بنابراین الگوریتمی نمیتوان نوشت که سریعتر از این حالت عمل کند و الگوریتم های مینیمم پیچیدگی در این زمینه ،قبلا کشف و ایجاد شده اند . اما مواردی هستند مانند ضرب دو ماتریس n در n که مرتبه ی پیچیدگی شان O(n^3) است و روش های جدیدی مانند روش استراسن آنرا به O(n^2.81) کاهش داده است. طبق روشهای اثبات شده امکان کمتر شدن این میزان وجود دارد. اما هنوز الگوریتمی که هزینه ی پیچیدگی کمتری از الگوریتم استراسن داشته باشد کشف نشده است. بنابراین هنوز شما میتوانید وقت خود را روی کاهش مرتبه ی پیچیدگی این الگوریتم و یافتن الگوریتم بهینه تر بگذارید.
یکی از مباحث اساسی دروس ساختمان داده ها و اصول طراحی الگوریتم ، یافتن الگوریتم هایی برای مرتب سازی اعدادی بهم ریخته ای است که در یک آرایه پشت سر هم قرار گرفته اند. تا کنون الگوریتم های مختلفی برای اینکار ایجاد شده است که در این مقاله با چند تا از این الگوریتم ها آشنا میشوید. همچنین مرتبه پیچیدگی هر الگوریتم (میزان زمانی که از CPU برای اجرای هر الگوریتم می گیرد) را ذکر خواهیم کرد.
الگوریتم مرتب سازی انتخابی (Selection Sort): در این روش، برنامه کوچکترین مقدار را یافته و آنرا در اولین خانه ی آرایه قرار می دهد. حال که کوچکترین عضو یافت شده است، برنامه به سراغ یافتن دومین عنصر کوچک در میان اعداد باقی مانده که از 2 تا n هستند می رود و دومین عدد کوچک را در خانه دوم قرار میدهد. حال به سراغ سومین عدد کوچک می رود و این رویه را تا یافتن آخر عدد و قرار دادن آن در جای خودش تکرار میکند. با توجه به اینکه برنامه باید n عدد را n بار با هم مقایسه کند مرتبه ی پیچیدگی این الگوریتم O(n^2) است.
مرتب سازی حبابی (Bubble Sort): در این روش هر عنصر با عنصر بعدی اش مقایسه میشود. در صورتی که عنصر دومی کوچکتر از عنصر اولی باشد، جای دو عنصر با هم عوض میشود. برنامه به کارش ادامه میدهد و عناصر دوم و سوم را با هم مقایسه میکند و این کار را تا اخر آرایه ادامه میدهد. دوباره الگوریتم ، پویش را از اول آرایه شروع میکند و مراحل قبل را تکرار میکند و این مراحل آنقدر تکرار میشوند تا آرایه کاملا مرتب شده باشد. مرتبه ی پیچیدگی این الگوریتم O(n^2) است.
مرتب سازی درجی (Insertion Sort): در این روش عنصر اول و دوم با هم مقایسه شده و در صورت نیاز مرتب میشوند و سپس سومین عنصر با عناصر اول و دوم مقایسه میشود. در صورتی که عنصر سوم از اولی کوچکتر باشد به جای اولین عنصر می نشیند و عناصر قبلی به سمت راست هل داده میشوند. اگر عنصر سوم از اولی بزرگتر و از دومی کوچکتر باشد، بین آنها درج میشود و عنصر دوم به بعد یکی به سمت راست هل داده میشود. (پس در این روش همیشه عناصر ِ قبل از عنصری که میخواهیم مرتبش کنیم، مرتب هشتند.) این روال برای بقیه عناصر نیز اجرا میشود و هر عنصر در جای خودش قرار می گیرد تا تمام عناصر مرتب شوند. مرتبه ی پیچیدگی این الگوریتم O(n^2) است.
مرتب سازی سریع(Quick Sort) : در این الگوریتم یک عنصر را بعنوان محور (pilot) مرتب سازی انتخاب میکنیم. و تمام عناصر کوچکتر از آن را به سمت چپ آن برده و عناصر بزرگتر را به سمت راست اش می‌بریم. حالا بخش چپ خودش یک بخش جدید است که با الگوریتمی که گفتیم آنرا مرتب میکنیم و سمت راست را نیز همینطور. یعنی در سمت چپی ها دوباره یک عنصر را بعنوان pilot در نظر میگیریم و عناصر کوچکتر از pilot را به سمت چپ آن و عناصر بزرگتر از pilot این قسمت را ، به سمت راست pilot می بریم. دوباره الگوریتم را روی یک چهارم های به وجود آمده اجرا میکنیم و اینکار را آنقدر ادامه میدهیم تا کل آرایه مرتب شود. مرتبه پیچیدگی این الگوریتم در بدترین حالت O(n^2) است. اما در حال نرمال O(n log n) است که کمترین مرتبه پیچیدگی برای مرتب سازی اعداد به حساب می آید.
مرتب سازی ادغام (Merge Sort): این الگوریتم به روش بازگشتی (Recursive) عمل میکند و آرایه را به چند آرایه ی دو عنصری تقسیم میکند و آنها را مرتب میکند. سپس آرایه های کوچک را دوبه‌دو با هم ادغام میکند تا آرایه های مرتب 4 عنصری ایجاد شوند و بعد آرایه های 8 عنصری و به همین ترتیب پیش می رود تا آرایه اصلی بصورت مرتب شده ظاهر شود. مرتبه پیچیدگی این الگوریتم O(n log n) است.
مرتب سازی هرمی (Heap Sort): در این روش، برنامه از کل آرایه ی داده شده یک درخت MaxHeap می سازد. (درخت مکس هیپ درختی دودویی و کامل است که مقدار ذخیره شده در هر گره ، بزرگتر و یا مساوی مقدار ذخیره شده در گره فرزندانش است) سپس مقدار ماگزیمم را از درخت حذف میکند و آنرا در انتهای آرایه میگذارد و دوباره از بقیه اعداد یک درخت maxHeap میسازد و باز روش مذکور را روی آن نیز اعمال میکند تا دومین عدد بزرگ یافت شود. در این روش آرایه از آخر به اول مرتب میشود. مرتبه پیچیدگی این الگوریتم O(n log n) است.
در تصویر زیر میتوانید مقایسه ای بین سرعت سه الگوریتم که مرتبه پیچیدگی شان n log n است مشاهده کنید.
http://uploadpress.wordpress.com/files/2009/12/sort-algorithms.jpg
روش هایی وجود دارند که حداقل مرتبه ی پیچیدگی هر الگوریتم را با روابطی اثبات میکنند. بطور مثال برای الگوریتم های مرتب سازی ، میزان O(n Log n) حداقل است و کمتر از این میزان ممکن نیست و همانطور که میدانیم الگوریتم های ادغام و هرمی و سریع هر سه با همین میزان پیچیدگی مرتب سازی را انجام میدهند. بنابراین الگوریتمی نمیتوان نوشت که سریعتر از این حالت عمل کند و الگوریتم های مینیمم پیچیدگی در این زمینه ،قبلا کشف و ایجاد شده اند . اما مواردی هستند مانند ضرب دو ماتریس n در n که مرتبه ی پیچیدگی شان O(n^3) است و روش های جدیدی مانند روش استراسن آنرا به O(n^2.81) کاهش داده است. طبق روشهای اثبات شده امکان کمتر شدن این میزان وجود دارد. اما هنوز الگوریتمی که هزینه ی پیچیدگی کمتری از الگوریتم استراسن داشته باشد کشف نشده است. بنابراین هنوز شما میتوانید وقت خود را روی کاهش مرتبه ی پیچیدگی این الگوریتم و یافتن الگوریتم بهینه تر بگذارید.