Summary of barrel sort and radix sort based on python

This paper first illustrates the operation steps of two kinds of sorting methods, then lists the implementation process with python, and finally summarizes the advantages and disadvantages of the bucket sorting method.

1. Bucket sorting:

Sort 1 array [5,3,6,1,2,7,5,10]

Values are between 1-10. Create 10 buckets:

[0 0 0 0 0 0 0 0 0 0 barrel]

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] values represented by buckets

Go through the groups, the first number 5, the fifth bucket plus 1

[0 0 0 0 1 0 0 0 0 0]

The second number is 3, the third bucket plus 1

[0 0 1 0 1 0 0 0 0 0]

After traversing

[1 1 1 0 2 1 1 0 0 1]

The output

[1 2 3 5 5 6 7 10]

Code:

def bucket_sort(lst):
 buckets = [0] * ((max(lst) - min(lst))+1)
 for i in range(len(lst)):
  buckets[lst[i]-min(lst)] += 1
 res=[]
 for i in range(len(buckets)):
  if buckets[i] != 0:
   res += [i+min(lst)]*buckets[i]
 return res

2. Radix sort:

For example, sort the following data sequence.

192,221,12,23

You can observe that each piece of data has at most three bits, so you can break each piece of data into three keywords: hundreds (high), 10 (low), and ones (low). If you think conventially, you're going to compare the hundreds place, the hundreds place, the same hundreds place, and then you're going to compare the 10 places, the 10 places; And then finally we compare the ones place. The radix sort method must rely on another sort method to sort any 1 subkeyword, and this sort method must be stable. For the sub-keywords separated from multiple keywords, they are located in the enumerable range of 0-9, which is not large, so the efficiency of bucket sorting is very good.

Code:

from random import randint
def radix_sort(lis,d):
 for i in xrange(d):#d Wheel sort 
  s = [[] for k in xrange(10)]# Because each 1 All the digits 0~9 , therefore, to establish 10 A barrel 
  for j in lis:
   s[j/(10**i)%10].append(i)
  li = [a for b in s for a in b]
 return li

The elements in the array are sorted from low to high. For the first round [192,221,12,23], the ones with the same digits are placed in one group, s[1] =[221],s[2]=[192,12],s[3]=23, the second round is sorted by 10 digits, s[1]=[12],s[2]=[221,23],s[9]=[192], the third round is sorted by hundreds digits. s [0] = [12, 10], s [1] = [192], s [2] = [221]

Conclusion:

Bucket sort and radix sort often appear as bucket sort, and radix sort has many rounds of bucket sort. Bucket sorting is no longer a comparation-based sorting method, it is a more ingenious sorting method, but this sorting method requires the sorted sequence to meet the following two characteristics: all the values of the sorted sequence are within the range of one enumeration; The enumerable range in which the to be sorted should not be too large, otherwise sorting overhead would be too high. It can be used to rank students' scores, since scores range within 100 for several students.

Bucket sorting is expensive in space and requires two arrays. The first buckets array is used to record the number of elements "dropped" into each bucket, thus storing the positions of each element in the ordered sequence, and the second array is used to cache the data to be sorted. It can only row plastic arrays. And when k is large and the array length n is small, that is, k > > When n, the secondary array C[k+1] consumes a large amount of space.