راهنماییی در مورد الگوریتم های مرتب سازی به روش حبابی و quik sort ؟؟؟

[aaaammmm87]

سلام
دوستان اگه هر کدومتون الگوریتم های مرتب سازی به روش های حبابی QUIK SORT و بلده بگه و یه برنامه هم در این دو مورد بنویسید . مرتب سازی کویک سرت رو حتما توضیح بدید !

[فاطـمه]

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

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

[فاطـمه]

اینم الگوریتم خوکشل quicksort به زبان جاوا:


کد:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

---------------------------------------------------------------------------------------
تحلیل الگوریتم:
بهترین حالت برای الگوریتم quicksort زمانی است که در هر مرحله از تقسیم لیست به دو بخش , دو بخش با اندازه مساوی تولید بشن.در این حالت برای مرتب کردن n عنصر , زمان اجرا برابر:

کد:
O(n log(n))
به علت اینکه عمق بازگشتی برابر log(n) است و توی هر مرحله با n تا عنصر سروکار داریم.توی شکل قسمت a رو ببینید(یادتون باشه که فرض کردیم یه حالت خاص رخ بده که توی هر مرحله بازگشتی اندازه لیست هایی که تشکیل میشن برابر باشه)


بدترین زمان اجرای این الگوریتم وقتی اتفاق میفته که در هر مرحله بازگشتی یک تکه نامتقارن تولید بشه , یعنی اینکه یه بخش فقط شامل یه عنصر باشه و بخش دیگه شامل بقیه عناصر باشه(شکل بالا قسمت c).که توی این وضعیت عمق بازگشتی n-1 میشه و زمان اجرای الگوریتم برابر:

کد:
O(n^2)
بطور معمول ما انتظار داریم قسمت بندی بصورت ی باشه که توی (شکل بالا b )نمایش داده شده.


توی quicksort انتخاب pivot موفقیت عمل قسمت بندی رو تضمین میکنه.
فرض کنید که اولین عنصر لیست به عنوان pivot انتخاب بشه.این مسیله میتونه ما رو به سمت بدترین حالت برای الگوریتم سوق بده در صورتیکه لیست از همون ابتدا نسبتاً مرتب باشه (یا بطور معکوس مرتب باشه), این کار باعث میشه که تقریبا تمام عناصر یا در smaller than pivot قرار بگیرن یا در larger than pivot که این عمل همونطوری که بحث شد زمان اجرا رو بالا میبره.
یک روش متداول که برای انتخاب pivot بکار گرفته میشه , روش median-of-three یا "میانگین سه" هست. توی این روش میانگین عنصر اول ,عنصر میانی و عنصر آخر هر لیست بعنوان pivot در اون لیست انتخاب میشه که معمولا به عنصر وسط لیست نزدیکتره.و باعث میشه پیچیدگی زمانی الگوریتم کم بشه.

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

---------------------------------------------------------------------------------------------------------------------------
البته یه توضیح اونم اینکه اینا با یه سرچ کوچولو به دست اومده و کاملا کپی هستن

[فاطـمه]

و این یکی هم که دیگه خود vb هست

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

و البته تو این سایت این الگوریتم به زبانهای مختلف برنامه نویسی وجود داره:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

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

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

اینم جالب بود

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

و البته این یکی از هم جالب تر

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید