Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Counting sort, like radix sort and bucket sort,
- # is an integer based algorithm (i.e. the values of the input
- # array are assumed to be integers). Hence counting sort is
- # among the fastest sorting algorithms around, in theory. The
- # particular distinction for counting sort is that it creates
- # a bucket for each value and keep a counter in each bucket.
- # Then each time a value is encountered in the input collection,
- # the appropriate counter is incremented. Because counting sort
- # creates a bucket for each value, a restriction is
- # that the maximum value in the input array be known beforehand.
- # Implementation notes:
- # 1] Since the values range from 0 to k, create k+1 buckets.
- # 2] To fill the buckets, iterate through the input list and
- # each time a value appears, increment the counter in its
- # bucket.
- # 3] Now fill the input list with the compressed data in the
- # buckets. Each bucket's key represents a value in the
- # array. So for each bucket, from smallest key to largest,
- # add the index of the bucket to the input array and
- # decrease the counter in said bucket by one; until the
- # counter is zero.
- # Best Case O(n+k); Average Case O(n+k); Worst Case O(n+k),
- # where n is the size of the input array and k means the
- # values range from 0 to k.
- def counting_sort(some_list):
- max_value = 0
- for i in range(len(some_list)):
- if some_list[i] > max_value:
- max_value = some_list[i]
- buckets = [0] * (max_value+ 1)
- for i in some_list:
- buckets[i] += 1
- i = 0
- for j in range(max_value + 1):
- counter, repetions = 1, buckets[j]
- while counter <= repetions:
- some_list[i] = j
- counter+=1
- i+=1
- return some_list
- print(counting_sort([1,23,4,5,6,7,8]))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement