If you're familiar with sorting algorithms in computer science, you may have heard of radix sort and bucket sort. These two algorithms are commonly used for sorting data efficiently. But what exactly sets them apart? Let's dive into the differences between radix sort and bucket sort.
Radix sort is a non-comparative sorting algorithm that sorts data with integer keys by grouping keys based on individual digits which share the same significant position and value. It operates by distributing the elements into 10 buckets according to their least significant digit, then concatenating the sorted lists for each digit. This process is repeated for each subsequent digit until the list is sorted.
def radix_sort(arr):
# Find the maximum number to know number of digits
max1 = max(arr)
exp = 1
while max1 // exp > 0:
counting_sort(arr, exp)
exp *= 10
# Applying counting sort to sort elements based on significant digit
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in range(n):
index = arr[i] // exp
count[index % 10] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
index = arr[i] // exp
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
for i in range(n):
arr[i] = output[i]
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print(arr)
Bucket sort is another non-comparative sorting algorithm that distributes elements into a finite number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm or recursively applying bucket sort. Once all the buckets are sorted, the elements are concatenated to produce the final sorted array.
def bucket_sort(arr):
n = len(arr)
buckets = [[] for _ in range(n)]
for num in arr:
index = int(num * n)
buckets[index].append(num)
for bucket in buckets:
insertion_sort(bucket)
k = 0
for i in range(n):
for j in range(len(buckets[i])):
arr[k] = buckets[i][j]
k += 1
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
arr = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
bucket_sort(arr)
print(arr)
In summary, radix sort and bucket sort are both efficient sorting algorithms that have their own distinct characteristics. Radix sort is based on the value of digits, while bucket sort works by distributing elements into separate buckets. Understanding these differences can help you choose the right sorting algorithm for your specific needs.