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

مرتب‌سازی پرچم آمریکا نوع دیگر الگوریتم مؤثر و درجا از مرتب‌سازی پایه‌ای است که آیتم‌ها را درون صدها سطل توزیع می‌کند. از الگوریتم‌های مرتب‌سازی غیرمقایسه‌ای مانند مرتب‌سازی پایه‌ای و مرتب‌سازی پرچم آمریکا معمولاً برای مرتب کردن اشیای بزرگ مانند رشته‌ها استفاده می‌شود که در آن‌ها مقایسه عمل واحد زمان نیست. مرتب‌سازی پرچم آمریکا میان بیت‌های شی تکرار شده که برای هر شی در هر زمان چندین بیت را در نظر می‌گیرد. مرتب‌سازی پرچم آمریکا برای هر مجموعه از بیت‌ها دو بار آرایهٔ اشیا را مرور می‌کند: اول برای شمارش تعداد اشیایی که در هر سطل قرار می‌گیرد، و دوم برای قرار دادن شی در سطل خودش. این روش مخصوصاً زمانی مؤثر واقع می‌شود که با استفاده از ۲۵۶ سطل یک بایت در یک زمان مرتب شود. این روش با برخی بهینه‌سازی‌ها برای مجموعه‌های بزرگی از رشته‌ها دو برابر سریع‌تر از مرتب‌سازی سریع است.

نام این روش از قیاس با مسئله پرچم ملی هلند در گام آخر می‌آید: افراز مؤثر آرایه به تعداد زیادی «راه راه».

به طور کلی الگوریتم‌های مرتب‌سازی لیستی از اشیا را با توجه به طرح مرتب‌سازی، مرتب می‌کنند. در مقابل الگوریتم‌های مرتب‌سازی بر اساس مقایسه، مانند مرتب‌سازی سریع، مرتب‌سازی پرچم آمریکا تنها قادر به مرتب‌سازی اعداد صحیح است (یا اشیایی که بتوان آن‌ها را به منزلهٔ اعداد صحیح تفسیر کرد). الگوریتم‌های مرتب‌سازی درجا، ازجمله مرتب‌سازی پرچم آمریکا، بدون تخصیص مقادیر قابل توجهی حافظه که فراتر از مقدار استفاده شده توسط آرایهٔ اصلی باشد، اجرا می‌شوند. این موضوع مزیت مهمی در صرفه‌جویی در حافظه و زمان کپی کردن آرایه است.

مرتب‌سازی پرچم آمریکا با تقسیم پیاپی لیستی از اشیا به سطل‌ها بر اساس اولین رقم نمایش پایه N آن‌هاست (پایه‌ای که استفاده می‌شود به عنوان مبنا ذکر می‌شود). اگر N برابر ۲ باشد، می‌توان هر شی را با استفاده از الگوریتم پرچم ملی هلند در سطل درست قرار داد. وقتی N بزرگتر باشد، اشیا نمی‌توانند بلافاصله در جایگاه قرار گیرند، زیرا مشخص نیست که هر سطل کجا شروع و به کجا ختم می‌شود. مرتب‌سازی پرچم آمریکا با دو بار مرور کردن آرایه این مشکل را حل می‌کند. بار اول تعداد اشیایی را که در هر یک از N سطل قرار می‌گیرند شمرده و سپس با مجموع مقدار سطل‌های قبلی، ابتدا و انتهای هر سطل در آرایه اصلی محاسبه می‌شود. در مرحله دوم هر شی به مکان درستش جابه‌جا می‌شود.

این روش زمانی بهترین عملکرد را دارد که مبنای آن توانی از دو باشد. زیرا می‌توان برای محاسبه مقدار هر رقم به جای عملگر هزینه‌بر به توان رساندن از عملگرهای شیفت بیت استفاده کرد. معمولاً هنگام مرتب‌سازی رشته‌ها با کدگذاری‌های ۷ یا ۸ بیتی مانند اسکی از مبنای ۲۵۶ یا ۱۲۸ استفاده می‌شود که سبب مرتب‌سازی کاراکتر به کاراکتر می‌شود.

  american_flag_sort(Array, Radix)     for each digit D:       # first pass: compute counts       Counts <- zeros(Radix)       for object X in Array:         Counts[digit D of object X in base Radix] += 1       # compute bucket offsets       Offsets <- [ sum(Counts[0..i]) for i in 1..Radix]       # swap objects into place       for object X in Array:         swap X to the bucket starting at Offsets[digit D of X in base Radix]       for each Bucket:         american_flag_sort(Bucket, Radix) 

مثال زیر که به زبان برنامه‌نویسی پایتون نوشته شده است مرتب‌سازی پرچم آمریکا را برای هر مبنایی از دو یا بزرگتر از آن انجام می‌دهد. در این‌جا بیان ساده به برنامه‌نویسی هوشمندانه ارجحیت داده شده است و بنابراین به جای تکنیک‌های شیفت بیت از تابع لگاریتم استفاده شده است.

  def get_radix_val(x, digit, radix):       return int(floor(x / radix**digit)) % radix   def compute_offsets(a_list, start, end, digit, radix):       counts = [0 for _ in range(radix)]       for i in range(start, end):           val = get_radix_val(a_list[i], digit, radix)           counts[val] += 1       offsets = [0 for _ in range(radix)]       sum = 0       for i in range(radix):           offsets[i] = sum           sum += counts[i]       return offsets   def swap(a_list, offsets, start, end, digit, radix):       i = start       next_free = copy(offsets)       cur_block = 0       while cur_block <radix-1:           if i>= start + offsets[cur_block+1]:               cur_block += 1               continue           radix_val = get_radix_val(a_list[i], digit, radix)           if radix_val == cur_block:               i += 1               continue           swap_to = next_free[radix_val]           a_list[i], a_list[swap_to] = a_list[swap_to], a_list[i]           next_free[radix_val] += 1   def american_flag_sort_helper(a_list, start, end, digit, radix):       offsets = compute_offsets(a_list, start, end, digit, radix)       swap(a_list, offsets, start, end, digit, radix)       if digit == 0:           return       for i in range(len(offsets)-1):           american_flag_sort_helper(a_list, offsets[i], offsets[i+1], digit-1, radix)   def american_flag_sort(a_list, radix):       for x in a_list:           assert(type(x) == int)       max_val = max(a_list)       max_digit = int(floor(log(max_val, radix)))       american_flag_sort_helper(a_list, 0, len(a_list), max_digit, radix)