مرتب سازی مجاور - نگاشت ( به انگلیسی: ProxmapSort ) یک نوع الگوریتم مرتب سازی است که با دسته بندی آرایه ای از داده ها یا کلیدها به چند «زیر آرایه» ( که در مرتب سازی سطلی، سطل نامیده می شوند ) انجام می شود.
ریشهٔ نام این الگوریتم از «مجاورت» و «نگاشت» می آید. با یک «مجاورت نگاشتی» که برای هر کلید K شروع زیر آرایه ( سطل ) را نشان می دهد به طوری که K در ترتیب مرتب نهایی قرار گیرد. کلیدها با استفاده از روش مشابه در مرتب سازی درجی در هر سطل درج می شوند.
اگر کلیدها بین زیر آرایه ها «خوب توزیع شده» باشند، مرتب سازی در زمان خطی رخ می دهد.
می توان گفت این الگوریتم ترکیبی از مرتب سازی سطلی و مبنایی است.
پس از اتمام مرتب سازی مجاور - نگاشت، در صورتی که کلیدها خوب توزیع شده باشند، جستجوی مجاور - نگاشت می تواند کلید را در O ( 1 ) پیدا کند.
این دو الگوریتم در اواخر دهه ۱۹۸۰ توسط پروفسور توماس در دانشگاه کالیفرنیا، ارواین اختراع شد.
فرض کنید آرایه A با n تا کلید داده شده است:
• Initialize: 2 آرایه با اندازه n: hitCount , proxMap و ۲ آرایه A . l طول: مکان و A2 را ایجاد و اولیه کنید.
• پارتیشن: با استفاده از یک تابع MapKey با دقت انتخاب شده، A2 را با استفاده از کلیدها در A در زیرزمینها تقسیم کنید
• پراکندگی: بیش از A را بخوانید، و هر کلید را در سطل A2 خود قرار دهید. مرتب سازی درج در صورت لزوم
• جمع آوری: از زیر زمین ها به ترتیب بازدید کنید و تمام عناصر را به آرایه اصلی برگردانید، یا به سادگی از A2 استفاده کنید.
توجه: «کلیدها» همچنین ممکن است شامل داده های دیگری باشد، به عنوان مثال آرایه ای از اشیاء دانشجویی که شامل کلید به علاوه شناسه و نام دانشجو می باشد. این امر باعث می شود ProxMapSort برای سازماندهی گروه های اشیاء، نه فقط خود کلیدها، مناسب باشد.
یک آرایه کامل را در نظر بگیرید: A با کلید N. بگذارید من یک فهرست از کلیدهای A. طبقه بندی A در آرایه A2 با اندازه مساوی باشم.
عملکرد کلید نقشه به صورت MapKey ( کلید ) = طبقه ( K ) تعریف شده است.
// compute hit counts for i = 0 to 11 // where 11 is n { H = 0; } for i = 0 to 12 // where 12 is A. length { pos = MapKey ( A ) ; H = H + 1; } runningTotal = 0; // compute prox map – location of start of each subarray for i = 0 to 11 if H = 0 P = - 9; else P = runningTotal; runningTotal = runningTotal + H; for i = 0 to 12 // compute location – subarray – in A2 into which each item in A is to be placed L = P; for I = 0 to 12; // sort items A2 = < empty> ; for i = 0 to 12 // insert each item into subarray beginning at start, preserving order { start = L; // subarray for this item begins at this location insertion made = false; for j = start to ( ! e end of A2 is found, and insertion not made | ) { if A2 == < empty> // if subarray empty, just put item in first position of subarray A2 = A; insertion made = true; else if A < A2 // key belongs at A2 int end = j + 1; // find end of used part of subarray – where first < empty> is while ( A2 != < empty> ) end++; for k = end - 1 to j // move larger keys to the right 1 cell A2 = A2; A2 = A; insertion made = true; // add in new key } } در اینجا یک آرایه به مرتب است و توابع mapKey تعیین تعداد subarrays استفاده کنید. به عنوان مثال، کف ( K ) به سادگی به عنوان تعداد زیر قطعه به عنوان تعداد صحیح از داده ها در A اختصاص می دهد. تقسیم کلید به طور ثابت باعث می شود تعداد زیردریایی ها کاهش یابد. از توابع مختلف می توان برای ترجمه طیف وسیعی از عناصر در A به زیرزمینها، از جمله تبدیل حروف A - Z به ۰–۲۵ یا بازگشت شخصیت اول ( ۰–۲۵۵ ) برای مرتب سازی رشته ها استفاده کرد. زیر بخش ها به محض ورود داده ها طبقه بندی می شوند، نه بعد از قرار دادن تمام داده ها در زیرزمین، همان طور که در مرتب سازی سطل معمولی است.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفریشهٔ نام این الگوریتم از «مجاورت» و «نگاشت» می آید. با یک «مجاورت نگاشتی» که برای هر کلید K شروع زیر آرایه ( سطل ) را نشان می دهد به طوری که K در ترتیب مرتب نهایی قرار گیرد. کلیدها با استفاده از روش مشابه در مرتب سازی درجی در هر سطل درج می شوند.
اگر کلیدها بین زیر آرایه ها «خوب توزیع شده» باشند، مرتب سازی در زمان خطی رخ می دهد.
می توان گفت این الگوریتم ترکیبی از مرتب سازی سطلی و مبنایی است.
پس از اتمام مرتب سازی مجاور - نگاشت، در صورتی که کلیدها خوب توزیع شده باشند، جستجوی مجاور - نگاشت می تواند کلید را در O ( 1 ) پیدا کند.
این دو الگوریتم در اواخر دهه ۱۹۸۰ توسط پروفسور توماس در دانشگاه کالیفرنیا، ارواین اختراع شد.
فرض کنید آرایه A با n تا کلید داده شده است:
• Initialize: 2 آرایه با اندازه n: hitCount , proxMap و ۲ آرایه A . l طول: مکان و A2 را ایجاد و اولیه کنید.
• پارتیشن: با استفاده از یک تابع MapKey با دقت انتخاب شده، A2 را با استفاده از کلیدها در A در زیرزمینها تقسیم کنید
• پراکندگی: بیش از A را بخوانید، و هر کلید را در سطل A2 خود قرار دهید. مرتب سازی درج در صورت لزوم
• جمع آوری: از زیر زمین ها به ترتیب بازدید کنید و تمام عناصر را به آرایه اصلی برگردانید، یا به سادگی از A2 استفاده کنید.
توجه: «کلیدها» همچنین ممکن است شامل داده های دیگری باشد، به عنوان مثال آرایه ای از اشیاء دانشجویی که شامل کلید به علاوه شناسه و نام دانشجو می باشد. این امر باعث می شود ProxMapSort برای سازماندهی گروه های اشیاء، نه فقط خود کلیدها، مناسب باشد.
یک آرایه کامل را در نظر بگیرید: A با کلید N. بگذارید من یک فهرست از کلیدهای A. طبقه بندی A در آرایه A2 با اندازه مساوی باشم.
عملکرد کلید نقشه به صورت MapKey ( کلید ) = طبقه ( K ) تعریف شده است.
// compute hit counts for i = 0 to 11 // where 11 is n { H = 0; } for i = 0 to 12 // where 12 is A. length { pos = MapKey ( A ) ; H = H + 1; } runningTotal = 0; // compute prox map – location of start of each subarray for i = 0 to 11 if H = 0 P = - 9; else P = runningTotal; runningTotal = runningTotal + H; for i = 0 to 12 // compute location – subarray – in A2 into which each item in A is to be placed L = P; for I = 0 to 12; // sort items A2 = < empty> ; for i = 0 to 12 // insert each item into subarray beginning at start, preserving order { start = L; // subarray for this item begins at this location insertion made = false; for j = start to ( ! e end of A2 is found, and insertion not made | ) { if A2 == < empty> // if subarray empty, just put item in first position of subarray A2 = A; insertion made = true; else if A < A2 // key belongs at A2 int end = j + 1; // find end of used part of subarray – where first < empty> is while ( A2 != < empty> ) end++; for k = end - 1 to j // move larger keys to the right 1 cell A2 = A2; A2 = A; insertion made = true; // add in new key } } در اینجا یک آرایه به مرتب است و توابع mapKey تعیین تعداد subarrays استفاده کنید. به عنوان مثال، کف ( K ) به سادگی به عنوان تعداد زیر قطعه به عنوان تعداد صحیح از داده ها در A اختصاص می دهد. تقسیم کلید به طور ثابت باعث می شود تعداد زیردریایی ها کاهش یابد. از توابع مختلف می توان برای ترجمه طیف وسیعی از عناصر در A به زیرزمینها، از جمله تبدیل حروف A - Z به ۰–۲۵ یا بازگشت شخصیت اول ( ۰–۲۵۵ ) برای مرتب سازی رشته ها استفاده کرد. زیر بخش ها به محض ورود داده ها طبقه بندی می شوند، نه بعد از قرار دادن تمام داده ها در زیرزمین، همان طور که در مرتب سازی سطل معمولی است.
wiki: مرتب سازی مجاور نگاشت