---

📘 Bucket Sort (Bin Sort)

Bucket Sort is a distribution-based, linear-time sorting algorithm that works by:

1. Distributing elements into several buckets based on value ranges
2. Sorting each bucket individually (often using insertion sort)
3. Concatenating all buckets to get the final sorted list

---

📌 When Bucket Sort Works Best?

Bucket Sort is efficient when:

• Input is uniformly distributed
• Values are in a known range
• Values are real numbers in [0, 1) or limited ranges

Examples:

• Fractional numbers
• Percentages
• Floating-point values
• Normalized data

---

📘 Steps of Bucket Sort

1. Create k empty buckets.
2. Insert each element of array into its appropriate bucket using a hash function:
   [
   \text{index} = \lfloor k \times value \rfloor
   ]
3. Sort each bucket (usually insertion sort because buckets are small).
4. Concatenate all buckets in order.

---

📘 Time Complexity

Case	Time
Best Case	O(n)
Average Case	O(n)
Worst Case	O(n²)

Worst case occurs when:

• All elements fall into one bucket
  → then sorting that bucket takes O(n²)

---

📘 Space Complexity

• O(n + k)
  (Extra space for buckets)

---

📌 Characteristics

• Not in-place
• Stable (if bucket sorting algorithm is stable)
• Extremely fast for uniformly distributed data
• Often used in applications like graphics, clustering, hashing

---

📘 Python Code for Bucket Sort

This version sorts floating point numbers in range [0, 1) (standard bucket sort case).

✔ Python Bucket Sort Implementation

def insertion_sort(bucket):
    for i in range(1, len(bucket)):
        key = bucket[i]
        j = i - 1
        
        while j >= 0 and bucket[j] > key:
            bucket[j + 1] = bucket[j]
            j -= 1
        
        bucket[j + 1] = key


def bucket_sort(arr):
    n = len(arr)
    if n == 0:
        return arr
    
    # Step 1: Create empty buckets
    buckets = [[] for _ in range(n)]
    
    # Step 2: Insert elements into buckets
    for num in arr:
        index = int(num * n)   # for numbers in [0,1)
        buckets[index].append(num)
    
    # Step 3: Sort each bucket
    for bucket in buckets:
        insertion_sort(bucket)
    
    # Step 4: Concatenate all buckets
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(bucket)
    
    return sorted_arr


# Example usage
arr = [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]
result = bucket_sort(arr)
print("Sorted array:", result)

---

📘 Example Output

Sorted array: [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]

---

📘 Bucket Sort for General Integers?

If you need Bucket Sort for integers, the logic is similar but bucket distribution changes.

(I can provide integer-based bucket sort if you want.)

---

📘 Summary (Exam Notes)

• Bucket Sort distributes data into multiple buckets
• Each bucket is sorted (usually by insertion sort)
• Works best for uniformly distributed data
• Time = O(n) average
• Worst time = O(n²)
• Space = O(n + k)
• Used for floating-point numbers, normalized data, hashing, etc.

---