(۱۱ خرداد ۱۳۹۸ ۱۱:۰۷ ب.ظ)Jooybari نوشته شده توسط:  سلام. وقت بخیر.
این SQRT Sort که می‌فرمائید یه سوالیه که یک مرتبه تو کنکور اومده. روش حلش مثل همین هست ولی نیاز نیست که اونو بدونید. تو اون مثال گفته بود که یه روال داریم که به اندازه $\sqrt n$ عنصر رو مرتب می‌کنه. تو این سوال گفته k عضو رو مرتب می‌کنه.
بگذریم. برگردیم سر همین سوال. مرتب سازی حبابی رو بلدید؟ مرتب سازی حبابی یه حالت خاص از همین سوال به ازای k=2 هست. هر بار یه پنجره به طول ۲ درنظر می‌گیره و نصف طول پنجره، جلو میره. تعداد دفعاتی هم که باید حباب رو به انتها برسونیم برابر هست با n تقسیم بر اندازه گامی که جلو میریم. یعنی k/2 یا همون ۱/ پس مرتبه زمانیش میشه $O(n^2)$.
اینجا هم همین کارو انجام میدیم. پنجره به طول k میگیریم و هر بار به اندازه k/2 جلو میریم. تعداد دفعات انتقال حباب از اول به آخر هم میشه n تقسیم بر k/2. پس مرتبه زمانی در این حالت میشه $O(n^2/k^2)$.

