نمایش نتایج 1 تا 8 از 8

نام تاپیک: Quick Sort

  1. #1

    Quick Sort

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

    ++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++

    الگوریتم quicksort یکی از سریع ترین و ساده ترین الگوریتم های مرتب سازی است.این الگوریتم بصورت بازگشتی و با خط مشی تقسیم و حل(divide-and-conquer) کار میکنه.

    ابتدا ,لیستی که قراره مرتب بشه (مثلا لیست a) به دو قسمت تقسیم میشه بطوریکه تمام عناصر قسمت اول(b) کوچکتر یا مساوی تمام عناصر قسمت دوم(c) باشند[divide].(بعدا توضیح میدم که چطور اینکار صورت میگیره).این دو قسمت بطور جداگانه با همین روش مرتب میشن (conquer). اگه دقت کنید میبینید که حاصل ترکیب این قسمتها یه دنباله مرتب رو تشکیل میده[combine].

    {برای اینکه تئوری الگوریتم براتون جا بیفته یه مثال من درآوردی میزنم :P اگه بخوایم یه عده دانش آموز کلاس اولی که توی صف وایسادن بترتیب قد مرتب کنیم بر اساس این الگوریتم اولین مرحله تقسیم صف کلاس اولی ها به دو قسمته که مثلا توی قسمت اول دانش آمورهایی که یک متر قد دارن یا قدشون کمتر یه متره قرار میگیرن و توی قسمت دوم دانش آموزایی که قدشون یک متر یا بیشتر یه متر باشه(تصور کنید) بعد روی هر کدوم از این دو قسمت این مرحله تکرار میشه.}

    همونطوری که دقت کردید توی هر مرحله تقسیم عناصر [divide] نیاز به عنصری داریم که بقیه عناصر با اون سنجیده بشن(یک متر توی مثال کلاس اولیها) به این عنصر محور یا pivot میگیم.

    حالا یه مثال عملی تر میزنم تا بهتر متوجه بشید:


    لیست اعداد شکل 1 رو در نظر بگیرید:
    برای ساده شدن کار فرض کنید که 75 رو به عنوان محور در نظر میگیریم(pivot).با یک نیگاه مشخصه که اعداد 75و65و55و61و68 کوچکتر و مساوی pivot هستند(smaller than pivot) و اعداد 81و93و100و78و98و84 بزگتر از محور( larger than pivot)
    الگوریتم میگه لیست رو باید جوری مرتب کنیم که اعداد موجود در(smaller than pivot) قبل از 75 و اعداد موجود در( larger than pivot) بعد از 75 ظاهر بشن(شکل 1-1)
    تنها کاری که میخوایم صورت بگیره اینه که عناصر سمت چپ 75 باید کوچکتر از 75 بشن و عناصر سمت راست 75 بزرگتر از 75.نگران این نیستیم که توی هر کدوم از این دوقسمت چند تا عدد مرتب شده داریم.
    حالا شکلهای دیگه رو با هم مرور میکنیم.


    دو عمل جستجو در الگوریتم quicksort انجام میشه.یکی از انتهای راست لیست برای یافتن عناصر کوچکتر یا مساوی با 75 (pivot) و دیگری از انتهای سمت چپ برای پیدا کردن عناصر بزگتر از 75.توی شکل 2 مشخصه که اولین عنصر جستجو از سمت راست 68 است و اولین عنصر در جستجو از چپ 84 است.
    بعد از یافتن این دو عدد که یکی کوچکتر از 75 و دیگری بزگتر از 75 هست ,جای اونها رو باهم عوض میکنیم(شکل 3).
    این دو تا جستجو یکی از سمت راست و دیگری از سمت چپ پی گیری میشن و عمل جابجایی هم صورت میگیره تا در نهایت به عدد 55 برسیم یعنی دو اشاره گر جستجو بهم رسیدن که این یعنی جستجو به پایان رسیده ,و عدد 55 و 75 رو با هم جابجا میکنیم و خلاص
    توی لیست آخر همه اعداد سمت چپ 75 از اون کمترند و همه اعداد سمت راستش ازش بیشتر.حالا ما میتونیم همین مراحل رو جداگانه روی هر کدوم از این دو قسمت انجام بدیم تا در نهایت لیست مرتب بشه.


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

    void quicksort (int[] a, int lo, int hi)
    {
    // lo is the lower index, hi is the upper index
    // of the region of array a that is to be sorted
    int i=lo, j=hi, h;
    int x=a[(lo+hi)/2];

    // partition
    do
    {
    while (a[i]<x) i++;
    while (a[j]>x) j--;
    if (i<=j)
    {
    h=a[i]; a[i]=a[j]; a[j]=h;
    i++; j--;
    }
    } while (i<=j);

    // recursion
    if (lo<j) quicksort(a, lo, j);
    if (i<hi) quicksort(a, i, hi);
    }




    تحلیل الگوریتم هم باشه واسه بعد فعلا میخوام برم بخسبم :?


    phantasm

  2. #2
    تحلیل الگوریتم:
    بهترین حالت برای الگوریتم 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 در اون لیست انتخاب میشه که معمولا به عنصر وسط لیست نزدیکتره.و باعث میشه پیچیدگی زمانی الگوریتم کم بشه.

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






    phantasm

  3. #3
    سلام مرسی از الگوریتمتون خیلی خیلی مفید واقع شدید امیدوارم که در کنکور خیلی خیلی موفق باشید
    حق یاورتون و دعای من همراهتون

  4. #4
    کاربر تازه وارد آواتار parandeh1383
    تاریخ عضویت
    تیر 1383
    محل زندگی
    تهران
    پست
    77

    نقل قول: Quick Sort

    من شكل هايي گه گفتيد رو نديدم!

  5. #5
    کاربر جدید آواتار kh_rouhi
    تاریخ عضویت
    دی 1387
    محل زندگی
    رشت
    سن
    35
    پست
    13

    نقل قول: Quick Sort

    خیلی ممنون از توضیح خوبتون.

  6. #6
    کاربر دائمی آواتار Reza,M
    تاریخ عضویت
    تیر 1389
    محل زندگی
    ايران سراي من است
    پست
    412

    نقل قول: Quick Sort

    با سلام
    دوست عزيز ميشه چگونگي و مراحل بدست آوردن پيچيدگي زماني اين الگوريتم رو هم بنويسي ؟

  7. #7

    نقل قول: Quick Sort

    نقل قول نوشته شده توسط Reza,M مشاهده تاپیک
    با سلام
    دوست عزيز ميشه چگونگي و مراحل بدست آوردن پيچيدگي زماني اين الگوريتم رو هم بنويسي ؟
    به پیوند زیر مراجعه کنید:

    http://www.algorithmha.ir/post.aspx?no=29

    باز اگه متوجه نشدید توضیح بیشتر می‌دم.

  8. یک شنبه 08 آبان 1390, 20:18 عصر


  9. #8

    نقل قول: Quick Sort

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

تاپیک های مشابه

  1. الگوریتم Quick sort
    نوشته شده توسط solaleh در بخش برنامه نویسی اسمبلی خانواده x86
    پاسخ: 4
    آخرین پست: پنج شنبه 26 شهریور 1388, 20:49 عصر
  2. الگوریتم quick sort (سوال)
    نوشته شده توسط حمید_65 در بخش برنامه نویسی با زبان C و ++C
    پاسخ: 3
    آخرین پست: چهارشنبه 29 خرداد 1387, 21:21 عصر
  3. مرتب کردن به روش Quick sort
    نوشته شده توسط coralisland_17 در بخش برنامه نویسی در 6 VB
    پاسخ: 2
    آخرین پست: شنبه 12 خرداد 1386, 11:35 صبح
  4. quick sort
    نوشته شده توسط nima_63 در بخش برنامه نویسی با زبان C و ++C
    پاسخ: 4
    آخرین پست: سه شنبه 12 اردیبهشت 1385, 09:18 صبح

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •