Write a short note on Quick sort, Radix sort and Bucket sort with example.

Quick Sort

Overview: Quick sort is a popular sorting algorithm that employs a divide-and-conquer approach to efficiently sort a list of elements. It works by selecting a pivot element, partitioning the list into two sublists based on the pivot, and recursively applying the same process to the sublists.

Algorithm:

1. Choose a pivot element from the list.
2. Partition the list into two sublists: one containing elements less than the pivot and the other containing elements greater than or equal to the pivot.
3. Recursively apply steps 1 and 2 to the two sublists until all sublists are sorted.

Example: Consider the list [5, 3, 8, 2, 1, 4, 7, 6].

1. Choose the pivot element as 4.
2. Partition the list into two sublists: [2, 1, 3] and [5, 7, 8, 6].
3. Recursively apply steps 1 and 2 to the sublists:
   • For the sublist [2, 1, 3], choose the pivot as 2. Partition into [1] and [3, 2]. Recursively sort these sublists.
   • For the sublist [5, 7, 8, 6], choose the pivot as 7. Partition into [5, 6] and [8]. Recursively sort these sublists.

The final sorted list is [1, 2, 3, 4, 5, 6, 7, 8].

Complexity:

• Best-case time complexity: O(n log n)
• Average-case time complexity: O(n log n)
• Worst-case time complexity: O(n^2)

Radix Sort

Overview: Radix sort is a non-comparative sorting algorithm that works by repeatedly sorting the elements of a list based on individual digits or bits. It processes the elements from the least significant digit to the most significant digit, creating multiple passes through the list.

Algorithm:

1. Determine the maximum number to identify the number of digits.
2. Create bins or buckets, one for each digit or bit value.
3. Perform multiple passes through the list, starting from the least significant digit:
   • In each pass, distribute the elements into the appropriate bins based on the current digit or bit value.
   • Empty the bins back into the list, maintaining the order of elements within each bin.

Example: Consider the list [170, 45, 75, 90, 802, 24, 2, 66].

1. Maximum number is 802, which has 3 digits.
2. Create bins for digits 0 to 9.
3. First pass (least significant digit):
   • Distribute elements into bins based on the last digit:
     • Bin 0: [2]
     • Bin 2: [75, 90]
     • Bin 4: [45]
     • Bin 5: [170, 802]
     • Bin 6: [66]
   • Empty the bins back into the list: [2, 75, 90, 45, 170, 802, 66]
4. Second pass (middle digit):
   • Distribute elements into bins based on the middle digit:
     • Bin 0: [2, 75, 66]
     • Bin 1: [45, 170]
     • Bin 2: [90, 802]
   • Empty the bins back into the list: [2, 75, 66, 45, 170, 90, 802]
5. Third pass (most significant digit):
   • Distribute elements into bins based on the most significant digit:
     • Bin 0: [2]
     • Bin 1: [45, 75]
     • Bin 2: [66, 90]
     • Bin 8: [170, 802]
   • Empty the bins back into the list: [2, 45, 75, 66, 90, 170, 802]

The final sorted list is [2, 45, 66, 75, 90, 170, 802].

Complexity:

• Time complexity: O(nk), where n is the number of elements and k is the maximum number of digits.

Bucket Sort

Overview: Bucket sort is a sorting algorithm that divides the input into several equally sized buckets and distributes the elements into these buckets. Each bucket is then sorted individually, and the sorted elements are concatenated to obtain the final sorted list.

Algorithm:

1. Determine the maximum and minimum values in the input list.
2. Divide the input range into n equally sized buckets.
3. Distribute the elements into the appropriate buckets based on their values.
4. Sort the elements within each bucket using any sorting algorithm (e.g., insertion sort).
5. Concatenate the sorted elements from all buckets to obtain the final sorted list.

Example: Consider the list [0.897, 0.565, 0.656, 0.1234, 0.389, 0.666, 0.1111].

1. Maximum value is 0.897 and minimum value is 0.1111.
2. Divide the range [0.1111, 0.897] into 3 equally sized buckets: [0.1111, 0.3323], [0.3324, 0.5556], [0.5557, 0.897].
3. Distribute the elements into the appropriate buckets:
   • Bucket 1: [0.1234, 0.1111]
   • Bucket 2: [0.389, 0.565]
   • Bucket 3: [0.656, 0.666, 0.897]
4. Sort the elements within each bucket:
   • Bucket 1: [0.1111, 0.1234]
   • Bucket 2: [0.389, 0.565]
   • Bucket 3: [0.656, 0.666, 0.897]
5. Concatenate the sorted elements from all buckets: [0.1111, 0.1234, 0.389, 0.565, 0.656, 0.666, 0.897]

The final sorted list is [0.1111, 0.1234, 0.389, 0.565, 0.656, 0.666, 0.897].

Complexity:

• Time complexity: O(n + k), where