鸽巢排序解释

1. Overview

In this tutorial, we’ll learn about the pigeonhole sorting algorithm.

2. What Is Pigeonhole Sort?

Pigeonhole sort is appropriate for sorting arrays of elements where the number of elements in the array () is close to the range of possible values inside the array ().

For example, if we had an array with elements , is 9, and is 1 through 9, which equals 9. Therefore, we can use pigeonhole sort since is equal to .

Furthermore, pigeonhole sort requires time.

3. How Does It Work?

Now let’s see how the sorting algorithm works.

3.1. Find the Range

First, we should find the range of possible values inside the array:

algorithm FindingTheRange(arr, n):
    // INPUT
    //    arr = the array to find the range from
    //    n = the number of elements in the array
    // OUTPUT
    //    N = the range of possible values inside the array

    min <- arr[0]
    max <- arr[0]

    for i <- 1 to n - 1:
        if arr[i] < min:
            min <- arr[i]
        if arr[i] > max:
            max <- arr[i]

    N <- max - min + 1

    return N

Now we can create pigeonholes with a size equal to .

3.2. Fill the Pigeonholes

Now let’s create the pigeonholes and fill them:

algorithm FillPigeonholes(arr, n, N, min):
    // INPUT
    //    arr = the array to be sorted
    //    n = the number of elements in the array
    //    N = the range of possible values in the array
    //    min = the minimum value in the array
    // OUTPUT
    //    pholes = the array of vectors (pigeonholes) filled with elements from arr

    pholes[N] <- array of empty vectors

    for i <- 0 to n - 1:
        push arr[i] into pholes[arr[i] - min]

    return pholes

The first line creates an array of vectors with the size of . Each vector is a pigeonhole that keeps equal elements.

After that, we go through the original array and put each element inside a pigeonhole with index .

3.3. Fill the Original Array

Now that we have sorted the elements and put them into the pigeonholes, we should put them in the original array:

algorithm FillingOriginalArray(arr, pholes, N):
    // INPUT
    //    arr = the original array to be filled with sorted elements
    //    pholes = the array of pigeonholes (vectors) filled in the previous step
    //    N = the number of pigeonholes
    // OUTPUT
    //    arr = the original array filled with sorted elements from pigeonholes

    index <- 0

    for i <- 0 to N - 1:
        // Iterate through each item in the phole (pigeonhole) at index i
        for it in pholes[i]:
            arr[index] <- it
            index <- index + 1

    return arr

The above code iterates through the pigeonholes and copies each element into the original array.

4. An Example

Let’s assume we have .

In the first step, we calculate , , and .

In the second step, we create the pigeonholes and fill them:

In the third step, we copy the elements from the pigeonholes into the original array:

We’ve successfully sorted the array.

5. Conclusion

In this tutorial, we learned how the pigeonhole sorting algorithm works and when it’s appropriate to use it.