9.bucketSort.md

Bucket sort

Bucket sort is an upgraded version of count sort. It uses the mapping relationship of functions, and the key to efficiency lies in the determination of this mapping function. To make bucket sort more efficient, we need to do two things:

1. In the case of sufficient extra space, try to increase the number of buckets
2. The mapping function used can evenly distribute the input N data into K buckets

At the same time, for the sorting of elements in the bucket, the choice of the comparison sorting algorithm is critical to the performance.

1. When is the fastest

When the input data can be evenly distributed to each bucket.

2. When is the slowest

When the input data is allocated to the same bucket.

3. JavaScript code implementation

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // minimum value of input data
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // maximum value of input data
      }
    }

    //Initialize the bucket
    var DEFAULT_BUCKET_SIZE = 5;            // Set the default number of buckets to 5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;   
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

//Using the mapping function to allocate data to each bucket
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]); // Sort each bucket, insertion sort is used here
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);
        }
    }

    return arr;
}

4. Java code implementation

public class BucketSort implements IArraySort {

    private static final InsertSort insertSort = new InsertSort();

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
// Copy arr without changing the parameter content
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return bucketSort(arr, 5);
    }

    private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
        if (arr.length == 0) {
            return arr;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        // Use the mapping function to allocate data to each bucket
        for (int i = 0; i < arr.length; i++) {
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {
            if (bucket.length <= 0) {
                continue;
            }
            // Sort each bucket, insertion sort is used here
            bucket = insertSort.sort(bucket);
            for (int value : bucket) {
                arr[arrIndex++] = value;
            }
        }

        return arr;
    }

    /**
     * Automatically expand and save data
     *
     * @param arr
     * @param value
     */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

}
```

## 5. PHP Code

```php
function bucketSort($arr, $bucketSize = 5)
{
    if (count($arr) === 0) {
      return $arr;
    }

    $minValue = $arr[0];
    $maxValue = $arr[0];
    for ($i = 1; $i < count($arr); $i++) {
      if ($arr[$i] < $minValue) {
          $minValue = $arr[$i];
      } else if ($arr[$i] > $maxValue) {
          $maxValue = $arr[$i];
      }
    }

    $bucketCount = floor(($maxValue - $minValue) / $bucketSize) + 1;
    $buckets = array();
    for ($i = 0; $i < count($buckets); $i++) {
        $buckets[$i] = [];
    }

    for ($i = 0; $i < count($arr); $i++) {
        $buckets[floor(($arr[$i] - $minValue) / $bucketSize)][] = $arr[$i];
    }

    $arr = array();
    for ($i = 0; $i < count($buckets); $i++) {
        $bucketTmp = $buckets[$i];
        sort($bucketTmp);
        for ($j = 0; $j < count($bucketTmp); $j++) {
            $arr[] = $bucketTmp[$j];
        }
    }

    return $arr;
}
```