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
برای همین گفتم شاید بد نباشه یکم مفید واقع بشیم :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