Америчка застава сортирање

Америчка застава сортирање (енгл. American flag sort) је ефикасна варијанта радикс сортирања која дистрибуира елементе у стотине сегмената. Неупоредни алгоритми за сортирање као што су радиx сорт и америцан флаг сорт се обично користе за сортирање великих објеката као што су стрингови, за које поредјење није јединица – време рада. Америчка застава сортирање пролази кроз битове објеката, с обзиром на неколико битова сваког објекта у исто време. За сваки скуп битова, америцан флаг има два пролаза кроз низ објеката: прво да преброји број објеката који ће пасти у сваку канту, а други да смести сваки објекат у његову канту. Ово ради добро, посебно када се сортирају бајтови користећи истовремено 256 канти. Са неким оптимизацијама, два пута је бржи од квиксорт за велике низове стрингова.

Име потиче по аналогија са холандским националним проблемом у вези заставе у последњем кораку: ефикасна подела низа у многим „врстама“ (пругама).

Алгоритам

Алгоритам за сортирање у општем случају сортира низ објеката према некој нарученој шеми. Насупрот алгоритмима за сортирање који су засновани на поређењу, као што је квиксорт, сортирање америчке заставе може само сортирати целе бројеве (интегерс) (или објекте који се могу тумачити као цели бројеви). Алгоритми за сортирање у месту, укључујући и америцан флаг сорт, раде без издвајања значајне количине меморије, уместо тога користе оригинални низ. Ово је значајна предност, и у уштеди меморије и времена за копирање низа.

Америчка застава сортирање, успешто ради дељењем низа објеката у сегменте на основу прве цифре њихове базе – Н репрезентације (база која се користи назива се радиx). Када је Н 2, сваки објекат може бити замењен одговарајућим сегментом, користеци алгоритам холандке националне заставе. Међутим, када је Н веће , објекти не могу одмах бити замењени на своје место, због тога што није познато где сваки сегмент треба да поцне и да се заврши. Америцан флаг сорт решава овај проблем тако што два пута пролази кроз низ. У првом пролазу се броје објекти који припадају сваком од Н сегмента. Почетак и крај сваког сегмента се затим израчунава као збир величина претходних сегмената. У другом пролазу замени се сваки објекат на своје место.

Америчка застава сортирање је најефикаснији са радиx чија је моћ 2, јер бит-схифтинг операције могу да се користе уместо скупих логаритама да се израчуна вредност сваке цифре. Када су стрингови за сортирање 8- или 7- битни , као што су код АСЦИИ кодирања, по правилу се користи бројни систем од 256 што одговара сортирању карактер по карактер.

Псеудокод

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)

Проста имплементација у Пајтону

Овај пример написан у Пајтон програмском језику показаће америцан флаг сорт за сваки корен из 2 или већи. Јеноставност излагања је одабрана изнад паметног програмирања па се функције користе уместо технике померања битова.

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 >= 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)

Види још

• Сегментно сортирање

Спољашње везе

• Paul E. Black, American flag sort at the National Institute of Standards and Technology, Dictionary of Algorithms and Data Structures.