جلسه دوم داده‌های حجیم (مرتب‌سازی)

در این مدل ترتیب دسترسی به داده‌ها خیلی مهم است. (اگر از قسمت قبل یادتان باشد برای خواندن تصادفی باید زمان متناسب با N مصرف کنیم در حالی که برای خواندن متوالی زمان متناسب با N/B که B یک عدد بزرگ است.)

صف: دو عمل این ساختمان داده اضافه کردن به ابتدا و حذف کردن از انتها است. پس هر کدام یک سری عمل خواندن/نوشتن متوالی است که زمان آن متناسب با میزان داده تقسیم بر B است. پس هر عمل push و pop زمان O(1/B) می‌برد.

پشته: مثل صف می‌شود گفت زمان O(1/B) می‌خواهد.

مرتب‌سازی با استفاده از صف:

ادغام:

کمتر از M/B صف مرتب‌شده داریم. آنها را به این صورت ادغام می‌کنیم که بلوک اول هر کدام را در حافظه‌ی اصلی می‌ریزیم. (چون تعداد لیست‌ها از M/B کمتر است در حافظه جا می‌شود). در هر بار انجام این کار یک بلوک از جواب به دست می‌آید (چون بلوک اول همه‌ی صف‌ها را داریم). آن را در یک صف جدید می‌ریزیم و همین کار را ادامه می‌دهیم. زمان این کار O(N/B) می‌شود.

تقسیم:

برای تقسیم کردن لیست (صف) به کمتر از M/B لیست نامرتب که عناصر هر لیست از لیست بعدی آن کمتر باشد با فرض اینکه مکان برش‌ها (برای حالت دو تایی میانه) را داشته باشیم. هر بلوک را تقسیم می‌کنیم و زمانی که بلوک مربوط به یک صف کامل شد I/O می‌زنیم تا آن را بنویسیم.

مرتب‌سازی ادغامی:

با استفاده از تابع ادغام می‌توانیم با شروع از لیست‌های M عضوی مرتب (چون این تعداد در حافظه جا می‌شود) و ادغام آنها به لیست مرتب شده برسیم. تعداد I/Oها به صورت یک تصاعد هندسی است که جمله‌ی اول آن N/M است (تعداد لیست‌های اولیه) و هر بار چون تعداد لیست‌ها تقسیم بر M/B می‌شود (ادغام می‌شوند)، بر این تعداد تقسیم می‌شود. (چون زمان ادغام متناسب با تعداد لیست‌ها است).

تعمیم مرتب‌سازی سریع:

مشابه قبل می‌شود این کار را انجام داد. فقط یک قسمت می‌ماند که پیدا کردن برش‌ها (مثل میانه) است. از همان الگوریتم میانه پیدا کردن در یک مجموعه استفاده می‌کنیم. اول میانه هر پنج تا عنصر متوالی را پیدا می‌کنیم و بعد یک لیست N/5 عنصری به دست می‌آید که به صورت بازگشتی میانه‌ی آن را حساب می‌کنیم. حالا که میانه را به دست آوردیم لیست‌ها را بر اساس آن دو قسمت می‌کنیم. و همین کار را به صورت بازگشتی ادامه می‌دهیم تا به تعداد برش مورد نیاز برسیم.

تحلیل پیدا کردن میانه (Selection):

؟؟؟

کران پایین مرتب‌سازی در مدل I/O:

باید بعد از یک I/O بگوید چقدر از N! حالت ورودی حذف می‌شوند و فرض کرده M عدد در حافظه است و با یک I/O حداکثر B عنصر خوانده/نوشته می‌شوند و بیشترین تعداد حالت‌هایی که این کار ایجاد می‌کند را حساب می‌کند. بعد تعداد کل حالت‌ها را بر این تقسیم می‌کند. چون به این بیشترین می‌شود رسید مشکلی پیش نمی‌آید. اما اگر نمی‌شد به نظرم باید این را هم حساب می‌کرد که آیا واقعاً می‌شود که چنین اتفاقی بیفتد یا نه. (پر بودن حافظه و ...)