Talk:American flag sort

The sample Python code does not properly sort the array

There is something wrong with the implementation or it is partial and needs to be changed.

from math import floor, log
from copy import copy

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)
    
A = [((20*(x**3))//1)+67500 for x in range(-15,16)]
print(A)
import random
random.shuffle(A)
print(A)
american_flag_sort(A, 4)
print(A)

The output is:

[0, 12620, 23560, 32940, 40880, 47500, 52920, 57260, 60640, 63180, 65000, 66220, 66960, 67340, 67480, 67500, 67520, 67660, 68040, 68780, 70000, 71820, 74360, 77740, 82080, 87500, 94120, 102060, 111440, 122380, 135000]
[74360, 60640, 111440, 32940, 65000, 66220, 0, 70000, 67500, 135000, 94120, 102060, 82080, 23560, 122380, 66960, 67480, 67520, 67340, 47500, 12620, 87500, 63180, 68780, 40880, 57260, 71820, 67660, 52920, 77740, 68040]
[0, 32940, 66960, 52920, 23560, 40880, 57260, 74360, 60640, 12620, 65000, 47500, 63180, 67480, 67520, 67340, 66220, 70000, 67500, 68780, 68040, 71820, 67660, 77740, 94120, 87500, 82080, 111440, 102060, 122380, 135000]

The last array, which is result from the function, is not properly sorted. Different radixes give different results, but none of them are correct.

Tested using Python 3.4.3 on Linux x64.

80.220.91.165 (talk) 10:23, 24 November 2015 (UTC)

Very late response, but this is correct, the provided Python code had several bugs. It was probably never tested. I'll go ahead and fix them. For future reference, the changes were as follows (I can't be arsed to summarize them considering how many bugs there were):

 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
+    offset = start
+    offsets = [start]
     for i in range(radix):
-        offsets[i] = sum
-        sum += counts[i]
+        offset += counts[i]
+        offsets.append(offset)
     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]:
+    while cur_block < radix:
+        i = next_free[cur_block]
+        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]
+        if radix_val != cur_block:
+            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

I'd rather replace the whole thing with something else though. I might still do that a little later.

MaksVerver (talk) 19:43, 27 July 2023 (UTC)

The original implementation is rather different--somewhat shorter, and much faster

See: Engineering Radix Sort, p. 16, and appendix program C. — Preceding unsigned comment added by 70.16.100.236 (talk) 20:03, 20 April 2018 (UTC)

Comparing "bytes" instead of objects

I just edited the page to say that American flag sort sorts on the basis of the bytes (mathematical representation) of the objects instead of a object-defined comparison.

I find this wording problematic because likening bytes to mathematical representation doesn't feel very accurate. Are there any better words out there? DesmondWillowbrook (talk) 17:20, 4 February 2023 (UTC)