مرتب‌سازی پرچم آمریکا
مرتب‌سازی پرچم آمریکا نوع دیگر الگوریتم مؤثر و درجا از مرتب‌سازی پایه‌ای است که آیتم‌ها را درون صدها سطل توزیع می‌کند. از الگوریتم‌های مرتب‌سازی غیرمقایسه‌ای مانند مرتب‌سازی پایه‌ای و مرتب‌سازی پرچم آمریکا معمولاً برای مرتب کردن اشیای بزرگ مانند رشته‌ها استفاده می‌شود که در آن‌ها مقایسه عمل واحد زمان نیست. مرتب‌سازی پرچم آمریکا میان بیت‌های شی تکرار شده که برای هر شی در هر زمان چندین بیت را در نظر می‌گیرد. مرتب‌سازی پرچم آمریکا برای هر مجموعه از بیت‌ها دو بار آرایهٔ اشیا را مرور می‌کند: اول برای شمارش تعداد اشیایی که در هر سطل قرار می‌گیرد، و دوم برای قرار دادن شی در سطل خودش. این روش مخصوصاً زمانی مؤثر واقع می‌شود که با استفاده از ۲۵۶ سطل یک بایت در یک زمان مرتب شود. این روش با برخی بهینه‌سازی‌ها برای مجموعه‌های بزرگی از رشته‌ها دو برابر سریع‌تر از مرتب‌سازی سریع است.
نام این روش از قیاس با مسئله پرچم ملی هلند در گام آخر می‌آید: افراز مؤثر آرایه به تعداد زیادی «راه راه».
الگوریتم
[ویرایش]به طور کلی الگوریتم‌های مرتب‌سازی لیستی از اشیا را با توجه به طرح مرتب‌سازی، مرتب می‌کنند. در مقابل الگوریتم‌های مرتب‌سازی بر اساس مقایسه، مانند مرتب‌سازی سریع، مرتب‌سازی پرچم آمریکا تنها قادر به مرتب‌سازی اعداد صحیح است (یا اشیایی که بتوان آن‌ها را به منزلهٔ اعداد صحیح تفسیر کرد). الگوریتم‌های مرتب‌سازی درجا، ازجمله مرتب‌سازی پرچم آمریکا، بدون تخصیص مقادیر قابل توجهی حافظه که فراتر از مقدار استفاده شده توسط آرایهٔ اصلی باشد، اجرا می‌شوند. این موضوع مزیت مهمی در صرفه‌جویی در حافظه و زمان کپی کردن آرایه است.
مرتب‌سازی پرچم آمریکا با تقسیم پیاپی لیستی از اشیا به سطل‌ها بر اساس اولین رقم نمایش پایه 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)
منابع
[ویرایش]پیوند به بیرون
[ویرایش]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).
| تئوری |  | |
|---|---|---|
| گونه‌های تعویضی | ||
| گونه‌های انتخابی | ||
| گونه‌های درجی | ||
| گونه‌های ادغامی | ||
| گونه‌های توزیعی | ||
| گونه‌های همرو | ||
| گونه‌های دوگانه | ||
| گونه‌های دیگر | ||