موضوع مقاله: مرتب‌سازی انفجاری | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مرتب‌سازی انفجاری | مقدمه: مرتب‌سازی انفجاری و گونه‌هایش الگوریتم‌های کارآمد در ذخیره‌گاه برای مرتب ساختن رشته‌ها هستند و از مرتب‌سازی سریع برای مجموعه بزرگی از داده‌ها سریع‌تر عمل می‌کنند. | ## بخش 1: مرتب‌سازی انفجاری | الگوریتم مرتب‌سازی انفجاری برای ذخیره کردن رشته‌ها از داده‌ساختار درخت پیشوندی انفجاری استفاده می‌کند. درخت پیشوندی انفجاری داده ساختاری است که جهت ذخیره رشته‌ها مورد استفاده قرار می‌گیرد. این داده ساختار از سه مؤلفه اصلی تشکیل شده‌است: رکوردها حاوی اطلاعاتی هستند که برنامه استفاده‌کننده از درخت پیشوندی انفجاری به آن احتیاج دارد؛ مانند محل قرار گرفتن رشته‌ها و همچنین اشاره‌گری جهت نگهداری ظرف‌هایی که آن رکورد را نگهداری می‌کنند. ظرف‌ها ظرف‌ها مجموعه کوچکی از رکوردها هستند که به صورت یک داده ساختار ساده مانند لیست یا درخت دودویی جستجو نگهداری می‌شوند. هر ظرف دارای یک سرآیند است که جهت ذخیره‌سازی آمار مورد استفاده قرار گرفته در عملیات انفجار مورد استفاده قرار می‌گیرند. هر گره از یک آرایه به طول از اشاره‌گرها که به یک گره دیگر یا یک ظرف اشاره می‌کنند، تشکیل شده‌است. عملیاتی که درخت پیشوندی انفجاری پشتیبانی می‌کند عبارتند از: جستجو جستجو در یک درخت پیشوندی انفجاری از دو گام مجزای زیر تشکیل شده‌است. ورودی این عملیات یک رشته حرفی و خروجی اشاره‌گری به یک رکورد یا در صورت جستجوی ناموفق اشاره‌گری به نال است. - گام اول: درخت پیشوندی دسترسی با توجه به حروف ابتدایی رشته مورد جستجو قرار گرفته طی می‌شود. | ## بخش 2: مرتب‌سازی انفجاری | شیء فعلی در مرحله اول برابر با ریشه درخت پیشوندی دسترسی و ارتفاع فعلی هم برابر با یک است. تا زمانی که شیء فعلی یکی از گره‌های درخت پیشوندی دسترسی است و ارتفاع کمتر از است: الف) شیء فعلی را برابر با گره یا ظرف اشاره شده توسط امین عنصر آرایه قرار داده می‌شود، ب) یکی زیاد می‌شود. اگر شیء فعلی گره درخت پیشوندی با ارتفاع بود، شیء فعلی برابر با شیء اشاره شده توسط اشاره‌گر تهی (که برای سادگی می‌تواند یک ظرف حاوی صفر یا یک رکورد در نظر گرفته‌شود) قرار داده می‌شود. در غیر اینصورت، اگر شیء فعلی نال بود این رشته در درخت پیشوندی انفجاری وجود ندارد و جستجو خاتمه می‌یابد. اگر ، از حروف باقی مانده جهت جستجو در ظرف استفاده می‌شود که در صورت پیدا شدن رکورد مربوطه، آن رکورد و در غیر اینصورت نال برگردانده می‌شود؛ وگرنه شیء فعلی برابر با یک ظرف حاوی صفر یا یک رکورد است که توسط یک اشاره‌گر تهی در دسترس قرار گرفته‌است. در انتها چون تمامی رشته در پیمایش درخت پیشوندی مورد استفاده قرار گرفته‌است، این اشاره‌گر برگردانده می‌شود. مثال برای مثال، جهت جستجوی عبارت "came" در درخت پیشوندی شکل زیر، ابتدا اشاره‌گر را از خانه 'C' گره ریشه تا گره بعدی درخت پیشوندی دنبال می‌کنیم. سپس از خانه 'A' به چپ‌ترین ظرف آن می‌رویم و در آنجا به دنبال زیررشته "me" می‌گردیم. ظرف‌های ما به شکل داده ساختار درخت دودویی جستجو هستند؛ بنابراین در این مرحله از الگوریتم جستجوی یک رشته در یک درخت دودویی جستجو استفاده می‌کنیم. | ## بخش 3: مرتب‌سازی انفجاری | - گام دوم: در غیر اینصورت اگر بود، از الگوریتم معمول درج در داده ساختار ظرفمان (که برای مثال می‌تواند درخت دودویی جستجو باشد) جهت درج رکورد مربوطه استفاده می‌کنیم. برای حذف یک رکورد، ابتدا باید آن را جستجو کنیم، بیابیم و با استفاده از روش معمول حذف در داده ساختار ظرفمان آن را از ظرف حذف کنیم. اگر حذف باعث خالی شدن یک ظرف شود، گره‌ای که پدر آن ظرف است باید به‌روزرسانی شود. در صورتی که گره هیچ بچه‌ای نداشته باشد، از درخت پیشوندی انفجاری حذف می‌شود و این عملیات می‌تواند به‌طور بازگشتی تا ریشه ادامه پیدا کند. انفجار به فرایند جایگزینی یک ظرف در عمق با یک گره از درخت پیشوندی و مجموعه‌ای از ظرف‌های جدید در عمق (که تمامی رکوردهای موجود در ظرف اصلی بین آن‌ها نگهداری می‌شود) انفجار گفته می‌شود. یک استراتژی موفق انفجار باید سریع پیدا شدن رشته‌های معمول بدون جستجوی اضافه در ظرف‌ها را تضمین کند. باید توجه داشت که ظرف‌هایی که به ندرت در دسترس قرار می‌گیرند نباید منفجر شوند، زیرا ظرف‌ها باید در قیاس با گره‌ها از فضای موجود بهره بیشتری ببرند. انفجار با پیمودن سه گام زیر انجام می‌شود: - گام اول: یک گره جدید در درخت پیشوندی دسترسی با نام ایجاد می‌شود و تمام اشاره‌گرهای آن به یک ظرف خالی اشاره می‌کنند. | ## جمع‌بندی | - گام دوم: برای هر رکورد در ظرف اصلی، الف) حرف اول آن رشته برداشته می‌شود، و ب) این رکورد به ظرفی که پوینتر گره b به آن اشاره می‌کند، اضافه می‌شود.