مرتب سازی و جست و جو در آرایه های دو بعدی

[armita]

فرض کنید که می خوایم یک آرایه ی دو بعدی رو مرتب کنیم به صورتی که هر سطر و هر ستون مرتب باشند !
چه جوری باید این کار رو انجام بدیم ؟
و بعد از این که این آرایه مرتب شد ، سریع ترین روشی که بتونیم در آرایه جست و جو کنیم چیه ؟
لطفا دوستانی که جواب رو می دونن جواب ندن (!) تا با افرادی که در این مورد اطلاعی ندارن بحث کنیم یک الگوریتم مناسب پیدا کنیم

 

[trustme]

پاسخ : آرایه های دو بعدی

فکر می کنم منظورتون از آرایه دو بعدی «آرایه ی دوبعدی مربعی» باشه! زبان مورد نظر رو هم مشخص کنی می تونیم در مورد امکاناتش حرف بزنیم!
فکر می کنم به صورت پیشفرض منظورتون C بوده!

اولین چیزی که به نظر می رسه: سطرها رو ثرت کنیم، بعد اول سطر ها رو به صورت ستونی ثرت کنیم!
ولی راه حل های بهتری باید وجود داشته باشد ...

 

[armita]

پاسخ : آرایه های دو بعدی

فکر می کنم منظورتون از آرایه دو بعدی «آرایه ی دوبعدی مربعی» باشه! زبان مورد نظر رو هم مشخص کنی می تونیم در مورد امکاناتش حرف بزنیم!
فکر می کنم به صورت پیشفرض منظورتون C بوده!

اولین چیزی که به نظر می رسه: سطرها رو ثرت کنیم، بعد اول سطر ها رو به صورت ستونی ثرت کنیم!
ولی راه حل های بهتری باید وجود داشته باشد ...

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

 

[trustme]

پاسخ : آرایه های دو بعدی

فکر می کنم دنبال حرکت قطری باشین!

 

[Sylar]

پاسخ : آرایه های دو بعدی

من اینطوری بدست آوردم
sort به صورت

o(n2lgn2)

و برای search هم

o(lgn2)

یک سری خورده اثبات هم توی ذهنم هست که کمترین از این نمیشه.

 

[trustme]

پاسخ : آرایه های دو بعدی

اینایی که نوشتی دقیقا یعنی چی !!!؟ من نمی دونم!

 

[Sylar]

پاسخ : آرایه های دو بعدی

اینایی که نوشتی دقیقا یعنی چی !!!؟ من نمی دونم!

توی الگوریتم های برنامه نویسی برای تشخیص بهینه گی یک الگوریتم نسبت به یک الگوریتم دیگه میان و طبق یک سری قواعد(این قواعد اول کتاب CLRS در موردشون توضیح داده)
سرعت اجرای الگوریتم را بررسی میکنن. اینکه این قواعد چین را لازم نیست بدونید (یعنی لازم نداری) بشون میگن Algorithm Order .
اگر Order الگوریتمی کمتر از یک الگوریتم دیگه باشه یعنی در زمان کمتری همون کار را میتونه انجام بده.
مثلا اثبات میکنن که نمیشه هیچ الگوریتمی ارائه داد که آرایه n عضوی را با تعداد حرکاتی کمتر از n.lgn مرتب کنه. (lgn یعنی لگاریتم n به پایه 2)
مثلا فرض کن الگوریتم مرتب کردنت این باشه که بیایی هر بار کوچیکترین عدد را پیدا کنی و بزاریش اول آرایه تا کل آرایه ات را بچینی.
اینطوری برای مرحله ی اول باید در بین n عدد کوچکترین را پیدا کنی که میشه n حرکت. بعدش بین n-1 عدد باید کوچکترین را پیدا کنی که میشه n-1 حرکت
به همین ترتیب تا دیگه هیچ عددی باقی نمونه. اینطوری تعداد حرکاتت میشه n+n-1+n-2+...+1
که میشه n(n+1)/2 که به طور خلاصه بش میگن Order الگوریتم n2 اه.(سعی میکنن نزدیک ترین عدد روند شده را بگن)

من اومدم گفتم که روشی دارم که توش با n2.lgn2 میتونم کل جدول را سورت کنم (یعنی با n2.lgn2 حرکت) و بعدش هم با lgn2 حرکت هر عددی را میخوام پیدا کنم توش.

 

[trustme]

پاسخ : آرایه های دو بعدی

نمی تونستی به جای O مثلا Order بزاری !؟

من با خودم فکر می کنم تا الگوریتمی پیدا بکنم که ایطوری باشه حالا تو الگوریتم رو نگو بزار یه مقدار ملت فکر کنن

 

[Sylar]

پاسخ : آرایه های دو بعدی

نمی تونستی به جای O مثلا Order بزاری !؟

من با خودم فکر می کنم تا الگوریتمی پیدا بکنم که ایطوری باشه حالا تو الگوریتم رو نگو بزار یه مقدار ملت فکر کنن

نه نمیشد . چون وقتی میگن فلان الگوریتم o اه n2 به این معنی نیست که order اش n2 اه.
o - O - تتا و... هرکدومشون یک نماد هستند برای تعیین نوع مقیاس
مثلا اگر الگوریتمی Teta ی n2 باشه یعنی با دقیقا n2 حرکت به هدف میرسه . نه کمتر نه بیشتر
وقتی میگن الگوریتمی o ی n2 یعنی اینکه در بد ترین حالت با n2 حرکت به هدف میرسه. یعنی کمتر هم میشه.ولی بیشتر نمیشه

 

[armita]

پاسخ : آرایه های دو بعدی

