Изменение алгоритма сортировки счета?

Question

Я понимаю, что это не стандартная сортировка, как указано в CLRS, но что делает моя упрощенная версия недостаточной, чем у стандартной сортировки? Я реализую только свои целые положительные числа, но это должно быть довольно легко настроить (используя карты).

def count_sort(array): 
    maximum = max(array) 
    minimum = min(0, min(array)) 
    count_array = [0]*(maximum-minimum+1) 

    for val in array: 
     count_array[val] += 1 

    sorted_array = [] 
    for i in range(minimum, maximum+1): 
     if count_array[i] > 0: 
      for j in range(0, count_array[i]): 
       sorted_array.append(i) 

    return sorted_array 

array = [3,2,-1,1,5,0,10,18,25,25] 
print array 
print count_sort(array) 

Edit: Причина, почему я думал, что это не был стандартный подсчет рода потому, что алгоритм рассматривается в лекции MIT OpenCourseWare казался немного сложнее (http://youtu.be/0VqawRl3Xzs?t = 34m54s).

Answer 1

Возможно, вы имели в виду http://en.wikipedia.org/wiki/Counting_sort?

Если да, это почти похоже на ваш код. Но у него есть одно улучшение: «Относительный порядок предметов с одинаковыми ключами сохраняется здесь, т. Е. Это стабильный вид». Поэтому, если вы сортируете словарь словаря по значению ключа, значения остаются неизменными, если они имеют одинаковые ключи.

Answer 2

Вы делаете что-то странное с вашим минимумом и макс. Попробуйте это:

def count_sort(array): 
    maximum = max(array) 
    minimum = min(array) 
    count_array = [0]*(maximum-minimum+1) 

    for val in array: 
     count_array[val-minimum] += 1 

    sorted_array = [] 
    for i in range(minimum, maximum+1): 
     if count_array[i-minimum] > 0: 
      for j in range(0, count_array[i-minimum]): 
       sorted_array.append(i) 

    print sorted_array 

array = [3,2,-1,1,5,0,10,18,25,25] 
print array 
count_sort(array) 

Answer 3

Я не вижу проблем с тем, как вы подсчитывать-сортировочного, во всяком случае некоторые предложения на ваш код приходит в голову, что, может быть, может вас заинтересовать.

Например, строка:

minimum = min(0, min(array)) 

может быть заменен:

minimum = min(0, *array) 

Если вы запускали код используется питон-2.x xrange() вместо range(), так что вы можете изменить:

for i in range(minimum, maximum+1): 

с:

for i in xrange(minimum, maximum+1): 

Для последнего цикла вы на самом деле не нужно range() вообще, проверьте вопрос pythonic way to do something N times, так что вы можете изменить:

for j in range(0, count_array[i]): 
    sorted_array.append(i) 

с:

for _ in itertools.repeat(None, count_array[i]): 
    sorted_array.append(i)