مرتب سازی انفجاری

مرتب سازی انفجاری ( به انگلیسی: Burstsort ) و گونه هایش الگوریتم های کارآمد در ذخیره گاه برای مرتب ساختن رشته ها هستند[ ۱] و از مرتب سازی سریع برای مجموعه بزرگی از داده ها سریع تر عمل می کنند. این الگوریتم نخستین بار در سال ۲۰۰۳ منتشر شد. [ ۲]
الگوریتم مرتب سازی انفجاری برای ذخیره کردن رشته ها از داده ساختار درخت پیشوندی انفجاری استفاده می کند.
داده ساختاری است که جهت ذخیره رشته ها مورد استفاده قرار می گیرد. این داده ساختار از سه مؤلفه[ ۳] اصلی تشکیل شده است:
• رکوردها ( به انگلیسی: Records )
حاوی اطلاعاتی هستند که برنامه استفاده کننده از درخت پیشوندی انفجاری به آن احتیاج دارد؛ مانند محل قرار گرفتن رشته ها و همچنین اشاره گری جهت نگهداری ظرف هایی که آن رکورد را نگهداری می کنند.
• ظرف ها ( به انگلیسی: Containers )
ظرف ها مجموعه کوچکی از رکوردها هستند که به صورت یک داده ساختار ساده مانند لیست یا درخت دودویی جستجو نگهداری می شوند. در یک ظرف به عمق k ، رشته ها دارای طول حداقل k هستند که k حرف ابتدایی آن ها یکسانند. هر ظرف دارای یک سرآیند است که جهت ذخیره سازی آمار مورد استفاده قرار گرفته در عملیات انفجار مورد استفاده قرار می گیرند.
• درخت پیشوندی دسترسی ( به انگلیسی: Access Trie )
یک درخت پیشوندی است که برگ های آن ظرف هستند. هر گره از یک آرایه p به طول | A | از اشاره گرها که به یک گره دیگر یا یک ظرف اشاره می کنند، تشکیل شده است.
عملیاتی که درخت پیشوندی انفجاری پشتیبانی می کند عبارتند از:
جستجو در یک درخت پیشوندی انفجاری از دو گام مجزای زیر[ ۴] تشکیل شده است. ورودی این عملیات یک رشته n حرفی c 1 . . . c n و خروجی اشاره گری به یک رکورد یا در صورت جستجوی ناموفق اشاره گری به نال است.
- گام اول:
درخت پیشوندی دسترسی با توجه به حروف ابتدایی رشته مورد جستجو قرار گرفته طی می شود. شیء فعلی در مرحله اول برابر با ریشه درخت پیشوندی دسترسی و ارتفاع فعلی هم برابر با یک است. تا زمانی که شیء فعلی یکی از گره های درخت پیشوندی دسترسی است و ارتفاع i کمتر از n است:
الف ) شیء فعلی را برابر با گره یا ظرف اشاره شده توسط c i امین عنصر آرایه p قرار داده می شود،
ب ) i یکی زیاد می شود.
اگر شیء فعلی گره درخت پیشوندی با ارتفاع i = n + 1 بود، شیء فعلی برابر با شیء اشاره شده توسط اشاره گر تهی ( که برای سادگی می تواند یک ظرف حاوی صفر یا یک رکورد در نظر گرفته شود ) قرار داده می شود. در غیر اینصورت، اگر شیء فعلی نال بود این رشته در درخت پیشوندی انفجاری وجود ندارد و جستجو خاتمه می یابد.