مرتب‌سازی پرچم آمریکا

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

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

الگوریتم

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

مرتب‌سازی پرچم آمریکا با تقسیم پیاپی لیستی از اشیا به سطل‌ها بر اساس اولین رقم نمایش پایه 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)

منابع

Engineering radix sort

American flag sort

پیوند به بیرون

Wikipedia contributors, "American flag sort," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/w/index.php?title=American_flag_sort&oldid=698868117 (accessed May 3, 2016).