سوال از الگوریتم sort

[omidjadidolislam]

آقا سلام
آقا ببخشید مزاحمتون میشم،چون چشمم به شما نمیخوره کمتر خجالت میکشم.
یه سوال دیگه و خدا کنه این یکی کتاب نخواد

اقا یه سوال از الگوریتم کامپیوتری دارم
اگه فرصت داشتید
1)//آقا در الگوریتمهای sort الگوریتم مرتب سازی ادغامی را نمیفهمم

2) اگه ما یکسری شماره مرتب داشته باشیم و ناگهان شماره ای جدید وارد شود چه الگوریتمی sort طوری که در کوتاهترین زمان به نتیجه برسیم مناسب است
3)//کلا محاسبه order الگوریتمها خصوصا این الگوریتم چگونه است

آقا حتی اگه صدا تون را بفرستید اگه فرصت داشتید و ممکن بود محبت کرده اید

[NotAtMyDesk]

الگوریتم مرتب سازی ادغامی را نمیفهمم sort آقا در الگوریتمهای

مرتب سازی ادغامی یا همون Merge sort از روش تقسیم و حل استفاده می کنه، به این صورت که اگه ما یه آرایه برای مرتب کردن داشته باشیم اول نیمه ی سمت راست و بعد نیمه ی سمت چپ رو مرتب کرده و بعد با هم ادغام می کنیم (مرتب کردن هر کدوم از این نیمه ها هم به صورت بازگشتی انجام می شه) و بعد این دو قسمت مرتب شده رو با هم ادغام می کنیم، حالا چه شکلی ادغام می شن؟ الان ما دو قسمت مرتب شده داریم (نیمه ی راست و چپ آرایه) یه اشاره گر به اول هر کدوم از این قسمت ها در نظر می گیریم بعد توی این دو قسمت جایی که اشاره گر به اون اشاره می کنه رو با هم مقایسه می کنیم (که در اول کار خونه ی اول دو قسمت با هم مقایسه می شه) هر عنصر که کوچکتر بود در خروجی نوشته می شه و اشاره گر اون قسمت ، یکی جلو برده می شه این کار ادامه پیدا می کنه تا این که اشاره گر یکی از قسمت ها به آخرش برسه، بقیه ی اون عناصری که باقی مونده رو هم در خروجی می نویسیم.

[omidjadidolislam]

مرتب سازی ادغامی یا همون Merge sort از روش تقسیم و حل استفاده می کنه، به این صورت که اگه ما یه آرایه برای مرتب کردن داشته باشیم اول نیمه ی سمت راست و بعد نیمه ی سمت چپ رو مرتب کرده و بعد با هم ادغام می کنیم (مرتب کردن هر کدوم از این نیمه ها هم به صورت بازگشتی انجام می شه) و بعد این دو قسمت مرتب شده رو با هم ادغام می کنیم، حالا چه شکلی ادغام می شن؟ الان ما دو قسمت مرتب شده داریم (نیمه ی راست و چپ آرایه) یه اشاره گر به اول هر کدوم از این قسمت ها در نظر می گیریم بعد توی این دو قسمت جایی که اشاره گر به اون اشاره می کنه رو با هم مقایسه می کنیم (که در اول کار خونه ی اول دو قسمت با هم مقایسه می شه) هر عنصر که کوچکتر بود در خروجی نوشته می شه و اشاره گر اون قسمت ، یکی جلو برده می شه این کار ادامه پیدا می کنه تا این که اشاره گر یکی از قسمت ها به آخرش برسه، بقیه ی اون عناصری که باقی مونده رو هم در خروجی می نویسیم.

آقا ممنون از توضیحاتون ولی چیزی نگرفتم
و در کل سه سوال داشتم اگه میشه با مثال بفرمایید

[Daleeeeer]