خب من می گم بیایم این آرایه ی دو بعدی مون رو بریزیم توی یک آرایه ی یک بعدی بعد اون رو با روش هرمی و یا کوییک مرتب کنیم.
بعد این آرایه ی یک بعدی رو به ترتیب توی آرایه دو بعدیمون می چینیم

برای جست جو ، نظر من اینه که اول عنصر وسط آرایه رو چک کنیم ، بعد یک چهارم آرایه مون حذف می شه ، بعد همین طور به صورت قطری بریم جلو .
نظرتون چیه ؟!

 

[Sylar]

پاسخ : آرایه های دو بعدی

خب من می گم بیایم این آرایه ی دو بعدی مون رو بریزیم توی یک آرایه ی یک بعدی بعد اون رو با روش هرمی و یا کوییک مرتب کنیم.
بعد این آرایه ی یک بعدی رو به ترتیب توی آرایه دو بعدیمون می چینیم

برای جست جو ، نظر من اینه که اول عنصر وسط آرایه رو چک کنیم ، بعد یک چهارم آرایه مون حذف می شه ، بعد همین طور به صورت قطری بریم جلو .
نظرتون چیه ؟!

میتونی بیشتر توضیح بدی که چطوری تصمیم گیری میکنی برای حذف ۱/۴ آرایه؟

 

[armita]

پاسخ : آرایه های دو بعدی

میتونی بیشتر توضیح بدی که چطوری تصمیم گیری میکنی برای حذف ۱/۴ آرایه؟

فرض کنید می خوایم عدد k رو در آرایه پیدا کنیم .
وقتی خونه ی وسط آرایه رو با k مقایسه کنیم ، اگر از k بزرگتر باشه ، 1/4 راست و پایین آرایه حذف میشه .
اگر هم کوچکتر باشه ، 1/4 بالا و چپ آرایه حذف میشه.

 

[Sylar]

پاسخ : مرتب سازی و جست و جو در آرایه های دو بعد&#17

فرض کنید می خوایم عدد k رو در آرایه پیدا کنیم .
وقتی خونه ی وسط آرایه رو با k مقایسه کنیم ، اگر از k بزرگتر باشه ، 1/4 راست و پایین آرایه حذف میشه .
اگر هم کوچکتر باشه ، 1/4 بالا و چپ آرایه حذف میشه.

مگه نیومدی آرایه ات را به ترتیب توی جدول چیدی؟
وقت خونه ی وسط را با K مقایسه کردی اگر از K بزرگتر بود یعنی تمام خونه های بعدش جواب ما نخواهد بود. چون توی آرایه مرتب شدمون بعد از اون خونه تمام خونه ها
بزرگتر از اون خونه هستند. پس نصف جدول حذف میشه نه ۱/۴.
چون داریم Binary Search میریم جستجومون میشه lgn2

 

[armita]

پاسخ : مرتب سازی و جست و جو در آرایه های دو بعد&#17

مگه نیومدی آرایه ات را به ترتیب توی جدول چیدی؟
وقت خونه ی وسط را با K مقایسه کردی اگر از K بزرگتر بود یعنی تمام خونه های بعدش جواب ما نخواهد بود. چون توی آرایه مرتب شدمون بعد از اون خونه تمام خونه ها
بزرگتر از اون خونه هستند. پس نصف جدول حذف میشه نه ۱/۴.
چون داریم Binary Search میریم جستجومون میشه lgn2

فکر کنم این تیکه ی سوال رو خوب توضیح ندادم !
منظورم این بود که یک آرایه رو می خواهیم مرتب کنیم ، بعد فرض می کنیم که یک آرایه ی مرتب داریم ولی لزوما با روشی که ما گفتیم مرتب نشده ، در نتیجه نصف آرایه حذف نمی شه.

 

[Sylar]

پاسخ : مرتب سازی و جست و جو در آرایه های دو بعد&#17

یه نکته ای:

log(n^2) = 2*logn پس فرقی نداره Binary Search توی آرایه ی n^2 باشه یا توی آرایه ی یک بعدی n تایی! در واقع از نظر order یکی هستند!!

پس اگه همه ی اعدادو توی یه آرایه ی یک بعدی بریزیم، مرتب کردنش می شه n^2 * log(n^2) = 2 * n ^2 *logn و جستجو کردن هم می شه log(n^2) = 2 * logn

این راحت ترین راهه!! دارم فکر می کنم راه بهتری هم داره یا نه!!

کاشکی حداقل پستهای قبل را یک دور میخوندی!

 

[stevendeljoo]

پاسخ : مرتب سازی و جست و جو در آرایه های دو بعدی

سریع ترین راه quick sort ه که الگوریتم پیچیده ای داره
فعلا خودم دارم زور میزنم بنویسمش
وقتی نوشتم کدشو میذارم

 

[ibtkm]

پاسخ : مرتب سازی و جست و جو در آرایه های دو بعدی

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

 

[ErfanDK]

پاسخ : مرتب سازی و جست و جو در آرایه های دو بعدی

خوب برای مرتب کردن می تونیم از روی پوینتر عملیات انجام بدیم ( تو C) دیگه لازم نیست آرایه رو بریزیم توی یک آرای یک بعدی بعد مرتب کنیم و بعد دوباره بیاریمش توی یک آرایه دو بعدی. چون که تو حافظه یک ارایه دوبعدی دقیقا مثل یک آرایه یک بعدی ذخیره میشه. در مورد سرچ هم همین روش رو روی پوینتر ها با الگوریتم باینری سرپ اجرا می کنیم. البته لازمه که قبل سرچ آرایه رو مرتب کنیم. با استفاده از پوینتر مقدار حافظه ی کمتری هم استفاده میشه.(چون لازم نیست آرایه بسازیم)