مرتب‌سازی گسترده

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علوم رایانه، مرتب‌سازی گسترده (به انگلیسی: Splaysort) یک الگوریتم انطباقی مقایسه‌ای بر مبنای ساختمان داده‌های درخت اسپلی است.[۱]

الگوریتم[ویرایش]

مراحل الگوریتم عبارت است از:

  1. مقداردهی اولیه کردن یک درخت اسپلی خالی
  2. برای هر آیتِم داده در ترتیب ورودی، آن را در درخت اسپلی قرار می‌دهد
  3. پیمایش درخت برای یافتن ترتیب داده

علاوه بر این، الگوریتم با استفاده از درخت اسپلی برای سرعت بخشیدن به هر عمل درج، ممکن است بعنوان شکلی از مرتب‌سازی درجی یا مرتب‌سازی درختی هم بنظر آید.

پانویس[ویرایش]

  1. Moffat, Alistair; Eddy, Gary; Petersson, Ola (July 1996), Splaysort: Fast, Versatile, Practical, Software Practice and Experience 26 (7): 781–797, doi:10.1002/(SICI)1097-024X(199607)26:7<781::AID-SPE35>3.3.CO;2-2 
  • مشارکت‌کنندگان ویکی‌پدیا، «Splaysort»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۱۳ اسفند ۱۳۹۲).