در الگوریتمهای sort الگوریتم مرتب سازی ادغامی را نمیفهمم
سلام. دوستمون خیلی قشنگ این الگوریتم رو توضیح داد. اما من برات مثال می گذارم شاید بهتر متوجه بشی:
ابتدا n عنصر یک آرایه N عنصری رو به طول 1 در نظر می گیریم. بعد این آرایه ها رو 2 به 2 با هم ادغام می کنیم تا n/2 آرایه به اندازه 2 بدست بیاد. سپس این n/2 آرایه رو دوبدو باهم ادغام می کنیم و همین طورادامه میدیم تا آرایه تموم بشه. اما مثال:
یک آرایه به شکل زیر داریم:
66,33,40,22,55,88,60,11,80,20,50,44,77,30
مرحله1: 66و33 40و22 88و55 60و11 80و20 50و44 77و30
مرحله 2: 66و40و33و22 88و60و55و11 80و50و44و20 77و30
مرحله 3: 88و66و60و55و40و33و22و11 80و77و50و44و30و20
مرحله 4: 88و80و77و66و60و55و50و44و40و33و30و22و20 و11
می بینی که پس از 4 مرحله آرایه مرتب شده. این الگوریتم به حداکثر [log n] مرحله برای مرتب کردن آرایه n عنصری احتیاج دارد.

اگه ما یکسری شماره مرتب داشته باشیم و ناگهان شماره ای جدید وارد شود چه الگوریتمی sort طوری که در کوتاهترین زمان به نتیجه برسیم مناسب است
اما جواب سوال دوم: اگر آرایه ای که داری نامرتب باشه، quick sort از همه بهتر عمل می کنه. اما در آرایه مرتب این الگوریتم بدترین عملکرد رو داره. خیلی ها این اشتباه رو می کنند و فکر می کنند که quick sort hاز همه بهتره. اما نقطه ضعف اون اینه!. برای آرایه مرتب اگه اشتباه نکنم bubble sort که از flag استفاده می کنه، بهترینه. (باز شک دارم، باید تست کنم.)


کلا محاسبه order الگوریتمها خصوصا این الگوریتم چگونه است
این محاسبه ها معمولاً بر اساس خود برنامه ها حساب می شن. به این صورت که اين كه چیزهایی که نیاز داریم بدونيم اینهاست:
زمان اجرای دستورات ثابت، همواره ثابت است.
زمان اجرای حلقه به اندازه تکرار اون هست.
اما به طور کلی این قضیه (بدست آوردن اردر زمانی) تجربی هست و بیشتر بر اساس استقرا و تجربه بدست می آید.


خدا کنه این یکی کتاب نخواد
برو کتاب ساختمان تننباوم و یا طراحی الگوریتم نیپولیتان رو بخون. خیلی خوب اردر زمانی رو توضیح دادن.

تا فردا کد merge sort و bubble sort رو برات قرار می دم.
خداحافظ.

[dadvand]

آقا سلام
آقا ببخشید مزاحمتون میشم،چون چشمم به شما نمیخوره کمتر خجالت میکشم.
یه سوال دیگه و خدا کنه این یکی کتاب نخواد

اقا یه سوال از الگوریتم کامپیوتری دارم
اگه فرصت داشتید
1)//آقا در الگوریتمهای sort الگوریتم مرتب سازی ادغامی را نمیفهمم

2) اگه ما یکسری شماره مرتب داشته باشیم و ناگهان شماره ای جدید وارد شود چه الگوریتمی sort طوری که در کوتاهترین زمان به نتیجه برسیم مناسب است
3)//کلا محاسبه order الگوریتمها خصوصا این الگوریتم چگونه است

آقا حتی اگه صدا تون را بفرستید اگه فرصت داشتید و ممکن بود محبت کرده اید