بی نهایت ممنون از اینکه جواب دادین
فقط ببخشید شرمنده
ولی من یه سوال دارم
مرتب سازی حبابی را متوجه هستم چجوری کار میکنه
ولی ربطشو به k که گفتین نمیفهمم
مثلا اگر n=6 و k=2 باشه اونوقت طبق صورت سوال i از یک هست تا پنج
[A[1,2
[A[2,3
[A[3,4
[A[4,5
[A[5,6
که سایز پنجره را سایز این آرایه ها بدونیم
مگه اینجوری نیست که ما بار اول ۱ را با ۲ مقایسه میکنیم
بار دوم ۲ را با ۳
بار سوم ۳ را با ۴
.....
پس یعنی هر بار به اندازه پنجره جلو میریم نه نصف پنجره
میشه لطفا در مورد این قسمت توضیح بدین
خیلی خیلی خیلی خیلی خیلییییییی مممنون میشم
تشکرااااات ویژهههههههه
بازم ببخشید که سوال داشتم

---

(۱۲ خرداد ۱۳۹۸ ۱۲:۴۸ ق.ظ)Saman نوشته شده توسط:  

(11 خرداد ۱۳۹۸ ۰۶:۳۹ ب.ظ)Sanazzz نوشته شده توسط:  سلام
نماز روزه هاتون قبول باش
ممنون میشم کمک کنین
جوابش گزینه ۲
من دو جا خواندم در مورد این سوال گفتن مشابه هست با sqrt sort میشه لطفا در مورد sqrt sort توضیح بدین و بگین پیچیدگی زمانی اش چطوریه
خیلی خیلی خیلی ممنون میشم تشکرات ویژههههه

سلام
اگر k رو برابر n بگیری هر بار فقط با یک بار صدا زدن این پنجره kتایی کل آرایه رو مرتب کردی
یعنی فقط گزینه ۲ درسته.چون فقط ۲ هست که ۱ میشه.
یا روش دیگر این که :
توی مرتب سازی های معمولی ما هر بار با مقایسه دو عنصر یعنی k=2 یک آرایه رو مرتب میکنیم.تعدا مقایسه های ما از مرتبه تتا n به توان ۲ هستش
حالا گفته k رو دلخواه بگیر.
تعداد عناصری که داری n/k تا است
ما nتا رو در زمان nبه توان ۲ مرتب میکردیم
پس n/k رو هم در زمان n/k به توان ۲ میشه مرتب کرد
یعنی در کل

خیلی خیلی خیلیییییی ممنونم از اینکه جواب دادین
تشکراااات ویژهههههه

(۱۲ خرداد ۱۳۹۸ ۰۱:۳۷ ق.ظ)Sanazzz نوشته شده توسط:  

(11 خرداد ۱۳۹۸ ۱۱:۰۷ ب.ظ)Jooybari نوشته شده توسط:  سلام. وقت بخیر.
این SQRT Sort که می‌فرمائید یه سوالیه که یک مرتبه تو کنکور اومده. روش حلش مثل همین هست ولی نیاز نیست که اونو بدونید. تو اون مثال گفته بود که یه روال داریم که به اندازه $\sqrt n$ عنصر رو مرتب می‌کنه. تو این سوال گفته k عضو رو مرتب می‌کنه.
بگذریم. برگردیم سر همین سوال. مرتب سازی حبابی رو بلدید؟ مرتب سازی حبابی یه حالت خاص از همین سوال به ازای k=2 هست. هر بار یه پنجره به طول ۲ درنظر می‌گیره و نصف طول پنجره، جلو میره. تعداد دفعاتی هم که باید حباب رو به انتها برسونیم برابر هست با n تقسیم بر اندازه گامی که جلو میریم. یعنی k/2 یا همون ۱/ پس مرتبه زمانیش میشه $O(n^2)$.
اینجا هم همین کارو انجام میدیم. پنجره به طول k میگیریم و هر بار به اندازه k/2 جلو میریم. تعداد دفعات انتقال حباب از اول به آخر هم میشه n تقسیم بر k/2. پس مرتبه زمانی در این حالت میشه $O(n^2/k^2)$.

بی نهایت ممنون از اینکه جواب دادین
فقط ببخشید شرمنده
ولی من یه سوال دارم
مرتب سازی حبابی را متوجه هستم چجوری کار میکنه
ولی ربطشو به k که گفتین نمیفهمم
مثلا اگر n=6 و k=2 باشه اونوقت طبق صورت سوال i از یک هست تا پنج
[A[1,2
[A[2,3
[A[3,4
[A[4,5
[A[5,6
که سایز پنجره را سایز این آرایه ها بدونیم
مگه اینجوری نیست که ما بار اول ۱ را با ۲ مقایسه میکنیم
بار دوم ۲ را با ۳
بار سوم ۳ را با ۴
.....
پس یعنی هر بار به اندازه پنجره جلو میریم نه نصف پنجره
میشه لطفا در مورد این قسمت توضیح بدین
خیلی خیلی خیلی خیلی خیلییییییی مممنون میشم
تشکرااااات ویژهههههههه
بازم ببخشید که سوال داشتم

---

(۱۲ خرداد ۱۳۹۸ ۱۲:۴۸ ق.ظ)Saman نوشته شده توسط:  

(11 خرداد ۱۳۹۸ ۰۶:۳۹ ب.ظ)Sanazzz نوشته شده توسط:  سلام
نماز روزه هاتون قبول باش
ممنون میشم کمک کنین
جوابش گزینه ۲
من دو جا خواندم در مورد این سوال گفتن مشابه هست با sqrt sort میشه لطفا در مورد sqrt sort توضیح بدین و بگین پیچیدگی زمانی اش چطوریه
خیلی خیلی خیلی ممنون میشم تشکرات ویژههههه

سلام
اگر k رو برابر n بگیری هر بار فقط با یک بار صدا زدن این پنجره kتایی کل آرایه رو مرتب کردی
یعنی فقط گزینه ۲ درسته.چون فقط ۲ هست که ۱ میشه.
یا روش دیگر این که :
توی مرتب سازی های معمولی ما هر بار با مقایسه دو عنصر یعنی k=2 یک آرایه رو مرتب میکنیم.تعدا مقایسه های ما از مرتبه تتا n به توان ۲ هستش
حالا گفته k رو دلخواه بگیر.
تعداد عناصری که داری n/k تا است
ما nتا رو در زمان nبه توان ۲ مرتب میکردیم
پس n/k رو هم در زمان n/k به توان ۲ میشه مرتب کرد
یعنی در کل

خیلی خیلی خیلیییییی ممنونم از اینکه جواب دادین
تشکراااات ویژهههههه

سلام میشه یکم بیشتر توضیح بدید ؟ در مورد این سوال؟

(۱۱ خرداد ۱۳۹۸ ۰۶:۳۹ ب.ظ)Sanazzz نوشته شده توسط:  سلام
نماز روزه هاتون قبول باش
ممنون میشم کمک کنین
جوابش گزینه ۲
من دو جا خواندم در مورد این سوال گفتن مشابه هست با sqrt sort میشه لطفا در مورد sqrt sort توضیح بدین و بگین پیچیدگی زمانی اش چطوریه
خیلی خیلی خیلی ممنون میشم تشکرات ویژههههه

سلام
اگر k رو برابر n بگیری هر بار فقط با یک بار صدا زدن این پنجره kتایی کل آرایه رو مرتب کردی
یعنی فقط گزینه ۲ درسته.چون فقط ۲ هست که ۱ میشه.
یا روش دیگر این که :
توی مرتب سازی های معمولی ما هر بار با مقایسه دو عنصر یعنی k=2 یک آرایه رو مرتب میکنیم.تعدا مقایسه های ما از مرتبه تتا n به توان ۲ هستش
حالا گفته k رو دلخواه بگیر.
تعداد عناصری که داری n/k تا است
ما nتا رو در زمان nبه توان ۲ مرتب میکردیم
پس n/k رو هم در زمان n/k به توان ۲ میشه مرتب کرد
یعنی در کل

منظور آقای جویباری از نصف پنجره اون جابه جایی هستش که انجام میدی.
شما بار اول nتا جابه جایی داری، بار دوم n-1 تا و الی آخر . . . تا میرسی به ۱ پس در کل از مرتبه تتا n به توان ۲ جابه جایی دارید.

هر بار به اندازه پنجره جلو نمیریدکه
فرض کن شما ۱ رو با ۲ مقایسه کنید.(و فرض کن میخوای صعودی مرتب کنی)
به لیست زیر با اندیس های ۱ تا ۶ دقت کن و عناصری که داخلش گذاشته شدن
$1\: \: 2\: \: 3\: 4\: 5\: 6$
$11\: 9\: 8\: 5\: 6\: 0$
شما ۱ رو با مقدار ۱۱ با ۲ با مقدار ۹ مقایسه میکنید ،مقدار ۱۱ از ۹ بزرگتر هستش پس ۱۱ میره جلو تر .(یک جابه جایی) پس وقتی k=2 بود(دو مقایسه) شما k رو یکی جلو بردید
بار بعدی اندیس ۲ که حاوی ۱۱ هست رو با اندیس۳ مقایسه کن که حاوی ۸ هستش و الی آخر
یه حالتی شبیه لغزاندن پنجره به جلو داره

در نهایت این کار شما لیست رو مرتب کردی

(۱۲ خرداد ۱۳۹۸ ۱۲:۰۹ ب.ظ)Saman نوشته شده توسط:  منظور آقای جویباری از نصف پنجره اون جابه جایی هستش که انجام میدی.
شما بار اول nتا جابه جایی داری، بار دوم n-1 تا و الی آخر . . . تا میرسی به ۱ پس در کل از مرتبه تتا n به توان ۲ جابه جایی دارید.

هر بار به اندازه پنجره جلو نمیریدکه
فرض کن شما ۱ رو با ۲ مقایسه کنید.(و فرض کن میخوای صعودی مرتب کنی)
به لیست زیر با اندیس های ۱ تا ۶ دقت کن و عناصری که داخلش گذاشته شدن
$1\: \: 2\: \: 3\: 4\: 5\: 6$
$11\: 9\: 8\: 5\: 6\: 0$
شما ۱ رو با مقدار ۱۱ با ۲ با مقدار ۹ مقایسه میکنید ،مقدار ۱۱ از ۹ بزرگتر هستش پس ۱۱ میره جلو تر .(یک جابه جایی) پس وقتی k=2 بود(دو مقایسه) شما k رو یکی جلو بردید
بار بعدی اندیس ۲ که حاوی ۱۱ هست رو با اندیس۳ مقایسه کن که حاوی ۸ هستش و الی آخر
یه حالتی شبیه لغزاندن پنجره به جلو داره

در نهایت این کار شما لیست رو مرتب کردی

بی نهایت مممنونممممممم از اینکه جواب دادین
کاملا متوجه شدم
منظور از جابه جایی ،جابه جاشدن پنجره هست
که اگر سایز پنجره را دو بگیریم
هر بار به اندازه نصف پنجره جلو میره
فقط یه سوال دیگه هم پپیش اومد ببخشید شرمنده
الان طبق گفته شما تو حبابی اول n تا جابه جایی بعد n-1 بعد n-2 تا و الای آخر
که اینا مگه اینجوری نیست که هر کدوم تقسیم بر k/2
و تو حالت حبابی چون k برابر دو هست مخرجش میشه یک و فقط صورت حساب که میشه n به توان دو
حالا اگر همه اینا تقسیم بر k/2 هست میشه
یه مخرج مشترک میگیریم میشه k/2 بعد صورت و جمع میزنیم میشه n به توان دو تقسیم بر k/2
شرمنده میشه این قسمتشم توضیح بدین خیلی خیلی خیلییییی ممنون میشم
تشکراااات ویژههههه

(۱۱ خرداد ۱۳۹۸ ۱۱:۰۷ ب.ظ)Jooybari نوشته شده توسط:  سلام. وقت بخیر.
این SQRT Sort که می‌فرمائید یه سوالیه که یک مرتبه تو کنکور اومده. روش حلش مثل همین هست ولی نیاز نیست که اونو بدونید. تو اون مثال گفته بود که یه روال داریم که به اندازه $\sqrt n$ عنصر رو مرتب می‌کنه. تو این سوال گفته k عضو رو مرتب می‌کنه.
بگذریم. برگردیم سر همین سوال. مرتب سازی حبابی رو بلدید؟ مرتب سازی حبابی یه حالت خاص از همین سوال به ازای k=2 هست. هر بار یه پنجره به طول ۲ درنظر می‌گیره و نصف طول پنجره، جلو میره. تعداد دفعاتی هم که باید حباب رو به انتها برسونیم برابر هست با n تقسیم بر اندازه گامی که جلو میریم. یعنی k/2 یا همون ۱/ پس مرتبه زمانیش میشه $O(n^2)$.
اینجا هم همین کارو انجام میدیم. پنجره به طول k میگیریم و هر بار به اندازه k/2 جلو میریم. تعداد دفعات انتقال حباب از اول به آخر هم میشه n تقسیم بر k/2. پس مرتبه زمانی در این حالت میشه $O(n^2/k^2)$.

ممنون از پاسخ خوب شما. اما پست‌های دوستان رو که خوندم احساس کردم نیاز به توضیح بیشتری وجود داره ...

توضیح خودم را با یک سؤال پرورش می‌دهم:
چرا میزان لغزش را برابر k/2 در نظر گرفتیم؟

جواب:
با فرض مرتب‌سازی صعودی، در هر تکرار از این نوع مرتب‌سازی حبابی، اعداد بزرگ با پشت سر گذاشتن اعداد کوچکتر به سمت انتهای لیست حرکت می‌کنند. نکته‌ی مهم این است که در پایان هر تکرار، تعدادی از عناصر به جای اصلی خود در انتهای لیست می‌رسند و نیازی نیست در تکرارهای بعدی لحاظ شوند. پس تعداد این عناصر (بگیرید a) بر پیچیدگی زمانی این الگوریتم مؤثر است.

در واقع a برابر حداقل تعداد مدخل‌های مشترک بین جفت مرتب‌سازی‌های متوالی در یک تکرار است. به بیانی، a پهنای باند عبور بزرگ‌ترین اعداد به سمت جایگاه اصلی خودشان است. پس میزان لغزش (بگیرید b) بر مقدار a تأثیر می‌گزارد. در واقع، a = k - b که b عددی بین ۱ تا ۱ - k است.

چون در هر تکرار a-تا از عناصر کم می‌شود، O(n/a) تکرار داریم. پس اگر میزان لغزش را برابر ۱ بگیریم، کمترین تکرار را داریم اما این کار سبب می‌شود در هر تکرار O(n) مرتب‌سازی نیاز باشد. زیرا در هر تکرار O(n/b) مرتب‌سازی نیاز است. پس بزرگ بودن b هم به همان اندازه برای ما مهم است. در نتیجه بهتر است a = b باشد:
a = k - b
a + b = k
۲b = k
b = k/2