Američka zastava sortiranje
Američka zastava sortiranje () 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. 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.

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.

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)

Vidi još 
 Segmentno sortiranje

Reference

Spoljašnje veze 
 

Алгоритми сортирања
Američka zastava sortiranje ( ) 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 . 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 istovremenokanti . Sa nekim optimizacijama , dva puta je brži od kviksort za velike nizove stringova . 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 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ć jer bit-shifting operacije mogu da se koriste umesto skupih logaritama da se izračuna vrednost svake cifre . Kada su stringovi za sortiranje ili bitni , kao što su kod ASCII kodiranja , po pravilu se koristi brojni sistem odšto odgovara sortiranju karakter po karakter . 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.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 izili 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 == 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 , len( a_list ) , max_digit , radix ) Vidi još Segmentno sortiranje Reference Spoljašnje veze Алгоритми сортирања