Talk:American flag sort

From Wikipedia, the free encyclopedia
Jump to: navigation, search
          This article is of interest to the following WikiProjects:
WikiProject United States (Rated Start-class, Low-importance)
WikiProject icon This article is within the scope of WikiProject United States, a collaborative effort to improve the coverage of topics relating to the United States of America on Wikipedia. If you would like to participate, please visit the project page, where you can join the ongoing discussions.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.
 
WikiProject Computer science (Rated Start-class)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 
WikiProject Computing (Rated Start-class)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

The sample Python code does not properly sort the array[edit]

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)