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

واضح آرشیو وب فارسی:سایت ریسک: aaaammmm8717-11-2008, 06:37 PMسلام دوستان اگه هر کدومتون الگوریتم های مرتب سازی به روش های حبابی QUIK SORT و بلده بگه و یه برنامه هم در این دو مورد بنویسید .:10: مرتب سازی کویک سرت رو حتما توضیح بدید ! فاطـمه18-11-2008, 07:44 AMدوست من به اینجا یه سر بزن ببین به دردت می خوره !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!!:20: فاطـمه18-11-2008, 07:49 AMاینم الگوریتم خوکشل quicksort به زبان جاوا: کد: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! --------------------------------------------------------------------------------------- تحلیل الگوریتم: بهترین حالت برای الگوریتم quicksort زمانی است که در هر مرحله از تقسیم لیست به دو بخش , دو بخش با اندازه مساوی تولید بشن.در این حالت برای مرتب کردن n عنصر , زمان اجرا برابر: کد: O(n log(n)) به علت اینکه عمق بازگشتی برابر log(n) است و توی هر مرحله با n تا عنصر سروکار داریم.توی شکل قسمت a رو ببینید(یادتون باشه که فرض کردیم یه حالت خاص رخ بده که توی هر مرحله بازگشتی اندازه لیست هایی که تشکیل میشن برابر باشه) http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quickcpx.gif بدترین زمان اجرای این الگوریتم وقتی اتفاق میفته که در هر مرحله بازگشتی یک تکه نامتقارن تولید بشه , یعنی اینکه یه بخش فقط شامل یه عنصر باشه و بخش دیگه شامل بقیه عناصر باشه(شکل بالا قسمت c).که توی این وضعیت عمق بازگشتی n-1 میشه و زمان اجرای الگوریتم برابر: کد: O(n^2) بطور معمول ما انتظار داریم قسمت بندی بصورت ی باشه که توی (شکل بالا b )نمایش داده شده. توی quicksort انتخاب pivot موفقیت عمل قسمت بندی رو تضمین میکنه. فرض کنید که اولین عنصر لیست به عنوان pivot انتخاب بشه.این مسیله میتونه ما رو به سمت بدترین حالت برای الگوریتم سوق بده در صورتیکه لیست از همون ابتدا نسبتاً مرتب باشه (یا بطور معکوس مرتب باشه), این کار باعث میشه که تقریبا تمام عناصر یا در smaller than pivot قرار بگیرن یا در larger than pivot که این عمل همونطوری که بحث شد زمان اجرا رو بالا میبره. یک روش متداول که برای انتخاب pivot بکار گرفته میشه , روش median-of-three یا "میانگین سه" هست. توی این روش میانگین عنصر اول ,عنصر میانی و عنصر آخر هر لیست بعنوان pivot در اون لیست انتخاب میشه که معمولا به عنصر وسط لیست نزدیکتره.و باعث میشه پیچیدگی زمانی الگوریتم کم بشه. یه مشکل دیگه که توی الگوریتم های بازگشتی باهاش سروکار داریم پیچیدگی فضا برای پشته فراخوانی هاست.بطوریکه هر چی عمق بازگشتی بیشتر باشه , پشته بزگتره.یه راه حل برای این مسیله اینه که بجای اینکه در هر مرحله همیشه لیست سمت چپ رو انتخاب کنیم , اول لیست کوچیکتر رو مرتب میکنیم .این عمل از عمق بازگشتی و سربار ناشی از بازگشتی میکاهد. --------------------------------------------------------------------------------------------------------------------------- البته یه توضیح اونم اینکه اینا با یه سرچ کوچولو به دست اومده و کاملا کپی هستنhttp://www.forum.p30world.com/images/New-smile/N_aggressive%20(26).gif فاطـمه18-11-2008, 07:52 AMو این یکی هم که دیگه خود vb هست !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! و البته تو این سایت این الگوریتم به زبانهای مختلف برنامه نویسی وجود داره: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! از اونجایی که کد یه مقدار بهم ریخت فکر کنم به سایت مراجعه کنید بهتر باشه... اینم فارسیش !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! اینم جالب بود !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! و البته این یکی از هم جالب تر !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! سایت ما را در گوگل محبوب کنید با کلیک روی دکمه ای که در سمت چپ این منو با عنوان +1 قرار داده شده شما به این سایت مهر تأیید میزنید و به دوستانتان در صفحه جستجوی گوگل دیدن این سایت را پیشنهاد میکنید که این امر خود باعث افزایش رتبه سایت در گوگل میشود

این صفحه را در گوگل محبوب کنید

[ارسال شده از: سایت ریسک]

[مشاهده در: www.ri3k.eu]

[تعداد بازديد از اين مطلب: 1340]