PDA

View Full Version : Quick Sort



phantasm
دوشنبه 31 فروردین 1383, 01:36 صبح
چند وقته که به دلایل مختلف , اعم از کنکور -علاقه-خوردن سرم تو دیوار و غیره افتادم تو کار مطالعه الگوریتم های مختلف.
برای همین گفتم شاید بد نباشه یکم مفید واقع بشیم :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

phantasm
دوشنبه 31 فروردین 1383, 14:01 عصر
تحلیل الگوریتم:
بهترین حالت برای الگوریتم 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 در اون لیست انتخاب میشه که معمولا به عنصر وسط لیست نزدیکتره.و باعث میشه پیچیدگی زمانی الگوریتم کم بشه.

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






phantasm

koroshking
جمعه 05 خرداد 1385, 08:20 صبح
سلام مرسی از الگوریتمتون خیلی خیلی مفید واقع شدید امیدوارم که در کنکور خیلی خیلی موفق باشید
حق یاورتون و دعای من همراهتون

parandeh1383
سه شنبه 03 آذر 1388, 15:09 عصر
من شكل هايي گه گفتيد رو نديدم!

kh_rouhi
یک شنبه 05 دی 1389, 21:26 عصر
خیلی ممنون از توضیح خوبتون.

Reza,M
دوشنبه 26 اردیبهشت 1390, 00:11 صبح
با سلام
دوست عزيز ميشه چگونگي و مراحل بدست آوردن پيچيدگي زماني اين الگوريتم رو هم بنويسي ؟

مسعود اقدسی فام
دوشنبه 26 اردیبهشت 1390, 20:45 عصر
با سلام
دوست عزيز ميشه چگونگي و مراحل بدست آوردن پيچيدگي زماني اين الگوريتم رو هم بنويسي ؟

به پیوند زیر مراجعه کنید:


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


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

motavalede62
یک شنبه 22 اردیبهشت 1392, 15:48 عصر
واقعا عالی توضیح دادی
اگه لطف کنی این پرژه رو با استفاده از چند نخی هم ارائه بدی ممنون میشم