الگوریتم مرتب سازی جایگذاری

[yas1213]

یک الگوریتم مرتب سازی جایگذاری که برای یافتن موقعیت جایگذاری بعدی از جست وجوی دودویی استفاده کند.

[pesar irooni]

اصلا سوالتون واضح نیست

[yas1213]

سوال همینه!!
یعنی الگوریتم مرتب سازی جایگذاری یا همون درجی بنویسیم و عنصر xرا با استفاده از جست و جوی دودویی در جای مورد نظر جایگذاری کنیم!

[pesar irooni]

منظورتون رو فهمیدم
براتون دو تا مطلب آپلود کردم که در این مورده. اونی که فارسیه گفته این کار نه تنها باعث بهبود زمان اجرا نمیشه بلکه ثابت اون رو بالا میبره ولی اونی که زبون اصلیه عکسش رو گفته به نظرم استدلالش بهتره.

[manager]

pesar irooni جان این دامینی که روش آپ کردی فیلتر شده... تو همین جا ضمیمه کن بی زحمت..

[pesar irooni]

جناب manager اینکه فیلتر نشده. هنوز کار میکنه. ضمنا شرمنده من نمیدونستم این سایت فضا هم بهمون میده.
جناب yas من وقت نکردم استدلالاش رو چک کنم. اگه خوندی بگو با نظر کدوم مولف موافقی. ایرانیه یا خارجیه؟

[yas1213]

جناب پسر ایروونی هر دو رو خوندم هر دو یه چیزیو میگن
هر دو میگن پیچیدگی زمانی در مرتب سازی با جست و جوی دودویی بیشتر میشه تو نمودارشم مشخصه!
بازم ممنون!

[pesar irooni]

:متعجب:من هم دفعه پیش و هم الان قسمت conclusion مولف خارجی رو خوندم. گفته که زمان جستجو خیلی بهتر شده. ممکنه دوباره چک کنی!!!!!!!!!!!!!!!!!!!!!!

[yas1213]

راست میگییییا!!!
من اوون قسمتو نخونده بودم!نمودارشم میگهBinary insertion sort پیچیدگی زمانیش بهتره یعنیlog n ولی Quick sort & Heap sort
n log n هستن ولی تو فارسیش Binary insertion sort n^2 نوشته !!!
الگوریتم فارسیه مشخص نکرده position &Element چی هستن؟؟شما میدونی؟؟؟

[pesar irooni]

position جایی که الگوریتم جستجوی دودویی برای عنصرمون پیدا میکنه، یعنی همون جای اصلیش. و element هم خود عنصری که باید سرجاش در یک گذر قرار بگیره. مثلا اگه آرایه تا الان بصورت 1,2,5,8,10 مرتب باشه و عنصر بعدی که قراره سرجاش قرار بگیره و الان در موقعیت 6 قرار داشته باشه و عدد 7 هم باشه، position ما عدد 4 میشه (یعنی مکان عدد 7 تو آرایه تا اینجا) و element ما هم همون عدد 7 میشه.

[pesar irooni]

position جایی که الگوریتم جستجوی دودویی برای عنصرمون پیدا میکنه، یعنی همون جای اصلیش. و element هم خود عنصری که باید سرجاش در یک گذر قرار بگیره. مثلا اگه آرایه تا الان بصورت 1,2,5,8,10 مرتب باشه و عنصر بعدی که قراره سرجاش قرار بگیره و الان در موقعیت 6 قرار داشته باشه و عدد 7 هم باشه، position ما عدد 4 میشه (یعنی مکان عدد 7 تو آرایه تا اینجا) و element ما هم همون عدد 7 میشه.

[yas1213]

اها!
برنامه فارسیه با اوون یکی فرق داره!!!
فارسیه Quick sort!
اوون یکی binery insertion sort!

[pesar irooni]

اما من فارسیه رو توضیح دادم. جفتشون binary insertion sort رو دارند.:متفکر:

[yas1213]

درالگوریتم فارسیه ارایه مرتبه یه عنصر x تو این ارایه مرتب میذاره!!
ولی اوون یکی ارایرو مرتب میکنه!یعنی اولش نا مرتبه!برای همین binary insertion sort میگن بهش!

[pesar irooni]

خوب قسمت مرتب کردنش یکیه دیگه
فقط نوع درج کردن بجای ترتیبی شده دودویی

[yas1213]

این zip که جناب پسر ایرونی در صفحه اول همین تاپیک گذاشتن به اسم 680-678 سوال 6 فصل دوم به نظر من الگوریتمش ایراد داره میشه چک کنین د درستشو بذارین !
سوالش اینه که:
الگوریتمی که لیست مرتب شده ای از nعنصر را با تقسیم به سه لیست فرعی هر یک با حدود n/3عنصر جست و جو کند ولیست فرعی حاوی عنصر را یافته ان را به سه لیست فرعی تقسیم کند که اندازه انها تقریبا یکسان باشد و چنان ادامه یابد که عنصر را بیابد یا معلوم گردد که در لیست نیست.

[pesar irooni]

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

W(n) = W(n/3) + 6
چون در هر مرحله حلقه while شش مقایسه انجام میده که البته میتونه تا 4 مقایسه کاهش بده که نداده (چون نیازی به تعیین حد پایین نیست وقتی حد بالا معلوم شده)
اما در هر حال مشکل زیاد حادی نداره و فقط ضرایبش تو نماد O بیشتر میشه.
ضمنا من قبلا گفتم که این مقاله فارسیه زیاد معتبر نیست، دلیلش هم همون تحلیل binary insetion sort بود

[yas1213]

10 12 13 14 18 20 25 27 30 35 40 45 47 50 51 از راست به چپ
اگه ارایه 15 عنصری داشته باشیم و عنصر مورد نظر ما مکان 13 باشه عنصر 47
mid1=5 و mid2=10 میشه بعدش از شرط یکی مونده به اخر استفاده می کنیم low=11 وmid1=9وmid2=18
اخه عنصر 18 نداریم که!!!!!!

[pesar irooni]

کاملا حق با شماست و این الگوریتم پر از اشکاله و برای تعداد عناصر مضارب 3 کار میکنه. ضمنا وقتی low=11 شده دیگه نباید mid1=9 بشه چون اصلا فایده ای نداره. احتمالا نویسنده نمیدونسته که باید (با یه کم ارفاغ نسبت به نقاط مرزی) اینطوری مینوشت :

mid1 = low + (high-low)/3
mid2 = low + 2*(high-low)/3
در اصل برای binary search هم همینه یعنی

mid = low + (high-low)/2
و اما با کمک ریاضیات به فرمول متعارف الگوریتمها میرسیم:

mid = low + high/2 - low/2 = low/2 + high/2 = (high+low)/2