سلسله‌مراتب داده
سلسله مراتب داده به سازماندهی منظم داده‌ها، معمولاً در قالب سلسله مراتبی اشاره دارد. سازماندهی داده شامل خاصیت‌ها، زمینه (فیلد)ها، سوابق (رکوردها)، پرونده (فایل)ها و غیره می‌باشد. این مفهوم نقطه شروعی است برای فهمیدن آنچه که داده‌ها را تشکیل می‌دهد و اینکه آیا داده‌ها دارای یک ساختار هستند یا خیر. به عنوان مثال، شخصی چگونه اطلاعاتی مانند «کارمند»، «نام»، «بخش»، «مارسی اسمیت»، «بخش فروش» و غیره را درک می‌کند با فرض اینکه همه آنها مرتبط هستند؟ یک راه برای درک آنها این است که این الفاظ را به عنوان اجزای کوچکتر یا بزرگتر در یک سلسله مراتب ببینید. ممکن است بگوییم مارسی اسمیت یکی از کارکنان بخش فروش است یا نمونه ای از یک کارمند در آن بخش. اطلاعاتی که ما می‌خواهیم دربارهٔ همه کارکنان مان، و نه تنها مارسی، ضبط کنیم، نام، شناسه، آدرس و غیره است.
مرتب‌سازی شل
به عنوان مثال برای مرتب‌سازی داده‌های { ۲ ۸ ۹ ۴ ۳ ۷ ۵ ۱ ۶ ۰ ۲ ۴ ۸ ۶ ۱ ۵ ۰ ۹ ۷ } با این روش، ابتدا داده‌ها در چند ستون (مثلاً در این جا در ۷ ستون) قرار داده می‌شود و سپس هر ستون به صورت مجزا مرتب می‌شود: در مرحله بعد: دنباله فاصله‌ها یک قسمت کامل از مرتب‌سازی شِل می‌باشد. هر دنباله افزایشی ای می‌تواند در آن مورد استفاده قرار بگیرد به شرطی که آخرین عنصر افزاینده آن ۱ باشد. الگوریتم با انجام یک مرتب‌سازی درجی فاصله‌ای شروع به کار می‌کند که فاصله در آن اولین عدد موجود در دنباله فاصله‌ها می‌باشد. سپس با انجام مرتب‌سازی درجی فاصله‌ای با استفاده از هر عدد موجود در دنبالهٔ فاصله‌ها به کار خود ادامه می‌دهد تا آنجا که فاصله به مقدار ۱ برسد. وقتی که مقدار فاصله ۱ باشد مرتب‌سازی فاصله‌ای به سادگی یک مرتب‌سازی درجی معمولی است که ضمانت می‌کند که لیست نهایی مرتب شده‌است. دنباله فاصله‌ای اصلی که توسط خود دونالد شِل پیشنهاد شد از formula_2 شروع می‌شود و همین طور آنقدر عدد را نصف می‌کند تا به ۱ برسد. این دنباله کارایی فوق‌العاده‌ای برای الگوریتم‌های چهارتایی مثل مرتب‌سازی درجی فراهم می‌کند، ولی به کمی تغییر می‌توان زمان اجرای متوسط و بدترین حالت آن را باز هم بهبود بخشید. درکتاب مرجع وایس (Weiss) نشان داده شده‌است که اگر داده اولیه یک آرایه به صورت {کوچک اول، بزرگ اول، کوچک دوم، بزرگ دوم و...} باشد که در آن نیمهٔ بالایی اعداد در موقعیت مرتب شده در خانه‌های زوج و نیمهٔ پایینی اعداد به همین صورت در خانه‌های فرد قرار گرفته باشند، این دنباله یک مرتب‌سازی با بدترین زمان اجرای formula_3 را تولید خواهد کرد. شاید مهم‌ترین ویژگی مرتب‌سازی شِل این باشد که حتی با کم و کم تر شدن فاصله‌ها عناصر به صورت k- مرتب شده باقی می‌مانند. برای مثال اگر لیستی در ابتدا ۵- مرتب شده باشد و آن را ۳- مرتب‌سازی کنیم آنگاه لیست نه تنها ۳- مرتب شده‌است، بلکه ۳ و ۵- مرتب شده نیز می‌باشد. اگر این درست نبود الگوریتم عملیاتی که در تکرارهای قبلی انجام داده‌است را خنثی می‌کند و دوباره از اول شروع به کار می‌کند و چنین زمان اجرای پایینی نخواهد داشت. بسته به نوع دنباله فاصله انتخاب شده، ثابت شده‌است که مرتب‌سازی شِل دارای بدترین زمان اجرایformula_3 (با استفاده از افزاینده‌های شِل که ۱/۲ اندازه آرایه هستند و هر بار نصف می‌شوند)، formula_5 (با استفاده از افزاینده‌های هیباردِ formula_6)، formula_7 (با استفاده از افزاینده‌های سِدگِویکِ formula_8 یاformula_9)، یا formula_10 (با استفاده از افزاینده‌های پرَتِ formula_11)، و احتمالاً زمان‌های اجرای بهتر و اثبات نشده‌ای، می‌باشد. همچنین توسط پونن (Poonen)، پلکستون(Plaxton) و سوئل(Suel) اثبات شد که بدترین حالت مرتب‌سازی شِل به صورت formula_12 وجود ندارد. بهترین دنباله با استناد به تحقیقات Marcin Ciura دنبالهٔ codice_5 می‌باشد. این تحقیقات همچنین نتیجه می‌دهند که در مرتب‌سازی شِل مقایسه‌ها، به جای جابجایی، باید عملکرد غالب در نظر گرفته شوند. مرتب‌سازی شِل با استفاده از این دنباله از مرتب‌سازی درجی، یا هیپ سریع تر اجرا می‌شود و با این حال که در آرایه‌های کوچک، از مرتب‌سازی‌سازی سریع نیز سریع تر عمل می‌کند، در آرایه‌های به قدر کافی بزرگ از آن باز می‌ماند. بعد از ۱۷۵۰ در دنباله بالا، فاصله‌هایی با پیشروی هندسی می‌توانند مورد استفاده قرار بگیرند. مثل: nextgap = round(gap * ۲٫۲) یک دنبالهٔ دیگر که به صورت تجربی بهتر عمل می‌کند دنبالهٔ اعداد فیبوناچی (بدون یکی از ۱های اولیه) دو بار به توان عدد طلایی است، که دنبالهٔ زیر را ناشی می‌شود: