موضوع مقاله: مرتب‌سازی مجاور-نگاشت | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مرتب‌سازی مجاور-نگاشت | مقدمه: چپ|قاب| در مرتب‌سازی سطلی بعد از پر شدن تمام سطل‌ها، عناصرِ هر سطل مرتب می‌شوند اما در این نوع مرتب‌سازی، درجِ یک عنصر در سطل به روش درج در مرتب‌سازی درجی انجام می‌شود. | ## بخش 1: مرتب‌سازی مجاور-نگاشت | (عنصر در دستهٔ مرتب شده قرار می‌گیرد) مرتب‌سازی مجاور-نگاشت (به انگلیسی: ProxmapSort) یک نوع الگوریتم مرتب‌سازی است که با دسته‌بندی آرایه ای از داده‌ها یا کلیدها به چند «زیر آرایه» (که در مرتب‌سازی سطلی، سطل نامیده می‌شوند) انجام می‌شود. با یک «مجاورت نگاشتی» که برای هر کلید K شروع زیر آرایه (سطل) را نشان می‌دهد به طوری که K در ترتیب مرتب نهایی قرار گیرد. اگر کلیدها بین زیر آرایه‌ها «خوب توزیع شده» باشند، مرتب‌سازی در زمان خطی رخ می‌دهد. پس از اتمام مرتب‌سازی مجاور-نگاشت، در صورتی که کلیدها خوب توزیع شده باشند، جستجوی مجاور-نگاشت می‌تواند کلید را در پیدا کند. این دو الگوریتم در اواخر دهه ۱۹۸۰ توسط پروفسور توماس در دانشگاه کالیفرنیا، ارواین اختراع شد. پارتیشن: با استفاده از یک تابع MapKey با دقت انتخاب شده، A2 را با استفاده از کلیدها در A در زیرزمینها تقسیم کنید پراکندگی: بیش از A را بخوانید، و هر کلید را در سطل A2 خود قرار دهید. مرتب‌سازی درج در صورت لزوم جمع‌آوری: از زیر زمین‌ها به ترتیب بازدید کنید و تمام عناصر را به آرایه اصلی برگردانید، یا به سادگی از A2 استفاده کنید. توجه: «کلیدها» همچنین ممکن است شامل داده‌های دیگری باشد، به عنوان مثال آرایه ای از اشیاء دانشجویی که شامل کلید به علاوه شناسه و نام دانشجو می‌باشد. | ## بخش 2: مرتب‌سازی مجاور-نگاشت | + میز آرایه A1 ۶٫۷ ۵٫۹ ۸٫۴ ۱٫۲ ۷٫۳ ۳٫۷ ۱۱٫۵ ۱٫۱ ۴٫۸ ۰٫۴ ۱۰٫۵ ۶٫۱ ۱٫۸H ۱ ۳ ۰ ۱ ۱ ۱ ۲ ۱ ۱ ۰ ۱ ۱ P ۰ ۱ -۹ ۴ ۵ ۶ ۷ ۹ ۱۰ -۹ ۱۱ ۱۲ L ۷ ۶ ۱۰ ۱ ۹ ۴ ۱۲ ۱ ۵ ۰ ۱۱ ۷ ۱ A2 ۰٫۴ ۱٫۱ ۱٫۲ ۱٫۸ ۳٫۷ ۴٫۸ ۵٫۹ ۶٫۱ ۶٫۷ ۷٫۳ ۸٫۴ ۱۰٫۵ ۱۱٫۵ نمایشی از ProxMapSort، یک نوع مرتب‌سازی سطل که از آرایه‌های موازی واسطه ای استفاده می‌کند تا به‌طور مؤثر نشانگرها و اندازه‌های بزرگترهای خود را نشان دهد. به عنوان مثال، کف (K) به سادگی به عنوان تعداد زیر قطعه به عنوان تعداد صحیح از داده‌ها در A اختصاص می‌دهد. از توابع مختلف می‌توان برای ترجمه طیف وسیعی از عناصر در A به زیرزمینها، از جمله تبدیل حروف A-Z به ۰–۲۵ یا بازگشت شخصیت اول (۰–۲۵۵) برای مرتب‌سازی رشته‌ها استفاده کرد. زیر بخش‌ها به محض ورود داده‌ها طبقه‌بندی می‌شوند، نه بعد از قرار دادن تمام داده‌ها در زیرزمین، همان‌طور که در مرتب‌سازی سطل معمولی است. اگر کلید پیدا شد، آن را بازگردانید (و اطلاعات مرتبط) اگر مقدار بیشتری از کلید پیدا کنید، کلید در مجموعه داده‌ها نیست محاسبه P [MapKey (k طول می‌کشد زمان. اگر در هنگام مرتب‌سازی از یک کلید نقشه که توزیع خوبی از کلیدها دارد استفاده می‌شد، هر زیرانداز در بالا با یک c ثابت محدود می‌شود، بنابراین در بیشتر c مقایسه‌ها برای یافتن کلید یا دانستن وجود آن لازم است؛ بنابراین ProxmapSearch است . هر یک با یک گذر از یک آرایه محاسبه می‌شود، با زمان ثابت صرف شده در هر مکان آرایه. بدترین حالت: MapKey همه موارد را در یک زیرسطح قرار می‌دهد، و در نتیجه مرتب‌سازی استاندارد و زمان زمان‌بندی درج می‌شود . | ## بخش 3: مرتب‌سازی مجاور-نگاشت | بهترین مورد: MapKey تعداد کمی از موارد مشابه را به ترتیب به جایی می‌دهد که بهترین مورد درج درج است. (زمان واقعی می‌تواند بسیار بهتر باشد، زیرا موارد c تا زمانی که آخرین مورد در سطل قرار نگیرد مرتب نشده‌اند). اگر بخاطر داشته باشید که مقادیر A تاکنون مرتب شده‌اند، و داده‌ها می‌توانند به جای استفاده از A2، مرتب شوند. سرعت آن را می‌توان به این که نمی مبتنی بر مقایسه و با استفاده از آرایه به جای اشیاء پویا اختصاص داده و اشاره گر است که باید دنبال شود، مانند این است که با زمانی که با استفاده از یک انجام منسوب درخت جستجوی دودویی. اگر نیازی به به روزرسانی داده‌ها نباشد، زمان دسترسی ممکن است این عملکرد را نسبت به سایر انواع مبتنی بر مرتب‌سازی غیر مقایسه مقایسه کند. نوع سطل عمومی مربوط به مرتب‌سازی پروکس-مپ مانند ProxmapSort، سطل مرتب کردن بر اساس به‌طور کلی در یک لیست از n ورودی عددی بین صفر و برخی از کلید حداکثر یا ارزش M و تقسیم وسیعی ارزش به n سطل هر یک از اندازه M / N عمل می‌کند. | ## جمع‌بندی | ] با این حال، عملکرد این نوع تنزل با خوشه (یا بیش از حد چند سطل با بیش از حد بسیاری از کلیدهای)؛ اگر بسیاری از مقادیر در نزدیکی اتفاق بیفتد، همه در یک سطل واحد قرار می‌گیرند و عملکرد به شدت کاهش می‌یابد.