1 - یک لیست 100 تایی رو به شما میگن مرتب کنی شما به نظرت طاقت فرسا میاد ، میگی خوب من این رو به دو لیست 50 تایی تقسیم میکنم و سپس هر کدام را مرتب کرده و آنها رو در هم ادغام میکنم . باز میگی 50 تایی هم زیاده ، من هر کدوم رو به دو لیست 25 تایی تقسیم میکنم و ...... تا آخر
این مرتب سازی ادغامی است .
2-برای درج در لیست مرتب از جستجوی دودویی برای پیدا کردن مکان کلید جدید استفاده میشود . که زمان جستجویی دودویی logn است . اگه جستجویی دودویی رو مشکل داری بگو تا توضیح بدم .
3- تعداد بار اجرای دستور اصلی order الگوریتم است که البته بدترین حالت ، حالت متوسط و بهترین حالت رو داریم .
در merg sort بدترین و حالت متوسط n logn است اینکه حالا چطور محاسبه میشه مفصله و نیاز به مقدمات هست حداقل من توانایی خلاصه گویی آن را ندارم . چون گفتی ارجاعت ندیم به کتاب ، نمیگم رجوع کن به کتاب طراحی الگوریتم مهندس قمی یا مقدمه ای بر الگوریتمها نوشته توماس (زبان اصلی ) :لبخند:
موفق باشی

[NotAtMyDesk]

فرض کن اعداد 5،2،4،7،1،3،2،6 به ما داده شده، ابتدا باید اعداد سمت راست و بعد اعداد سمت چپ را مرتب کنیم، یعنی 5،2،4،7 را مرتب می کنیم برای مرتب کردن این قسمت نیز ابتدا سمت چپ بعد سمت راست را مرتب می کنیم، یعنی اول 5،2 را مرتب می کنیم برای مرتب کردن این قسمت نیز ابتدا سمت چپ و بعد سمت راست را مرتب می کنیم یعنی اول 5 و بعد 2 ! 5 مرتب است، 2 هم همین طور! حالا که سمت راست و چپ مرتب است پس حالا وقت ادغام کردن است 2 و 5 را مقایسه می کنیم 2 از 5 کوچکتر است پس آن را قبل از 5 قرار می دهیم 2،5 مرتب شد سمت راست رو هم به همین طریق مرتب می کنیم حالا 2،5 و 4،7 رو با هم ادغام می کنیم ، دو عدد اول رو با هم مقایسه می کنیم 2 از 4 کوچکتر است 2 را بر می داریم، بعد 5 و 4 را مقایسه می کنیم چون 4 کوچکتر است، 4 را برمی داریم بعد 5 و 7 را مقایسه می کنیم و چون 5 کوچکتر است آن را برمی داریم و آخر سر هم که فقط 7 باقی مانده پس آن را برمی داریم ، ترتیب اعداد به این صورت شد 2،4،5،7 که اعداد مرتب شده هستند این کار را همین طور ادامه می دهیم تا کل اعداد مرتب شوند.
http://i33.tinypic.com/2cr66fr.jpg

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



2) اگه ما یکسری شماره مرتب داشته باشیم و ناگهان شماره ای جدید وارد شود چه الگوریتمی sort طوری که در کوتاهترین زمان به نتیجه برسیم مناسب است

این چیزی که می گی شبیه set توی STL در ++C هستش، که همیشه یه آرایه ی مرتب شده داریم و اگه یه چیزی بخوایم توش قرار بدیم به صورت مرتب شده قرار می ده در مورد Set می دونم که با زمان insert ، log n می کنه و می دونم که از Red-Black Tree استفاده می کنه اما خودم الگوریتمش رو بلد نیستم، فکر کنم اگه از اون استفاده کنی خوب باشه



3)//کلا محاسبه order الگوریتمها خصوصا این الگوریتم چگونه است

محاسبه ی Order الگوریتم ها خودش یه بحث طولانیه که اگه تو کتابا بگردی می تونی چیزای زیادی در موردش یاد بگیری و در کل به نظرم یه چیزه تجربیه! هر چی Order الگوریتم های بیشتری رو حساب کنی بیشتر دستت راه میفته
در مورد این الگوریتم هم Orderش N log N هستش

[omidjadidolislam]

فرض کن اعداد 5،2،4،7،1،3،2،6 به ما داده شده، ابتدا باید اعداد سمت راست و بعد اعداد سمت چپ را مرتب کنیم، یعنی 5،2،4،7 را مرتب می کنیم برای مرتب کردن این قسمت نیز ابتدا سمت چپ بعد سمت راست را مرتب می کنیم، یعنی اول 5،2 را مرتب می کنیم برای مرتب کردن این قسمت نیز ابتدا سمت چپ و بعد سمت راست را مرتب می کنیم یعنی اول 5 و بعد 2 ! 5 مرتب است، 2 هم همین طور! حالا که سمت راست و چپ مرتب است پس حالا وقت ادغام کردن است 2 و 5 را مقایسه می کنیم 2 از 5 کوچکتر است پس آن را قبل از 5 قرار می دهیم 2،5 مرتب شد سمت راست رو هم به همین طریق مرتب می کنیم حالا 2،5 و 4،7 رو با هم ادغام می کنیم ، دو عدد اول رو با هم مقایسه می کنیم 2 از 4 کوچکتر است 2 را بر می داریم، بعد 5 و 4 را مقایسه می کنیم چون 4 کوچکتر است، 4 را برمی داریم بعد 5 و 7 را مقایسه می کنیم و چون 5 کوچکتر است آن را برمی داریم و آخر سر هم که فقط 7 باقی مانده پس آن را برمی داریم ، ترتیب اعداد به این صورت شد 2،4،5،7 که اعداد مرتب شده هستند این کار را همین طور ادامه می دهیم تا کل اعداد مرتب شوند.
http://i33.tinypic.com/2cr66fr.jpg

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


این چیزی که می گی شبیه set توی STL در ++C هستش، که همیشه یه آرایه ی مرتب شده داریم و اگه یه چیزی بخوایم توش قرار بدیم به صورت مرتب شده قرار می ده در مورد Set می دونم که با زمان insert ، log n می کنه و می دونم که از Red-Black Tree استفاده می کنه اما خودم الگوریتمش رو بلد نیستم، فکر کنم اگه از اون استفاده کنی خوب باشه


محاسبه ی Order الگوریتم ها خودش یه بحث طولانیه که اگه تو کتابا بگردی می تونی چیزای زیادی در موردش یاد بگیری و در کل به نظرم یه چیزه تجربیه! هر چی Order الگوریتم های بیشتری رو حساب کنی بیشتر دستت راه میفته
در مورد این الگوریتم هم Orderش N log N هستش

آقا اگه ممکنه order یکی دو تا را شما روش بدست آوردنشو بفرمایید و چند تا دیگه بدید تا من بدست بیاورم

[omidjadidolislam]

1 - یک لیست 100 تایی رو به شما میگن مرتب کنی شما به نظرت طاقت فرسا میاد ، میگی خوب من این رو به دو لیست 50 تایی تقسیم میکنم و سپس هر کدام را مرتب کرده و آنها رو در هم ادغام میکنم . باز میگی 50 تایی هم زیاده ، من هر کدوم رو به دو لیست 25 تایی تقسیم میکنم و ...... تا آخر
این مرتب سازی ادغامی است .
2-برای درج در لیست مرتب از جستجوی دودویی برای پیدا کردن مکان کلید جدید استفاده میشود . که زمان جستجویی دودویی logn است . اگه جستجویی دودویی رو مشکل داری بگو تا توضیح بدم .
3- تعداد بار اجرای دستور اصلی order الگوریتم است که البته بدترین حالت ، حالت متوسط و بهترین حالت رو داریم .
در merg sort بدترین و حالت متوسط n logn است اینکه حالا چطور محاسبه میشه مفصله و نیاز به مقدمات هست حداقل من توانایی خلاصه گویی آن را ندارم . چون گفتی ارجاعت ندیم به کتاب ، نمیگم رجوع کن به کتاب طراحی الگوریتم مهندس قمی یا مقدمه ای بر الگوریتمها نوشته توماس (زبان اصلی ) :لبخند:
موفق باشی

آقا سلام
آقا جستجوی دودویی برای یافتن کلید جدید استفاده میشه یعنی چه؟

[Daleeeeer]

سلام. ببين وقتي مي خواي يك كليد (داده هاي تو ليست) جديد رو توي ازايه وارد كني. چون جاي اون اول كار نامعلوم هست. شما بايد اول جاي اون رو پيدا كني و بعد عمليات درج رو انجام بدي
تو اين الگوريتم (با فرض مرتب بودن ليست) مياي ابتدا ليست رو نصف مي كني و بعد جاي كليد رو پيدا مي كني كه توي يكي از اين دو بخش قرار داره. بعد براي اون نصفه باز همين اعمال رو انجام مي دي تا جاي كليد پيدا بشه.

[omidjadidolislam]

دوستان گرامی سلام
ممنون از جوابهای شما
یکی از دوستانم یه فایل برای من میل کرده که توضیحات جالبی داده برای بقیه دوستان میگذارم البته صدا هم داره اگه کسی خواست بگه برایش میل کنم
1-اگه کسی میتونه کمی راجع به راه بدست آوردن order الگوریتم یعنی O(nlogn کمک کنه
2-اگه کسی کدی هم از این الگوریتم داره ممنون میشیم ببینیم

[NotAtMyDesk]

2-اگه کسی کدی هم از این الگوریتم داره ممنون میشیم ببینیم




void merge_sort (int n, int a[])
{
const int n_first = n / 2, n_second = n - n_first;
int first[n_first], second[n_second];
if (n > 1)
{
for (int i = 0; i < n_first; i++)
first[i] = a[i];
for (int i = n_first; i < n; i++)
second[i - n_first] = a[i];
merge_sort (n_first, first);
merge_sort (n_second, second);
merge (first, n_first, second, n_second, a);
}
}

void merge (int first[], int n_first, int second[], int n_second, int a[])
{
int ifirst = 0, isecond = 0, i = 0;
while (ifirst < n_first && isecond < n_second)
{
if (first[ifirst] < second[isecond])
a[i] = first[ifirst++];
else
a[i] = second[isecond++];
i++;
}
if (ifirst < n_first)
for (int k = ifirst; k < n_first; k++)
a[i++] = first[k];
else
for (int k = isecond; k < n_second; k++)
a[i++] = second[k];
}

[omidjadidolislam]

دوستان گرامی سلام
ممنون از جوابهای شما
یکی از دوستانم یه فایل برای من میل کرده که توضیحات جالبی داده برای بقیه دوستان میگذارم البته صدا هم داره اگه کسی خواست بگه برایش میل کنم
1-اگه کسی میتونه کمی راجع به راه بدست آوردن order الگوریتم یعنی O(nlogn کمک کنه
2-اگه کسی کدی هم از این الگوریتم داره ممنون میشیم ببینیم[/quote]

[rostamkhani]

سلام
آقا کسی کدی نداره
آقا در مورد الگوریتم بازگشتی کسی میتونه توضیح ساده ای بده

[omidjadidolislam]

void merge_sort (int n, int a[])
{
const int n_first = n / 2, n_second = n - n_first;
int first[n_first], second[n_second];
if (n > 1)
{
for (int i = 0; i < n_first; i++)
first[i] = a[i];
for (int i = n_first; i < n; i++)
second[i - n_first] = a[i];
merge_sort (n_first, first);
merge_sort (n_second, second);
merge (first, n_first, second, n_second, a);
}
}

void merge (int first[], int n_first, int second[], int n_second, int a[])
{
int ifirst = 0, isecond = 0, i = 0;
while (ifirst < n_first && isecond < n_second)
{
if (first[ifirst] < second[isecond])
a[i] = first[ifirst++];
else
a[i] = second[isecond++];
i++;
}
if (ifirst < n_first)
for (int k = ifirst; k < n_first; k++)
a[i++] = first[k];
else
for (int k = isecond; k < n_second; k++)
a[i++] = second[k];
}



آقا دست شما درد نکنه
آیا میشه جوری این کد با روش بازگشتی را طوری توضیح بدید که ما هم بتونیم چنین کدی بزنیم حتی اگه در توضیح صدای خودتون رو لطف کنید برام میل کنید ممنون میشم
چون خوب الگوریتم های بازگشتی را نمیتونم تصور کنم و بنویسمomid_ebook@yahoo.com