Thursday, July 28, 2016

Fastest sorting algorithm for integers - radixsort


A programmer has often the problem of fast sorting. Which algorithm he/she should take for that type of data. I will show you simply the fastest algorithm but only for sorting integers. I'm talking about the radixsort. But sth like the fastest algorithm doesn't exist for sorting. Because it's always a question of the data type and pattern wich you wan't to sort. 

The code is written in python, because nearly every programmer understands it ^^ 

def radixsort( aList ):
  RADIX = 10
  maxLength = False
  tmp , placement = -1, 1
  while not maxLength:
    maxLength = True
    # declare and initialize buckets
    buckets = [list() for _ in range( RADIX )]
    # split aList between lists
    for  i in aList:
      tmp = i / placement
      buckets[tmp % RADIX].append( i )
      if maxLength and tmp > 0:
        maxLength = False
    # empty lists into aList array
    a = 0
    for b in range( RADIX ):
      buck = buckets[b]
      for i in buck:
        aList[a] = i
        a += 1
    # move to next digit
    placement *= RADIX

No comments:

Post a Comment