Američka zastava sortiranje

Američka zastava sortiranje (engl. American flag sort) je efikasna varijanta radiks sortiranja koja distribuira elemente u stotine segmenata. Neuporedni algoritmi za sortiranje kao što su radix sort i american flag sort se obično koriste za sortiranje velikih objekata kao što su stringovi, za koje poredjenje nije jedinica – vreme rada.^[1] Američka zastava sortiranje prolazi kroz bitove objekata, s obzirom na nekoliko bitova svakog objekta u isto vreme. Za svaki skup bitova, american flag ima dva prolaza kroz niz objekata: prvo da prebroji broj objekata koji će pasti u svaku kantu, a drugi da smesti svaki objekat u njegovu kantu. Ovo radi dobro, posebno kada se sortiraju bajtovi koristeći istovremeno 256 kanti. Sa nekim optimizacijama, dva puta je brži od kviksort za velike nizove stringova.^[1]

Ime potiče po analogija sa holandskim nacionalnim problemom u vezi zastave u poslednjem koraku: efikasna podela niza u mnogim „vrstama“ (prugama).

Algoritam[уреди | уреди извор]

Algoritam za sortiranje u opštem slučaju sortira niz objekata prema nekoj naručenoj šemi. Nasuprot algoritmima za sortiranje koji su zasnovani na poređenju, kao što je kviksort, sortiranje američke zastave može samo sortirati cele brojeve (integers) (ili objekte koji se mogu tumačiti kao celi brojevi). Algoritmi za sortiranje u mestu, uključujući i american flag sort, rade bez izdvajanja značajne količine memorije, umesto toga koriste originalni niz. Ovo je značajna prednost, i u uštedi memorije i vremena za kopiranje niza.

Američka zastava sortiranje, uspešto radi deljenjem niza objekata u segmente na osnovu prve cifre njihove baze – N reprezentacije (baza koja se koristi naziva se radix). Kada je N 2, svaki objekat može biti zamenjen odgovarajućim segmentom, koristeci algoritam holandke nacionalne zastave. Međutim, kada je N veće , objekti ne mogu odmah biti zamenjeni na svoje mesto, zbog toga što nije poznato gde svaki segment treba da pocne i da se završi. American flag sort rešava ovaj problem tako što dva puta prolazi kroz niz. U prvom prolazu se broje objekti koji pripadaju svakom od N segmenta. Početak i kraj svakog segmenta se zatim izračunava kao zbir veličina prethodnih segmenata. U drugom prolazu zameni se svaki objekat na svoje mesto.

Američka zastava sortiranje je najefikasniji sa radix čija je moć 2, jer bit-shifting operacije mogu da se koriste umesto skupih logaritama da se izračuna vrednost svake cifre. Kada su stringovi za sortiranje 8- ili 7- bitni , kao što su kod ASCII kodiranja, po pravilu se koristi brojni sistem od 256 što odgovara sortiranju karakter po karakter.^[1]

Pseudokod[уреди | уреди извор]

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)

Prosta implementacija u Pajtonu[уреди | уреди извор]

Ovaj primer napisan u Pajton programskom jeziku pokazaće american flag sort za svaki koren iz 2 ili veći. Jenostavnost izlaganja je odabrana iznad pametnog programiranja pa se funkcije koriste umesto tehnike pomeranja bitova.

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)